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

Question

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

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

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

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

这很慢，因为位需要反转 3 次，使用 byteswap 时需要 40 多次操作。

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

Answer 1

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