Search code examples
c++mathbit-manipulationalu

Binary addition carrying from left to right

How would you efficiently implement 64 bit binary addition carrying from left to right? Like flipping the bits then adding:

0101 + 1110 = BitReverse(1010 + 0111)
            = BitReverse(10001)
            = 10001

My current solution is to reverse the bit order of the inputs using delta swaps (and possibly a byteswap intrinsic), use normal addition, then reverse again, which is not particularly fast, but probably better than looping for 64-bit integers. (I haven't tested it but it would still be too slow.)

uint64_t addreverse(uint64_t a, uint64_t b) {
    return BitReverse(BitReverse(a) + BitReverse(b));
}

This is quite slow, as the bits need to be reversed three times, requiring over 40 operations when using byteswap.

EDIT: I cannot store them reversed as I require regular addition as well.

Solution

  • Emulating a Kogge-Stone adder, with the shift direction reversed, gives a nice algorithm,

    uint64_t p = x ^ y;
uint64_t g = x & y;

g |= p & (g >> 1);
p &= p >> 1;

g |= p & (g >> 2);
p &= p >> 2;

g |= p & (g >> 4);
p &= p >> 4;

g |= p & (g >> 8);
p &= p >> 8;

g |= p & (g >> 16);
p &= p >> 16;

g |= p & (g >> 32);

uint64_t result = x ^ y ^ (g >> 1);