Add two integers using only bitwise operators?

Question

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

According to him self, he just wants to understand the logic behind adding binary numbers. — Jesper Fyhr Knudsen
– Jesper Fyhr Knudsen, Commented Nov 1, 2010 at 10:23
Nothing special, just for the knowledge. I'm not in the university yet :( — Delta
– Delta, Commented Nov 1, 2010 at 10:24
if you're interested in this sort of thing, check out a book called Hacker's Delight — jasper
– jasper, Commented 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
– elmattic, Commented Nov 1, 2010 at 12:00

Maciej Hehl · Accepted Answer · 2010-11-01 18:36:40Z

84

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.

edited Nov 1, 2010 at 18:36

answered Nov 1, 2010 at 12:39

Maciej Hehl

7,9851 gold badge26 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Delta Over a year ago

Thank you. That's what I was looking for. Now I'm gonna try to understand why this works. ty

nietaki Over a year ago

Can anyone produce a concise proof why a version without a loop or recursion isn't possible for arbitrary representation size?

zbeekman Over a year ago

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.

dascandy Over a year ago

@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.

CodeArtist · Accepted Answer · 2015-10-14 00:14:24Z

31

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

edited Oct 14, 2015 at 0:14

CodeArtist

5,7068 gold badges46 silver badges66 bronze badges

answered Nov 20, 2014 at 1:19

Shatazone

2,5126 gold badges30 silver badges40 bronze badges

4 Comments

Anirudh Over a year ago

Do we need the if statement here, when b = 0, a^b = a and thus the result stays the same .

lastoneisbearfood Over a year ago

@Anirudh, yes. You need that base case to end the recursion.

rootkea Over a year ago

How about changing if statement to if ((a & b) == 0) return (a ^ b);? This will slash one extra recursive call.

Nishit Mengar Over a year ago

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)

The Archetypal Paul · Accepted Answer · 2010-11-01 10:47:33Z

9

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.

answered Nov 1, 2010 at 10:47

The Archetypal Paul

41.9k20 gold badges107 silver badges136 bronze badges

Comments

Jared Burrows · Accepted Answer · 2017-10-18 16:52:09Z

6

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

edited Oct 18, 2017 at 16:52

Jared Burrows

55.9k26 gold badges160 silver badges190 bronze badges

answered Oct 8, 2014 at 12:02

dragonfly02

3,7293 gold badges41 silver badges63 bronze badges

Comments

Trying · Accepted Answer · 2013-03-16 12:13:20Z

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!!!

answered Mar 16, 2013 at 12:13

Trying

14.3k11 gold badges72 silver badges113 bronze badges

2 Comments

Qantas 94 Heavy Over a year ago

i++ is that not addition? ;)

user501743 Over a year ago

not happy for negative numbers but so readable

codejockie · Accepted Answer · 2018-07-05 11:36:18Z

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

lbndvs · Accepted Answer · 2022-09-25 08:20:03Z

1

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

answered Sep 25, 2022 at 8:20

lbndvs

8110 bronze badges

Comments

naresh · Accepted Answer · 2011-08-13 07:02:11Z

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

answered Aug 13, 2011 at 7:02

naresh

11 bronze badge

1 Comment

peenut Over a year ago

-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.

Collectives™ on Stack Overflow

Add two integers using only bitwise operators?

8 Answers 8

4 Comments

4 Comments

Comments

Comments

2 Comments

Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

8 Answers 8

4 Comments

4 Comments

Comments

Comments

2 Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related