Add two integers using only bitwise operators?

c# bit-manipulation
Delta picture Delta · Nov 1, 2010 · Viewed 62k times · Source

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

Answer

Maciej Hehl picture Maciej Hehl · Nov 1, 2010

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.

Related questions

C# int to byte[]

I need to convert an int to a byte[] one way of doing it is to use BitConverter.GetBytes(). But im unsure if that matches the following specification: An XDR signed integer is a 32-bit datum that encodes an integer …

Read More
Most common C# bitwise operations on enums

For the life of me, I can't remember how to set, delete, toggle or test a bit in a bitfield. Either I'm unsure or I mix them up because I rarely need these. So a "bit-cheat-sheet" would be nice to …

Read More
Checking if a bit is set or not

How to check if a certain bit in a byte is set? bool IsBitSet(Byte b,byte nPos) { return .....; }

Read More