按时间复杂度 O(1) C++ 代码计算 Byte 中 1 的位数

Question

我搜索了一种算法，该算法通过 O(1) 的时间复杂度以及我在谷歌中找到的内容来计算 Byte 中的个数：

// C++ implementation of the approach  
#include <bits/stdc++.h> 
using namespace std; 
  
int BitsSetTable256[256]; 
  
// Function to initialise the lookup table  
void initialize()  
{  
  
    // To initially generate the  
    // table algorithmically  
    BitsSetTable256[0] = 0;  
    for (int i = 0; i < 256; i++) 
    {  
        BitsSetTable256[i] = (i & 1) +  
        BitsSetTable256[i / 2];  
    }  
}  
  
// Function to return the count  
// of set bits in n  
int countSetBits(int n)  
{  
    return (BitsSetTable256[n & 0xff] +  
            BitsSetTable256[(n >> 8) & 0xff] +  
            BitsSetTable256[(n >> 16) & 0xff] +  
            BitsSetTable256[n >> 24]);  
}  
  
// Driver code  
int main()  
{  
    // Initialise the lookup table  
    initialize();  
    int n = 9;  
    cout << countSetBits(n); 
}  
  

我明白我需要 256 大小的数组（换句话说，查找表的大小）从 0 到 255 的索引，它们都是 Byte 表示的小数值！

但是在函数 initialize 我不明白 for 循环中的术语：BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
为什么我这样做？！我不明白 for 循环中此行代码的目的是什么。

此外，在函数 countSetBits 中，该函数返回：

 return (BitsSetTable256[n & 0xff] +  
            BitsSetTable256[(n >> 8) & 0xff] +  
            BitsSetTable256[(n >> 16) & 0xff] +  
            BitsSetTable256[n >> 24]); 

我完全不明白我在做什么和 0xff 按位以及为什么我做右移.. 请有人向我解释这个概念吗？！我完全不明白为什么在 BitsSetTable256[n >> 24] 的函数 countSetBits 中我们没有做到 0xff 明智？

我明白为什么我需要大小为 2^8 的查找表，但是我上面提到的其他代码行不明白，谁能用简单的话向我解释一下？以及计算 Byte 中的个数的目的是什么？

非常感谢你们！

Answer 1

关于问题的第一部分：

// Function to initialise the lookup table  
void initialize()  
{  
  
    // To initially generate the  
    // table algorithmically  
    BitsSetTable256[0] = 0;  
    for (int i = 0; i < 256; i++) 
    {  
        BitsSetTable256[i] = (i & 1) +  
        BitsSetTable256[i / 2];  
    }  
}  

这是一种简洁的递归。（请注意，我的意思不是“递归函数”，而是更数学意义上的递归。）

种子是 BitsSetTable256[0] = 0;

然后使用（已经存在的）结果初始化每个元素，i / 2并为此添加 1 或 0。从而，

• 如果索引的最后一位为 1，则加i1
• 如果索引的最后一位为 0，则添加i0。

要获得 的最后一位的值i，i & 1是通常的 C/C++ 位掩码技巧。

为什么BitsSetTable256[i / 2]要建立在价值的结果之上？的结果BitsSetTable256[i / 2]是i排除最后一位的所有位的数量。

请注意，i / 2和i >> 1（值（或位）右移 1 从而删除最小/最后一位）是等效表达式（对于相应范围内的正数 - 排除边缘情况）。

关于问题的另一部分：

    return (BitsSetTable256[n & 0xff] +  
            BitsSetTable256[(n >> 8) & 0xff] +  
            BitsSetTable256[(n >> 16) & 0xff] +  
            BitsSetTable256[n >> 24]);

• n & 0xff 屏蔽掉高位，隔离低 8 位。
• (n >> 8) & 0xff将n8 位的值右移（从而丢弃 8 位最少的位），然后再次屏蔽隔离低 8 位的高位。
• (n >> 16) & 0xff将n16 位的值右移（从而丢弃 16 位最少的位），然后再次屏蔽隔离低 8 位的高位。
• (n >> 24) & 0xff将n24 位的值右移（从而丢弃 24 位最少的位），这应该有效地使高 8 位成为低 8 位。

假设int和unsigned具有通常在时下通用平台这包括所有位的32位n。

请注意，负值的右移是实现定义的。

（我肯定记得按位移位运算符。）

因此，负值的右移可能会用 1 填充所有高位。
可以打破BitsSetTable256[n >> 24]导致(n >> 24) > 256
，因此BitsSetTable256[n >> 24]一个出绑定访问。

更好的解决方案是：

    return (BitsSetTable256[n & 0xff] +  
            BitsSetTable256[(n >> 8) & 0xff] +  
            BitsSetTable256[(n >> 16) & 0xff] +  
            BitsSetTable256[(n >> 24) & 0xff]);

Answer 2

中的代码countSetBits采用 anint作为参数；显然假定为 32 位。那里的实现是n通过移位和掩码从中提取四个单字节；对于这四个单独的字节，使用查找并添加每个字节的位数以产生结果。

查找表的初始化有点棘手，可以看作是动态规划的一种形式。条目按参数的递增索引填充。第一个表达式屏蔽掉最低有效位并对其进行计数；第二个表达式将参数减半（也可以通过移位来完成）。由此产生的参数较小；然后正确地假设较小参数的必要值已经在查找表中可用。

对于查找表的访问，请考虑以下示例：

input value (contains 5 ones):
01010000 00000010 00000100 00010000

input value, shifting is not necessary
masked with 0xff (11111111)
00000000 00000000 00000000 00010000     (contains 1 one)

input value shifted by 8
00000000 01010000 00000010 00000100
and masked with 0xff (11111111)
00000000 00000000 00000000 00000100     (contains 1 one)

input value shifted by 16
00000000 00000000 01010000 00000010
and masked with 0xff (11111111)
00000000 00000000 00000000 00000010     (contains 1 one)

input value shifted by 24,
masking is not necessary
00000000 00000000 00000000 01010000     (contains 2 ones)

提取的值仅设置了最低 8 位，这意味着相应的条目在查找表中可用。查找表中的条目已添加。基本思想是参数中 1 的数量可以按字节计算（事实上，位串中的任何分区都是合适的）。