c++ - 二进制加法从左到右携带

您如何有效地实现从左到右的64位二进制加法？就像翻转位然后添加:

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

我当前的解决方案是使用增量交换(可能是byteswap固有的)来反转输入的位顺序，使用普通加法，然后再次反转，这不是特别快，但可能比循环64位整数更好。 (我还没有测试过，但是它仍然太慢了。)

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

这非常慢，因为需要将位反转三次，使用byteswap时需要进行40多次操作。

编辑:我不能将它们反向存储，因为我也需要定期添加。

最佳答案

模拟Kogge-Stone adder，将移位方向反向，给出了一种不错的算法，

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);