59

In C#, is it possible to perform a sum of two 32-bit integers without using things like if..else, loops etc?

That is, can it be done using only the bitwise operations OR (|), AND (&), XOR (^), NOT (!), shift left (<<) and shift right (>>)?

6
  • 1
    Out of curiosity, why do you want to do such a thing?
    – Oded
    Nov 1, 2010 at 10:18
  • 2
    According to him self, he just wants to understand the logic behind adding binary numbers. Nov 1, 2010 at 10:23
  • Nothing special, just for the knowledge. I'm not in the university yet :(
    – Delta
    Nov 1, 2010 at 10:24
  • 5
    if you're interested in this sort of thing, check out a book called Hacker's Delight
    – jasper
    Nov 1, 2010 at 10:56
  • Make sure you have read Structured Computer Organization from Tanenbaum. This is a damn good book which starts with a lot of low-level stuff like that and goes up the stack afterwards.
    – elmattic
    Nov 1, 2010 at 12:00

8 Answers 8

79

Here is an example for your amusement

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

The loop could be unrolled. Number of times it executes, depends on the number of bits set in operands, but it's never greater than the width of unsigned int. Once carry becomes 0, next iterations don't change anything.

4
  • 3
    Thank you. That's what I was looking for. Now I'm gonna try to understand why this works. ty
    – Delta
    Nov 1, 2010 at 14:35
  • 1
    Can anyone produce a concise proof why a version without a loop or recursion isn't possible for arbitrary representation size?
    – nietaki
    Mar 31, 2013 at 14:38
  • I will point out that this should work in modern Fortran as well, since there is no unsigned integer type. One can simply use a normal integer and this procedure to guarantee unsigned integer addition modulo 2^w where w is the number of bits in your integer model. Usually integers are two's compliment in Fortran, so the bits will represent unsigned integers but if you print the value of your integer it will interpret the bits as a signed two's compliment integer. If you want to use large integers and verify that your addition works & is modulo 2^w be careful interpreting the results.
    – zbeekman
    May 23, 2013 at 19:05
  • @nietaki: Consider the case of N ones on one hand and a single one bit on the other hand. Every time you loop once, the carry moves one bit to the left. You have to loop at least N times to get the carry to move all the way to the left to overflow either into the next bit or into the resultant carry bit.
    – dascandy
    Jul 17, 2014 at 11:42
30

Try this:

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

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

Edit: Corrected if statement

4
  • 2
    Do we need the if statement here, when b = 0, a^b = a and thus the result stays the same .
    – Anirudh
    Mar 10, 2016 at 2:37
  • 6
    @Anirudh, yes. You need that base case to end the recursion. Aug 20, 2016 at 0:33
  • How about changing if statement to if ((a & b) == 0) return (a ^ b);? This will slash one extra recursive call.
    – rootkea
    Mar 15, 2022 at 6:05
  • Could you explain how this handles signed integers? I get- 1. find carry for all the bits 2. create a number by adding all the bits which have a 0/1 combination 3. shift carry left and add it to (2) May 22, 2022 at 0:51
8

Think about how addition happens bit by bit. Shift the values to get each bit of each operand in turn, then look at the four possible values for the two bits and work out what the result bit should be and whether there's a carry bit to worry about. Then see how the result and carry can be caculated using the bitwise ops.

6
static int binaryadd(int x, int y)
{
  while (x != 0)
  {
    int c = y & x;
    y = y ^ x; 
    x = c << 1;             
  }
  return y;
}
4
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;
}

Taking 32 bit as int takes 32 bit. Thanks!!!

2
  • 15
    i++ is that not addition? ;) Feb 1, 2014 at 1:55
  • not happy for negative numbers but so readable
    – user501743
    Apr 23, 2022 at 7:16
0
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;
}

Sum of two bits can be performed using the XOR ^ operator and carry bit can be obtained by using AND & operator. Provided a and b don't have set bits at the same position, then using ^ operator gives the sum of a and b.

Comments from geeksforgeeks

0
public int getSum(int a, int b) {
    while(b!=0){
        int temp=a;
        a=a^b;
        b=(temp&b)<<1;
    }
    return a;
}
-7
        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 ");
        }
1
  • 5
    -1 code provided is just "int c = b | e" which is OR, not ADD. The rest of code is just bad example of converting int to binary string.
    – peenut
    Aug 20, 2013 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.