查找 table 以计算整数中设置位的数量

Question

正在尝试解决这个热门面试问题 - http://www.careercup.com/question?id=3406682

我掌握了 2 种方法 -

Brian Kernighan 的算法 - Bits counting algorithm (Brian Kernighan) in an integer time complexity
查找table。

我假设当人们说使用查找 table 时，他们指的是一个以 Integer 作为键、设置位数作为值的 Hashmap。

如何构造此查找 table？我们是否使用 Brian 算法在第一次遇到整数时计算位数，将其放入 hashtable，下次遇到该整数时，从 hashtable 中检索值？

PS：我知道硬件和软件 api 可用于执行 popcount (Integer.bitCount())，但在这个面试问题的上下文中，我们是不允许使用那些方法。

Answer 1

整数可以直接用于索引数组；例如所以你只有一个简单的无符号 8 位整数数组，其中包含 0x0001、0x0002、0x0003 的设置位计数...并按 array[number_to_test].

进行查找

您不需要实现哈希函数来将 16 位整数映射到您可以订购的东西，这样您就可以拥有查找功能！

Answer 2

回答有关如何计算此 table 的问题：

int table[256]; /* For 8 bit lookup */
for (int i=0; i<256; i++) {
    table[i] = table[i/2] + (i&1);
}

在给定整数的每个字节上查找此 table 并对获得的值求和。

Answer 3

我到处寻找答案，但没有得到满意的解释。

让我们从了解左移的概念开始。当我们向左移动一个数字时，我们 将数字乘以 2，向右移动会将其除以 2。

例如，如果我们想从数字 10(01010) 生成数字 20(二进制 10100)，那么我们必须将数字 10 向左移动一位。我们可以看到 10 和 20 中的设置位数相同，除了 20 中的位数与数字 10 相比向左移动了一个位置。因此从这里我们可以得出结论，数字 n 中的设置位数是与n/2中的设置位数相同（如果n为偶数）。

在奇数的情况下，如 21(10101)，除最后一位外，所有位都与数字 20 相同，在 21 的情况下，最后一位将设置为 1，从而导致奇数有额外的一组位。

让我们概括一下这个公式

number of set bits in n is number of set bits in n/2 if n is even
number of set bits in n is number of set bit in n/2 + 1 if n is odd (as in case of odd number last bit is set.

更通用的公式是：

BitsSetTable256[i] = (i & 1) +  BitsSetTable256[i / 2];

其中 BitsetTable256 是 table 我们正在构建的位计数。对于基本情况，我们可以设置 BitsetTable256[0] = 0； table 的其余部分可以使用上述公式以自下而上的方式计算。

查找 table 以计算整数中设置位的数量

Lookup table for counting number of set bits in an Integer

hashmap

lookup-tables

bit