c - 计算任意大二进制数之和的最快方法是什么

Question

我似乎找不到任何关于这方面的好文献。具有这样的 BigBinaryNumber(带虚拟符号位的二进制补码)结构:

typedef unsigned char byte;
enum Sign {NEGATIVE = (-1), ZERO = 0, POSITIVE = 1};
typedef enum Sign Sign;
struct BigBinaryNumber
{
    byte *number;
    Sign signum;
    unsigned int size;
};
typedef struct BigBinaryNumber BigBinaryNumber;

我可以采用小学方法(即对单个字节求和并使用进位进行后续求和)或者使用固定大小的查找表。

关于最快的二进制求和方法有什么好的文献吗？

Answer 1

添加数字的最快方法是处理器现有的 add 指令。只要你在内存中合理地布置了数字(例如，你没有向后的位顺序或任何东西)，从每个数字一次加载 32 位应该非常简单，本地将它们加在一起，并得到进位:

uint32_t *word_1 = &number1.number + offset, *word_2 = &number2.number + offset;
uint32_t *word_tgt = &dest.number + offset;
uint64_t sum = *word_1 + *word_2 + carry; // note the type!
*word_tgt = (uint32_t) sum; // truncate
carry = sum >> 32;

请注意，您可能需要添加一些特殊情况来处理数字中的最后一个字节(或确保 *number 始终分配 4 个字节的倍数)。

如果您使用的是 64 位 CPU，您可以扩展它以使用 uint64_t。但是，没有用于溢出的 uint128_t，因此您可能不得不使用一些技巧来获取进位位。