C:256 位整数的幂运算

Question

我正在处理一个对无符号 256 位整数进行运算的算法，我需要编写一个函数来计算给定公式的值

uint256 compute(uint16 x) {
    return floor(exp2(x / 256)) - 1;
}

我们可以看到方程保留了变量边界( compute(0) == 0 ， compute(65535) == 1<<255 )。除法应被视为有理数除法，而不是整数。

所提出的语法是伪 C，但我正在寻找一种可以在其他语言中使用的通用算法方法。

非常感谢您的帮助和时间。

Answer 1

您可以预先计算 x 函数的所有 256 位值并将其制成表格在[65280, 65535] (即 255 x 256 + i )；您将通过参数的 8 个最低有效位来查找表。这将需要 8KB 的存储空间。

对于参数的较低值，请将表格值右移 255 - (x >> 8) .

如果您想要纯粹的速度并且能够承受 64KB 的存储空间，则可以预先计算 0 到 7 的移位，并通过使用正确的字节偏移进行复制来执行更大的移位。

或者，您可以考虑指数的 CORDIC 方法，但我认为它不会更快或需要更少的存储空间。