4 ms·
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
by ggrrhh_ta 4y ago
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.
- kleiba 4y agoThat'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).