4 ms·
How do you derive the identities mentioned at the bottom of the post?
by marginalia_nu 4y ago
How do you derive the identities mentioned at the bottom of the post?
- deleted 4y ago[deleted]
- foota 4y agoI believe these follow from the definition of twos complement addition. Times 2 is just a left shift. So it's like a carry bit.
- ggrrhh_ta 4y agoThe 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).
- pbsd 4y agoThe 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.
- deleted 4y ago[deleted]