将跨越多个无符号长整型表示的两个二进制数相加的高效算法

Question

我想在这个特定的框架中对两个二进制数求和，我将参考C++的编码语法。 64 个二进制数被编码为无符号 long long int 向量。

vector<unsigned long long int> a;

其中 v[j] 的第 i 位等于第 i 个数的第 j 位，i = 0, ..., 64-1。

现在让我们考虑两个 64 位数字的集合

vector<unsigned long long int> a, b;

我想通过按位运算，将a中编码的64个数字与b中编码的64个数字一次性求和。例如，我想将a中编码的第0个数字与b中编码的第0个数字相加，将a中编码的第1个数字与b中编码的第1个数字相加，等等，然后写入结果变成一个

vector<unsigned long long int> c;

最快的方法是什么？我似乎记得必须使用二叉树结构，但我不确定。

Answer 1

添加一对转置整数（每个逻辑整数物理存储在位矩阵的列中）可以像这样完成：

#include <cstdint>
#include <vector>
#include <cstddef>

using std::uint64_t;
using std::size_t;

std::vector<uint64_t> add_transposed_integers(
    const std::vector<uint64_t> &a,
    const std::vector<uint64_t> &b)
{
    size_t n = a.size();
    std::vector<uint64_t> c(n);

    uint64_t carry = 0;
    for (size_t i = 0; i < n; i++) {
        uint64_t sum = (a[i] ^ b[i]) ^ carry;
        carry = (a[i] & b[i]) | (carry & (a[i] ^ b[i]));
        c[i] = sum;
    }

    return c;
}

这里的按位逻辑只是纹波进位加法。

我假设

a

、

b

和

c

都应该具有相同的位数（这意味着：它们的向量都具有相同的长度）。如果不是这样，您可以轻松地进行一些修改。

我并不认为这是最快的方法，但让它更快并不容易。例如，您可能会考虑 SIMD，但进位传播确实很奇怪，您需要一些更高级的加法算法，例如 Kogge-Stone，它可以支持一些并行性，但总共会花费更多的操作。