只使用位运算符，如何将两个整数相加？

Question

在C#中，是否可以在不使用if、else、循环等结构的情况下对两个32位整数进行求和？

也就是说，是否可以仅使用按位操作OR(|)、AND(&)、XOR(^)、NOT(!)、左移(<<)和右移(>>)来实现？

- Delta

---

出于好奇，你为什么想要做这样的事情？ - Oded

据他自己所说，他只想理解添加二进制数字的逻辑。 - Jesper Fyhr Knudsen

没什么特别的，只是为了增加知识。我还没有上大学 :( - Delta

如果您对这种事情感兴趣，可以看一本名为《Hacker's Delight》的书（http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201914654/ref=sr_1_1?ie=UTF8&s=books&qid=1288608932&sr=8-1）。 - jasper

确保你已经阅读了Tanenbaum的《结构化计算机组织》。这是一本非常好的书，从很多低级别的东西开始，然后逐渐向上堆叠。 - elmattic

这是一个关于量子计算的好问题。 - vwvan

Answer 1

这里是一个供您娱乐的示例

unsigned int myAdd(unsigned int a, unsigned int b)
{
    unsigned int carry = a & b;
    unsigned int result = a ^ b;
    while(carry != 0)
    {
        unsigned int shiftedcarry = carry << 1;
        carry = result & shiftedcarry;
        result ^= shiftedcarry;
    }
    return result;
}

循环可以展开。它执行的次数取决于操作数中设置的位数，但从不超过 unsigned int 的宽度。一旦 carry 变为 0，下一次迭代就不会改变任何东西。

- Maciej Hehl

---

谢谢。这正是我在寻找的。现在我会尝试理解为什么这个方法有效。谢谢。 - Delta

有人能提供一个简明的证明，为什么对于任意表示大小，没有循环或递归的版本是不可能的吗？ - nietaki

我要指出的是，这也适用于现代Fortran，因为它没有无符号整数类型。可以简单地使用普通整数和此过程来保证无符号整数加法模2^w，其中w是您整数模型中的位数。通常，在Fortran中，整数是二进制补码，因此位将表示无符号整数，但如果打印整数的值，则会将位解释为带符号的二进制补码整数。如果要使用大整数并验证您的加法是否工作且模2^w，请小心解释结果。 - zbeekman

考虑一下N个1在一只手上，另一只手上只有一个1位。每次循环一次，进位向左移动一位。你必须至少循环N次，才能将进位移动到最左边，溢出到下一位或结果进位位。 - dascandy

Answer 2

试一下这个：

    private int add(int a, int b) {
        if(b == 0)
            return a;

        return add( a ^ b, (a & b) << 1);
    }

编辑： 更正了 if 语句

- Shatazone

---

我们需要在这里使用if语句吗？当b = 0时，a^b = a，因此结果保持不变。 - Anirudh

@Anirudh，是的。你需要一个基本情况来结束递归。 - lastoneisbearfood

将 if 语句改为 if ((a & b) == 0) return (a ^ b); 如何？这将减少一个额外的递归调用。 - rootkea

你能解释一下这个如何处理有符号整数吗？我理解的是：

1. 找到所有位的进位
2. 通过添加所有具有0/1组合的位来创建一个数字
3. 将进位左移并加到（2）中

- Nishit Mengar

Answer 3

想想加法是如何逐位进行的。将值移位以依次获取每个操作数的每个位，然后查看两个位的四个可能值，并计算结果位应该是什么以及是否存在进位位需要考虑。然后使用位运算符计算结果和进位。

- The Archetypal Paul

Answer 4

static int binaryadd(int x, int y)
{
  while (x != 0)
  {
    int c = y & x;
    y = y ^ x; 
    x = c << 1;             
  }
  return y;
}

- dragonfly02

Answer 5

public static int getSum(int p, int q)
{
    int carry=0, result =0;
    for(int i=0; i<32; i++)
    {
        int n1 = (p & (1<<(i)))>>(i); //find the nth bit of p
        int n2 = (q & (1<<(i)))>>(i); //find the nth bit of q

        int s = n1 ^ n2 ^ carry; //sum of bits
        carry = (carry==0) ? (n1&n2): (n1 | n2); //calculate the carry for next step
        result = result | (s<<(i)); //calculate resultant bit
    }

    return result;
}

把32位作为int类型使用就会占用32位空间。谢谢！

- Trying

---

i++ 不是加法，它表示将变量 i 的值加 1。;) - Qantas 94 Heavy

不喜欢负数，但易读性很好。 - user501743

Answer 6

public int getSum(int a, int b) {
    while(b!=0){
        int temp=a;
        a=a^b;
        b=(temp&b)<<1;
    }
    return a;
}

- lbndvs

Answer 7

int Add(int a, int b)
{
      int result = 0,
          // carry now contains common set bits of "a" and "b"
          carry = a & b;

      if (Convert.ToBoolean(carry))
      {
          // Sum of bits of "a" and "b" where at least one 
          // of the bits is not set
          result = a ^ b;

          // carry is shifted by one so that adding it 
          // to "a" gives the required sum
          carry = carry << 1;

          result = add(carry, result);
      }
      else
      {
          result = a ^ b;
      }

      return result;
}

两个二进制位的和可以使用异或运算符^来计算，进位位可以通过使用与运算符&来获得。 如果提供的a和b在同一位置上没有设置位，则使用^运算符可以得到a和b的和。

geeksforgeeks的评论

- codejockie

Answer 8

        int  b =  25;
        for (int t = 128; t > 0; t = t / 2)
        {
            if ((b & t) != 0) Console.Write("1 ");
            if ((b & t) == 0) Console.Write("0 ");
        }
        Console.WriteLine();
        //b = (sbyte)~b;
        int e = 22;
        for (int t = 128; t > 0; t = t / 2)
        {
            if ((e & t) != 0) Console.Write("1 ");
            if ((e & t) == 0) Console.Write("0 ");
        }
        Console.WriteLine();
        int c = b | e;
        for (int t = 128; t > 0; t = t / 2)
        {
            if ((c & t) != 0) Console.Write("1 ");
            if ((c & t) == 0) Console.Write("0 ");
        }

- naresh

---

提供的代码只是“int c = b | e”，这是按位或（OR）而不是加法。其余的代码只是将整数转换为二进制字符串的糟糕示例。 - peenut