乘以 66049 如何重复位？

Question

这是提高精度的像素混合操作的一部分。

typedef unsigned uint;

uint h(uint x) {
    x &= 0xff;
    return x << 8 | x;
}

uint g(uint x, uint y) {
    return h(x) * h(y) >> 24;
}

我查看了编译器的输出，发现了一行非常有趣的内容。

g:
        movzx   edi, dil
        movzx   esi, sil
        imul    esi, edi
        imul    eax, esi, 66049  # <---
        shr     eax, 24
        ret

这可以反编译为，

uint g_(uint x, uint y) {
    return (x & 0xff) * (y & 0xff) * 66049 >> 24;
}

我无法理解乘以66049如何产生所需的结果。它背后的数学原理是什么？

Answer 1

66049 是十六进制的 0x10201。这是一个重要的线索，因为：

\n

(x << 8 | x) = (x * 0x101)\n

\n

（假设 0 \xe2\x89\xa4 x \xe2\x89\xa4 0xFF），则(x << 8 | x) * (y << 8 | y)与 相同x * y * 0x101 * 0x101。

\n

0x101 * 0x101可以简化为-这0x10201就是你的魔法常数。

\n

那么为什么与x * 0x101相同呢(x << 8 | x)？通过十进制示例应该很容易看出这一点。如果将 0-99 中的任何数字乘以 101，则会重复数字 - 例如，32 * 101 = 3232。这是因为乘以 100 实际上只是在末尾添加 0（即 32 * 100 = 3200）和额外的 1只需添加原始值 (32 * 101 = 32 * 100 + 32 * 1 = 3200 + 32 = 3232)。同样的原理也适用于十六进制（或二进制）。

\n