奇偶校验使用 "modulo"

Question

我 运行 进入这个，同时查找找到奇偶校验的算法，这被认为是有效的：

function usingModulo(v) {
    v ^= v >> 1
    v ^= v >> 2
    v = (v & 0x11111111) * 0x11111111
    return (v >> 28) & 1
}

有人可以解释一下这实际上是如何工作的吗？

Answer 1

v ^= v >> 1

之后v中的bit 2i是bit 2i和2i+1的奇偶校验。

v ^= v >> 2

之后v中的bit 4i就是bits 4i,4i+1,4i+2,4i+3的奇偶校验。

v = (v & 0x11111111) * 0x11111111

在此之后，v 的前 4 位包含旧 v 中位置 4i 的位的总和，特别是位置 28 的位将包含总和的最低有效位，这将是输入数字中所有位的奇偶性。

return (v >> 28) & 1

这将提取位置 28 的位（所有位的奇偶校验）。

更新

要详细解释第 3 步中的乘法，将乘法视为一系列移位和加法可能会有所帮助。

例如，要以 10 为底数将数字 x 乘以 111，您可以将 100x 和 10x 与 x 相加。

类似地，将 x 乘以 0x11111111 与将 x 移动 0,4,8,... 并将结果相加是相同的。

当考虑一系列移位和加法时，最高位将包含所有移位和加在一起的奇偶校验位可能更有意义。