How to perform addition of 2 very large (over 50 digits) binary string values in C#

Question

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.

Answer 1

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());

Answer 2

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.

Answer 3

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();
    }
  }
}