Bit-Twiddling 计算整数二进制中1的位数

所谓Bit-Twiddling,指的就是通过直接操作数据的字节来实现对数据的修改功能。有时候,它可以显著提高我们程序的运算效率。

我们通过下面这道编程题来给出Bit-Twiddling的运用场景:

给定正整数n,求出n的二进制表示中数位1出现的次数,例如:
输入n=5,即二进制n=101,输出2
输入n=11,即二进制n=1011,输出3

蛮力解法

对于上面的问题,最简单的解法就是:便利字符二进制中的每一个数位,如果当前数位是1,则给计数器加一。最后计数器的值则是数位1出现的次数。具体的代码如下:

int countOnes(unsigned int n)
{

int ones = 0; // 计数器
while (n > 0)
{
one += (1 & n); // 如果最低位为1,则将ones的值加一
n >>= 1; // 右移1位
}
return ones;
}

不难看出,上面的算法运行的次数仅仅和整数n的二进制位数有关,我们用N表示传入参数的大小,那么计算的复杂度可以表示为O(logN)

Bit-Twiddling 解法-1

在给出具体的代码之前,我们先来了解一个算式n &= (n - 1),这个算式就是Bit-Twiddling的其中一种,它的作用是清除正整数n最靠右的数字1,下面给出简单的证明:

对于任意正整数$n$,不妨设其最低(右)的数位$1$对应于$2^k$,那么$n$的二进制展开应该如下:
$$n = x x … x 1 0 0 … 0$$
其中数位$x$可能是0或1,而最低的$k+1$必然是$”100…0”$,即数位1后是$k$个0。所以我们可以有:
$$n - 1 = x x … x 0 1 1 … 1$$
从而,我们可以得到$n \& (n - 1)$的值:
$$n \& (n - 1) = x x … x 0 0 0 … 0$$
等效于将原n二进制展开中的最低位1转置为0。

现在我们可以通过n & (n - 1)这个式子来优化之前使用的蛮力解法了。

int countOnes(unsigned int n)
{

int ones = 0; // 计数器
while(n > 0)
{
ones += 1;
n &= n - 1; // 清除最低位的1
}
return ones;
}

上面算法的复杂度线性正比于数位1的实际数目。对于二进制数位为k的正整数n,蛮力解法在任意情况下都需要k次循环,而使用这里的解法,只有在最坏情况下需要进行k次循环(此时$n=2^{k}-1$),在最好的情况下只需要1次循环(此时$n=2^{k-1}$)。

我们用N表示传入参数的大小,那么计算的复杂度可以表示为O(logN)。从复杂度来看,两种算法并没有很大差别,这两个算法的最大差别在于logN之前的常数系数,在N足够随机的情况下,后一种算法的平均时间应该只有前一种算法的二分之一。

那么,是否这就是最优的解法呢?当然不是,我们仍然有优化的空间。

Bit-Twiddling 解法-2

我们可以考虑把二分法应用到当前的算法中,先参考一个简单的例子:计算二进制数字10110010的数位1出现的次数。使用二分法来思考,我们用Ones(10110010)来表示数位中出现的1的次数,那么有类似的结论:

Ones(10110010) = Ones(1011) + Ones(0010)
Ones(1011) = Ones(10) + Ones(11)
Ones(10) = Ones(1) + Ones(0) = 1 + 0 = 1

上面的计算涉及到多次加法,借助一些Bit-Twiddling技巧,我们可以将多个加法合并。

我们接下来一步一步解析其具体的步骤,为了简单起见,我们考虑8位长的整数,还是使用最开始的例子:n=10110010,我们可以将这个二进制数通过竖线|按照如下规则拆解:

n = 1|0|1|1|0|0|1|0

我们将n拆分为八个区间,每个区间有1位数。两个竖线|之间的数值就表示这个区间内数位1的计数。现在我们要做的就是将第2n - 1个区间的计数与第2n个计数相加,让后将结果保存至这两个区间合并后的空间。从左往右数,第一区间和第二区间分别是10,二者的和为1,第三个区间和第四个区间分别是11,二者的和为10,后面的区间以此类推。

我们可以用n = n & 01010101b + (n >> 1) & 01010101b来一次性完成八个区间的求和。得到下面的结果。

n = 01|10|00|01

上面的结果一共4个区间,每个区间2位数。各个区间的数表示初始状态正整数n中各个区间中的数位1的计数,即n的第一个区间(从左至右)一共有1个1,第二个到第四个区间分别有2,0,1个1

接下来,我们用n = n & 00110011b + (n >> 1) & 00110011b来一次性完成4个区间的求和运算,得到如下只含有2个区间的结果:

n = 0011|0001

表示n的高4位一共有3个1,低4位一共有1个1。接下来,使用n = n & 00001111b + (n >> 1) & 00001111b来将最后两个区间合并。得到:

n = 00000100

此时只有一个区间,表示这个8位数中含有的1的数,为4。

我们将这样的示例推导至32位整数的情况,可以参考如下代码:

#define POW(c) (1 << (c)) // 2^c
#define MASK(c) (((unsigned long) -1) / (POW(POW(c)) + 1)) //以2^c位为单位分组,相间地全0和全1
// MASK(0) = 55555555(h) = 01010101010101010101010101010101(b)
// MASK(1) = 33333333(h) = 00110011001100110011001100110011(b)
// MASK(2) = 0f0f0f0f(h) = 00001111000011110000111100001111(b)
// MASK(3) = 00ff00ff(h) = 00000000111111110000000011111111(b)
// MASK(4) = 0000ffff(h) = 00000000000000001111111111111111(b)

//输入:n的二进制展开中,以2^c位为单位分组,各组数值已经分别等于原先这2^c位中1的数目
#define ROUND(n, c) (((n) & MASK(c)) + ((n) >> POW(c) & MASK(c))) //运算优先级:先右移,再位与
//过程:以2^c位为单位分组,相邻的组两两捉对累加,累加值用原2^(c + 1)位就地记录
//输出:n的二进制展开中,以2^(c + 1)位为单位分组,各组数值已经分别等于原先这2^(c + 1)位中1的数目

int countOnes2 ( unsigned int n ) { //统计整数n的二进制展开中数位1的总数
n = ROUND ( n, 0 ); //以02位为单位分组,各组内前01位与后01位累加,得到原先这02位中1的数目
n = ROUND ( n, 1 ); //以04位为单位分组,各组内前02位与后02位累加,得到原先这04位中1的数目
n = ROUND ( n, 2 ); //以08位为单位分组,各组内前04位与后04位累加,得到原先这08位中1的数目
n = ROUND ( n, 3 ); //以16位为单位分组,各组内前08位与后08位累加,得到原先这16位中1的数目
n = ROUND ( n, 4 ); //以32位为单位分组,各组内前16位与后16位累加,得到原先这32位中1的数目
return n; //返回统计结果
} //32位字长时,O(log_2(32)) = O(5) = O(1)

上面的代码来自于《数据结构(C++语言版) 第三版 邓俊辉 编著》,代码链接

可见,若计算模型支持的整数字长为W,输入正整数为N,那么算法的复杂度为

T(N) = O(logW) = O(loglogN)

通常,loglogN可以被视作常数,比如就目前人类所能感知到整个宇宙而言,所有的基本粒子数约为 N = 10^81 = 2^270,即便如此之大的N,也不过loglogN = log270 < 9

参考资料

《数据结构 (c++语言版) 第三版 邓俊辉 编著》

此文有用? 求鼓励!

显示 Gitment 评论