0

I have been thinking of adding binary numbers where binary numbers are in a form of string and we add those two binary numbers to get a resultant binary number (in string).

So far I have been using this:

long first = Convert.ToInt64(a, 2); long second = Convert.ToInt64(b, 2); long addresult = first + second; string result = Convert.ToString(addresult, 2); return result;

Courtesy of Stackoverflow: Binary addition of 2 values represented as strings

But, now I want to add numbers which are far greater than the scope of a long data type. For Example, a Binary value whose decimel result is a BigInteger, i.e., incredibly huge integers as shown below:

  1. 111101101000010111101000101010001010010010010110011010100001000010110110110000110001101 which equals to149014059082024308625334669

  2. 1111001101011000001011000111100011101011110100101010010001110101011101010100101000001101000010000110001110100010011101011111111110110101100101110001010101011110001010000010111110011011 which equals to23307765732196437339985049250988196614799400063289798555

At least I think it does.

Courtesy of Stackoverflow:

  1. C# Convert large binary string to decimal system
  2. BigInteger to Hex/Decimal/Octal/Binary strings?

I have used logic provided in above links which are more or less perfect.

But, is there a more compact way to add the given two binary strings?

Kindly let me know as this question is rattling in my mind for some time now.

Improve this question
2
  • Is there any particular reason why you can't just use binary addition logic to build a new string, rather than converting it to some kind of integer and then converting it back? Commented Jul 25, 2021 at 6:22
  • @KieranMoynihan Thanks for your question, actually there is a reason. A simple one, really! I am not familiar with one or simply don't know. Believe me when I say I have never used anything remotely related. I faced a question like this in one of assessments I took where this was one of the test cases. Other test cases were bigger than this. Commented Jul 25, 2021 at 6:37

3 Answers 3

Reset to default
2

You can exploit the same scheme you used before but with BigInteger:

using System.Linq; using System.Numerics; ... BigInteger first = a.Aggregate(BigInteger.Zero, (s, item) => s * 2 + item - '0'); BigInteger second = b.Aggregate(BigInteger.Zero, (s, item) => s * 2 + item - '0'); StringBuilder sb = new StringBuilder(); for (BigInteger addresult = first + second; addresult > 0; addresult /= 2) sb.Append(addresult % 2); if (sb.Length <= 0) sb.Append('0'); string result = string.Concat(sb.ToString().Reverse());
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks for the solution. I must say this is far too smaller and quicker! But I have a same question for you too. Is this solution enough for bigger binary strings than I provided in this questions, like 30-40 digits large?
@Abhishek Raj: BigInteger is an integer value of arbitrary length, it'll be enough and to spare for 30-40 digit numbers
1

This question was a nostalgic one - thanks. Note that my code is explanatory and inefficient with little to no validation, but it works for your example. You definitely do not want to use anything like this in a real world solution, this is just to illustrate binary addition in principle.

BinaryString#1 111101101000010111101000101010001010010010010110011010100001000010110110110000110001101 decimal:149014059082024308625334669 BinaryString#2 1111001101011000001011000111100011101011110100101010010001110101011101010100101000001101000010000110001110100010011101011111111110110101100101110001010101011110001010000010111110011011 decimal:23307765732196437339985049250988196614799400063289798555 Calculated Sum 1111001101011000001011000111100011101011110100101010010001110101011101010100101000001101000010001101111011100101011010100101010000000111111000100100101001100110100000111001000100101000 decimal:23307765732196437339985049251137210673881424371915133224 Check 23307765732196437339985049251137210673881424371915133224 decimal:23307765732196437339985049251137210673881424371915133224

Here's the code

