如何在 C# 中执行 2 个非常大（超过 50 位）二进制字符串值的加法

Question

我一直在考虑添加二进制数，其中二进制数是字符串形式，我们将这两个二进制数相加以获得结果二进制数（字符串形式）。

到目前为止我一直在使用这个：

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

return result;

由 Whosebug 提供：Binary addition of 2 values represented as strings

但是，现在我想添加远远大于 long 数据类型范围的数字。例如，一个二进制值，其十进制结果是 BigInteger，即非常大的整数，如下所示：

111101101000010111101000101010001010010010010110011010100001000010110110110000110001101 等于149014059082024308625334669
1111001101011000001011000111100011101011110100101010010001110101011101010100101000001101000010000110001110100010011101011111111110110101100101110001010101011110001010000010111110011011 等于23307765732196437339985049250988196614799400063289798555

至少我认为是。

由 Whosebug 提供：

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

我使用了以上链接中提供的逻辑，或多或少是完美的。

但是，是否有更紧凑的方法来添加给定的两个二进制字符串？

请告诉我这个问题已经在我脑海中盘旋了一段时间。

Answer 1

这个问题很怀旧 - 谢谢。请注意，我的代码是解释性的且效率低下，几乎没有验证，但它适用于您的示例。你绝对不想在现实世界的解决方案中使用这样的东西，这只是为了说明二进制加法的原理。

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

这是代码

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

Answer 2

我将在 AlanK 的旁边添加一个替代解决方案，作为一个示例，说明您如何在添加之前不将数字转换为某种形式的整数来解决这个问题。

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

请注意，此解决方案比 Alan 的解决方案慢 ~10%（至少对于此测试用例而言），并且假设字符串到达方法时格式正确。

Answer 3

您可以利用之前使用的相同方案，但使用 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());

如何在 C# 中执行 2 个非常大（超过 50 位）二进制字符串值的加法

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

c#

biginteger