CODEWITHSUNDEEP
c#algorithmbit-manipulation
user3175088
user3175088

Reputation:

Add two numbers using bit manipulation

I'm working on the following practice problem from GeeksForGeeks:

Write a function Add() that returns sum of two integers. The function should not use any of the arithmetic operators (+, ++, –, -, .. etc).

The given solution in C# is:

public static int Add(int x, int y)
{
    // Iterate till there is no carry  
    while (y != 0)
    {
        // carry now contains common set bits of x and y
        int carry = x & y;

        // Sum of bits of x and y where at least one of the bits is not set
        x = x ^ y;

        // Carry is shifted by one so that adding it to x gives the required sum
        y = carry << 1;
    }
    return x;
}

Looking at this solution, I understand how it is happening; I can follow along with the debugger and anticipate the value changes before they come. But after walking through it several times, I still don't understand WHY it is happening. If this was to come up in an interview, I would have to rely on memory to solve it, not actual understanding of how the algorithm works.

Could someone help explain why we use certain operators at certain points and what those totals are suppose to represent? I know there are already comments in the code, but I'm obviously missing something...

Upvotes: 6

Views: 1859

Answers (3)

Prune
Prune

Reputation: 77837

At each iteration, you have these steps:

carry <- x & y   // mark every location where the addition has a carry
x <- x ^ y       // sum without carries
y <- carry << 1  // shift the carry left one column

On the next iteration, x holds the entire sum except for the carry bits, which are in y. These carries are properly bumped one column to the left, just as if you were doing the addition on paper. Continue doing this until there are no more carry bits to worry about.

Very briefly, this does the addition much as you or I would do it on paper, except that, instead of working right to left, it does all the bits in parallel.

Upvotes: 7

user555045
user555045

Reputation: 64904

Decimal arithmetic is more complicated than binary arithmetic, but perhaps it helps to compare them.

The algorithm that is usually taught for addition is to go through the digits one by one, remembering to "carry a one" when necessary. In the above algorithm, that is not exactly what happens - rather, all digits are added and allowed to wrap, and all the carries are collected to be applied all at once in the next step. In decimal that would look like this:

123456
777777
------ +
890123
001111 << 1
011110
------ +
801233
010000 << 1
100000
------ +
901233
000000 done

In binary arithmetic, addition without carry is just XOR.

Upvotes: 4

Christopher
Christopher

Reputation: 9804

What you have here is a case of Binary Math on the Represenetation in memory: https://www.wikihow.com/Add-Binary-Numbers

Generally when programming in C#, you do not bother with the "how is it represented in memory" level of things. 55% of the time it is not worth the effort, 40% it is worse then just using the builtin functions. And the remaing 5% you should ask yourself why you are not programming in Native C++, Assembler or something with similar low level capacities to begin with.

Upvotes: 0

Related Questions