HAKMEM汉明重磅有一个bug，有办法救它吗？

Question

;if A is a 9 bit quantity, B gets number of 1's (Schroeppel)
  IMUL A,[1001001001] ;4 copies
  AND A,[42104210421] ;every 4th bit
  IDIVI A,17 ;casting out 15.'s in hexadecimal

这个函数似乎需要一个33位来计算32s位置的位。

uint32_t i = 0b11101011;
uint32_t u = i * (uint32_t)01001001001;
uint32_t x = u & (uint32_t)042104210421;
v = x % 017;
std::cout << "i: " << std::bitset<8>(i) << ", u: " << std::bitset<32>(u) <<
", x: " << std::bitset<32>(x) << ", v: " << v << std::endl;

给予：

i: 11101011
u: 01011011101011011101011011101011
x: 00010001000000010001000000000001
v: 5

但是：

uint64_t v = i;
uint64_t u = v * (uint64_t)01001001001;
uint64_t x = u & (uint64_t)042104210421;
v = x % 017;
std::cout << "i: " << std::bitset<8>(i) << ", u: " << std::bitset<33>(u) <<
", x: " << std::bitset<33>(x) << ", v: " << v << std::endl;

给予：

i: 11101011
u: 101011011101011011101011011101011
x: 100010001000000010001000000000001
v: 6

由于绝对指令的数量非常少(尽管idiv函数很昂贵，在我的用例中最重要的是指令的计数)，所以我想使用这个或类似的函数。但我不太明白模数15是如何工作的。

我只需要数到7位(虽然8位才是理想的)。修复这个函数的最佳方法是什么？

Answer 1

在下面，我假设8位a。最初的HAKMEM代码很可能是为一个36位字的机器设计的，在其创建时很常见。

问题是，代码as-is错过了a的bit 5的积累，后者映射到产品的bit 32，这在32位机器中无法表示。同时，该产品的第8位未使用。因此，我们可以隔离a的第5位，并将其移动到产品的第8位。然后掩盖每一次咀嚼中的最低位数，然后用乘法对咬数进行求和，这样，总和就会在最高的咬口处结束。生成的C代码如下所示。

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int reference_popc (uint32_t a)
{
    int res = 0;
    while (a) {
        a &= a - 1;
        res++;
    }
    return res;
}

// based on HAKMEM item 167
int hakmem_popc_byte (uint8_t a)
{
    int r;
    r = (((((uint32_t)a * 01001001001) | ((a & 0x20) << 3)) & 0x11111111) * 0x11111111) >> 28;
    return r;
}

int main (void)
{
    uint8_t a = 0;
    do {
        if (hakmem_popc_byte(a) != reference_popc (a)) {
            printf ("error @ %08x: res=%d  ref=%d\n", 
                    a, hakmem_popc_byte(a), reference_popc (a));
            return EXIT_FAILURE;
        }
        a = a + 1;
    } while (a);
    return EXIT_SUCCESS;
}

在进一步研究了初始乘法产生的位模式之后，我观察到我们可以做得比上面的快速修复更好。初始乘法将位8、17和26设置为零。为了避免在通过掩蔽选择第四个位时碰到任何这些，我们可以使用掩码0x88888888。然而，这需要向下移动提取的数据，以避免溢出在最重要的吞吐过程中的总和。由此产生的代码是：

// based on HAKMEM item 167
int hakmem_popc_byte (uint8_t a)
{
    int r;
    r = (((((uint32_t)a * 01001001001) & 0x88888888) >> 3) * 0x11111111) >> 28;
    return r;
}