puzzle - 字节中设置位的模式

Question

Joel 在他的 Guerrilla Guide to Interviewing 中提到计算一个字节中设置位的数量是一个编程问题。 ，并谈到了一种利用查找表中出现的模式的方法。在我发现这种模式后不久，我写了一篇关于它的文章。

总结一下:

Number of bits set in a byte in 16x16
0   1   1   2   1   2   2   3   1   2   2   3   2   3   3   4  
1   2   2   3   2   3   3   4   2   3   3   4   3   4   4   5  
1   2   2   3   2   3   3   4   2   3   3   4   3   4   4   5  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
1   2   2   3   2   3   3   4   2   3   3   4   3   4   4   5  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
3   4   4   5   4   5   5   6   4   5   5   6   5   6   6   7  
1   2   2   3   2   3   3   4   2   3   3   4   3   4   4   5  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
3   4   4   5   4   5   5   6   4   5   5   6   5   6   6   7  
2   3   3   4   3   4   4   5   3   4   4   5   4   5   5   6  
3   4   4   5   4   5   5   6   4   5   5   6   5   6   6   7  
3   4   4   5   4   5   5   6   4   5   5   6   5   6   6   7  
4   5   5   6   5   6   6   7   5   6   6   7   6   7   7   8  

第一行和第一列完全相同，网格中的每个位置都可以通过添加该位置的行和列中的第一个值来计算。因此，对于一个 8 位数字，您只需要一个包含 16 个条目的查找表，并且可以只使用前 16 个数字。然后，例如，如果您想计算数字 243 中的设置位，您只需执行以下操作:

a = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]
x = 243 / 16 => 15 # (int)
y = 243 % 16 => 3

a[x] + a[y] => 6

# Are there six bits set in the number 243?
243 = 11110011 # yep

之后我注意到的下一个模式是，每次将 NxN 网格的大小加倍时，每个象限都可以通过将 0、1、1 和 2 分别添加到每个象限来计算，如下所示:

# Make a 4x4 grid on the paper, and fill in the upper left quadrant with the values of the 2x2 grid.  
# For each quadrant, add the value from that same quadrant in the 2x2 grid to the array.  

# Upper left quad add 0 to each number from 2x2  
0   1   *   *  
1   2   *   *  
*   *   *   *  
*   *   *   *  

# Upper right quad add 1 to each number from 2×2  
0   1   1   2  
1   2   2   3  
*   *   *   *  
*   *   *   *  

# Lower left quad add 1 to each number from 2×2  
0   1   1   2  
1   2   2   3  
1   2   *   *  
2   3   *   *  

# Lower right quad add 2 to each number from 2×2  
0   1   1   2  
1   2   2   3  
1   2   2   3  
2   3   3   4  

再重复这个过程两次，你就会从上面得到 16x16 的网格，所以我想一定有某种四叉树算法可以让你从网格开始:

0 1
1 2

并给定一个数字 N，动态生成查找表并计算出位数。所以我的问题/挑战是， 你能找出一个算法来做到这一点吗？

Answer 1

这是一个愚蠢的问题!在第一个示例中，您使用 16 个条目的表而不是 256 个来计算设置的位数，这并不是什么神奇的事情!您所做的就是计算字节的前四位(第一个半字节)中设置的位数，然后在第二个半字节中将两者相加。 x/16 是第一个半字节，x%16 是第二个半字节。

如果你重复这个过程，现在你有一个两个位的查找表，你只需做四次，每对一次。在极端情况下，您可以将所有位一个一个地加在一起，您就会得到明显的答案。

查找表的重点是避免添加。