字节中设置位的模式

Question

Joel 在他的文章中提到，计算一个字节中设置位的数量是一个编程问题。 面试游击指南, ，并讨论了一种利用查找表中出现的模式的方法。在我发现这种模式后不久，我写了一篇关于它的文章。

总结一下：

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

基于罗伯特的代码 这里, ，甚至可以在没有除法或模数的情况下完成，用一个移位和一个 AND 替换它们，如下所示：

a = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]
x = 243 >> 4 # 15 (same as dividing by 16)
y = 243 & 0x0f # 3 ( same as modding by 16)

result = a[x] + a[y] # 6 bits set 

或者在C中：

const unsigned char oneBits[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};

unsigned char CountOnes(unsigned char x)
{
    unsigned char results;
    results = oneBits[x&0x0f];
    results += oneBits[x>>4];
    return results
}

对于任何大小的整数，您可以循环遍历字节并进行快速查找，如下所示：

def bits(n)
    a = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]
    a[n >> 4] + a[n & 0x0f]
end

def setBits(n)
   total = 0
   while(n > 0)
       total += bits(n&0xff)
       n >>= 8
   end
   total
end

setBits(6432132132165432132132165436265465465653213213265465) # 78 bits set

我对这个答案很满意。我知道更复杂和四叉树式的东西不会有效，我只是认为这是一个不错的思想实验。

Answer 2

这是一个愚蠢的问题！在你计算使用的是16项表，而不是256设置的位数的第一个例子是没有什么神奇！所有你要做的就是在计数字节（第一个半字节）的前四位设置的位数，然后在第二个半字节，将两者结合在一起。 X / 16的第一半字节中，x％16是第二半字节。

如果你重复这个过程，现在你有一个查找表两位与你只是做了四次，一次一对。在极端情况下，你可以添加所有的位一起一个接一个，你会得到明显的答案。

一查找表的整点是避免加入。

Answer 3

请问帖子晚了，但我只是找到了挑战。我的$ 1.02（蛮力）

Private Sub Button1_Click(ByVal sender As System.Object, _
                          ByVal e As System.EventArgs) Handles Button1.Click

    For x As Integer = 0 To 255
        Debug.WriteLine(bitsOn2(CByte(x)) & " " & Convert.ToString(x, 2).PadLeft(8, "0"c))
    Next

End Sub

Private Function bitsOn(ByVal aByte As Byte) As Integer
    Dim aBit As Byte = 1
    For z As Integer = 0 To 7
        If (aByte >> z And aBit) = aBit Then bitsOn += 1
    Next
End Function

Dim aDict As New Dictionary(Of Integer, Integer)
Private Function bitsOn2(ByVal aByte As Byte) As Integer
    If aDict.Count = 0 Then 'init dictionary
        For x As Integer = 0 To 255
            aDict.Add(x, bitsOn(CByte(x)))
        Next
    End If
    Return aDict(aByte)
End Function