hashmap - 用于计算整数中设置位数的查找表

Question

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

我可以掌握两种方法 -

1. Brian Kernighan 的算法 - Bits counting algorithm (Brian Kernighan) in an integer time complexity

2. 查找表。

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

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

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

Answer 1

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

让我们首先了解左移的概念。当我们向左移动一个数字时，我们将该数字乘以 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 是我们为位计数构建的表。对于基本情况，我们可以设置 BitsetTable256[0] = 0；表格的其余部分可以使用上述公式以自下而上的方式计算。