Hacker News Reader

Comment by marginalia_nu | Hacker News Reader

How do you derive the identities mentioned at the bottom of the post?

The first one is already explained, a^b + 2*(a&b) is computing the sum and carry in parallel, and then adding them up.

The second formula is more elaborate, and makes heavy use of the above identity:

      2*(a|b)-(a^b)
    = 2*((a&b)^a^b)-(a^b) (express boolean or in terms of and and xor)
    = 2*(a&b) ^ 2*(a^b) - (a^b)
    = 2*(a&b) + 2*(a^b) - (a^b) (there can't be carries, so xor equals addition in this case)
    = 2*(a^b) + 4*(a&b) - 2*(a&b) - (a^b)
    = 2*((a^b) + 2*(a&b)) - 2*(a&b) - (a^b)
    = 2*(a+b) - (a+b)
    = a+b.

The first one is just the binary sum without carry (x xor y) and then adding the carries of that sum (x&y) shifted by 1 bit (2*(x&y)), still the addition of the carries can in turn produce carries, but that is taken care of by the normal "+" which is addition with carry.

That's correct, and here's a further illustration.

Consider adding two single bits, X and Y - you'll get the following sums, denoted in binary (column CM):

    X Y | CM
    ----+---
    0 0 | 00
    0 1 | 01
    1 0 | 01
    1 1 | 10

As you'll note, the M-bit is just XOR and the C-bit is AND (google "half-adder" if you're into hardware).

And as we remember from school, the carry (C-bit) always has to be added to the next column to the left, that's why we shift it by one bit (aka multiplication by 2).

I believe these follow from the definition of twos complement addition. Times 2 is just a left shift. So it's like a carry bit.

Reply on news.ycombinator.com