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, Nov 01 '10 at 10:23
Nothing special, just for the knowledge. I'm not in the university yet :( — Delta, Nov 01 '10 at 10:24
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 01 '10 at 12:00
if you're interested in this sort of thing, check out a book called [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, Nov 01 '10 at 10:56
This is a great question for [quantum computing](https://lvwarren.blogspot.com/2019/01/computing-and-future-8-thoughts-on.html). — vwvan, Jan 20 '19 at 06:32

Maciej Hehl · Accepted Answer · 2010-11-01T18:36:40.237

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.

edited Nov 01 '10 at 18:36

answered Nov 01 '10 at 12:39

Maciej Hehl

7,895
1
22
23

3

Thank you. That's what I was looking for. Now I'm gonna try to understand why this works. ty – Delta Nov 01 '10 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 '13 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 '13 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 '14 at 11:42

score 30 · Answer 2 · edited Oct 14 '15 at 00:14

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

edited Oct 14 '15 at 00:14

CodeArtist

5,534
8
40
65

answered Nov 20 '14 at 01:19

Shatazone

2,422
6
28
38

2

Do we need the if statement here, when b = 0, a^b = a and thus the result stays the same . – Anirudh Mar 10 '16 at 02:37
6

@Anirudh, yes. You need that base case to end the recursion. – lastoneisbearfood Aug 20 '16 at 00:33
How about changing `if` statement to `if ((a & b) == 0) return (a ^ b);`? This will slash one extra recursive call. – rootkea Mar 15 '22 at 06: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) – Nishit Mengar May 22 '22 at 00:51

score 8 · Answer 3 · answered Nov 01 '10 at 10:47

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.

score 6 · Answer 4 · edited Oct 18 '17 at 16:52

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 '17 at 16:52

Jared Burrows

54,294
25
151
185

answered Oct 08 '14 at 12:02

dragonfly02

3,403
32
55

score 4 · Answer 5 · answered Mar 16 '13 at 12:13

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 '13 at 12:13

Trying

14,004
9
70
110

15

`i++` is that not addition? ;) – Qantas 94 Heavy Feb 01 '14 at 01:55
not happy for negative numbers but so readable – user501743 Apr 23 '22 at 07:16

codejockie · Answer 6 · 2018-07-05T11:36:18.770

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

score 0 · Answer 7 · answered Sep 25 '22 at 08:20

0

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 '22 at 08:20

lbndvs

61
9

score -7 · Answer 8 · answered Aug 13 '11 at 07:02

        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 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 '13 at 17:28

Add two integers using only bitwise operators?

8 Answers8

Linked

Related