using System; using System.Linq; using System.Numerics; namespace ConsoleApp3 { class Program { // return 0 for '0' and 1 for '1' (C# chars promotion to ints) static int CharAsInt(char c) { return c - '0'; } // and vice-versa static char IntAsChar(int bit) { return (char)('0' + bit); } static string BinaryStringAdd(string x, string y) { // get rid of spaces x = x.Trim(); y = y.Trim(); // check if valid binaries if (x.Any(c => c != '0' && c != '1') || y.Any(c => c != '0' && c != '1')) throw new ArgumentException("binary representation may contain only '0' and '1'"); // align on right-most bit if (x.Length < y.Length) x = x.PadLeft(y.Length, '0'); else y = y.PadLeft(x.Length, '0'); // NNB: the result may require one more bit than the longer of the two input strings (carry at the end), let's not forget this var result = new char[x.Length]; // add from least significant to most significant (right to left) var i = result.Length; var carry = '0'; while (--i >= 0) { // to add x[i], y[i] and carry // - if 2 or 3 bits are set then we carry '1' again (otherwise '0') // - if the number of set bits is odd the sum bit is '1' otherwise '0' var countSetBits = CharAsInt(x[i]) + CharAsInt(y[i]) + CharAsInt(carry); carry = countSetBits > 1 ? '1' : '0'; result[i] = countSetBits == 1 || countSetBits == 3 ? '1' : '0'; } // now to make this byte[] a string var ret = new string(result); // remember that final carry? return carry == '1' ? carry + ret : ret; } static BigInteger BigIntegerFromBinaryString(string s) { var biRet = new BigInteger(0); foreach (var t in s) { biRet = biRet << 1; if (t == '1') biRet += 1; } return biRet; } static void Main(string[] args) { var s1 = "111101101000010111101000101010001010010010010110011010100001000010110110110000110001101"; var s2 = "1111001101011000001011000111100011101011110100101010010001110101011101010100101000001101000010000110001110100010011101011111111110110101100101110001010101011110001010000010111110011011"; var sum = BinaryStringAdd(s1, s2); var bi1 = BigIntegerFromBinaryString(s1); var bi2 = BigIntegerFromBinaryString(s2); var bi3 = bi1 + bi2; Console.WriteLine($"BinaryString#1\n {s1}\n decimal:{bi1}"); Console.WriteLine($"BinaryString#2\n {s2}\n decimal:{bi2}"); Console.WriteLine($"Calculated Sum\n {sum}\n decimal:{BigIntegerFromBinaryString(sum)}"); Console.WriteLine($"Check\n {bi3}\n decimal:{bi3}"); Console.ReadKey(); } } }
Improve this answer

2 Comments

Thanks for your solution. I must be honest and say that I am still trying to understand the while loop used for addition as I have myself encountered this problem as an assessment question and have never seen this in the real world. I must say that your solution and comments provided are very explanatory. I am positive it will help me understand this even more. I just have one question. Can this solution be used if test cases are rather smaller (in the range of int data type) as well as rather larger than the provided example??
It will work for arbitrary length strings. If you intend converting back and forth to system integer types though, be aware that these strings are "ordered intuitively" from most to least significant bit (as you might expect in a textbook) but on Intel platforms numeric types are stored in little endian order (reversed, from least significant to most significant byte). A UInt16 with value 46971 (0xB77B) will appear in memory in byte order |7B|B7|, 0x12345678 as |78|56|34|12| etc. You'll also want to watch out for signed types (2s complement notation). Good luck on your journey.
1

I'll add an alternative solution alongside AlanK's just as an example of how you might go about this without converting the numbers to some form of integer before adding them.

 static string BinaryStringAdd(string b1, string b2) { char[] c = new char[Math.Max(b1.Length, b2.Length) + 1]; int carry = 0; for (int i = 1; i <= c.Length; i++) { int d1 = i <= b1.Length ? b1[^i] : 48; int d2 = i <= b2.Length ? b2[^i] : 48; int sum = carry + (d1-48) + (d2-48); if (sum == 3) { sum = 1; carry = 1; } else if (sum == 2) { sum = 0; carry = 1; } else { carry = 0; } c[^i] = (char) (sum+48); } return c[0] == '0' ? String.Join("", c)[1..] : String.Join("", c); }

Note that this solution is ~10% slower than Alan's solution (at least for this test case), and assumes the strings arrive to the method formatted correctly.

Improve this answer

3 Comments

Depending on what the large numbers are used for after this addition, this seems to be a far more efficient solution.
@kierenMoynihan Thanks for the solution. I must admit that this solution looks way less troublesome and sleeker solution than the above. Just to confirm, can this be used for text cases that are even more larger than the ones provided?
@AbhishekRaj Yes. So long as you can populate your string variables on your side (i.e. the values fit in a string), it should be able to run.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.