如何计算32位数中‘1’的个数
本文内容来自微信公众号嵌入式Linux。支持原创,尊重原创!
大神计算32位数中‘1’的个数
首先直接看代码:
int count_bits(int x)
{
register int xx=x;
xx=xx-((xx>>1)&0x55555555);
xx=(xx&0x33333333)+((xx>>2)&0x33333333);
xx=(xx+(xx>>4))&0x0f0f0f0f;
xx=xx+(xx>>8);
return (xx+(xx>>16)) & 0xff;
}
我看到后的第一反应就是懵逼,不断的位移不断地按位与,到最后是什么结果不仔细分析我看不出来,看了函数名,也大概猜到了是统计什么位的个数的。
韦大神如何实现相同的功能
同样,先直接上代码:
#include "stdio.h"
#include "time.h"
int count_bits(int x)
{
register int xx=x;
xx=xx-((xx>>1)&0x55555555);
xx=(xx&0x33333333)+((xx>>2)&0x33333333);
xx=(xx+(xx>>4))&0x0f0f0f0f;
xx=xx+(xx>>8);
return (xx+(xx>>16)) & 0xff;
}
int count_bits2(int x)
{
int i = 0;
int s = 0;
for(i = 0;i<32;i++)
{
if(x&0x01)
s ++;
x = x>>1;
}
return (s);
}
int main(void)
{
printf("%d\n",count_bits(12345678));
printf("%d\n",count_bits2(12345678));
}
OK,只看count_bits2函数,就简单太多了!
刨析大神代码
先来个简单的例子:
#include "stdio.h"
int count_bits4(char x)
{
x = (x&0x55) + ((x>>1)&0x55);
x = (x&0x33) + ((x>>2)&0x33);
x = (x&0x0F) + ((x>>4)&0x0F);
return x;
}
int main()
{
printf("%x\n",count_bits4(0x12));
}
贴上运行结果:
我们现看看下面这段 0x55 = 0b01010101 0x33 = 0b00110011 0x0F = 0b00001111
图中表示相邻两个数不断相加,知道这个数据的长度
比如:
如果要计算0x34里面1的个数,那么先将其转换成二进制,然后把相邻的二进制位相加,再然后把相邻的两位数相加,最后把相邻的四位数相加。
复杂一点的
上代码:
#include "stdio.h"
int count_bits3(long long s)
{
s = (s&0x5555555555555555L) + ((s>>1)&0x5555555555555555L);
s = (s&0x3333333333333333L) + ((s>>2)&0x3333333333333333L);
s = (s&0x0F0F0F0F0F0F0F0FL) + ((s>>4)&0x0F0F0F0F0F0F0F0FL);
s = (s&0x00FF00FF00FF00FFL) + ((s>>8)&0x00FF00FF00FF00FFL);
s = (s&0x0000FFFF0000FFFFL) + ((s>>16)&0x0000FFFF0000FFFFL);
s = (s&0x00000000FFFFFFFFL) + ((s>>32)&0x00000000FFFFFFFFL);
return (int)s;
}
int main()
{
printf("%x\n",count_bits3(0x122312351345134));
}
运行结果输出15。这里就不再贴图了。感兴趣的可以自己测试一下。
搞清楚了上面的那段代码,再看下面这段代码,就会好很多了。
实测大神的代码是如何吊打普通代码的
上菜:test1.c
#include "stdio.h"
#include <time.h>
int count_bits(int x)
{
register int xx=x;
xx=xx-((xx>>1)&0x55555555);
xx=(xx&0x33333333)+((xx>>2)&0x33333333);
xx=(xx+(xx>>4))&0x0f0f0f0f;
xx=xx+(xx>>8);
return (xx+(xx>>16)) & 0xff;
}
int main(void)
{
clock_t start, end;
start = clock();
unsigned int i = 0;
for(i = 0;i<10000000;i++){
count_bits(12345678);
}
printf("%d\n",count_bits(12345678));
end = clock();
double seconds =(double)(end - start)/CLOCKS_PER_SEC;
fprintf(stderr, "Use time is: %.8f s\n", seconds);
return (0);
}
test2.c
#include "stdio.h"
#include <time.h>
int count_bits2(int x)
{
int i = 0;
int s = 0;
for(i = 0;i<32;i++)
{
if(x&0x01)
s ++;
x = x>>1;
}
return (s);
}
int main(void)
{
clock_t start, end;
start = clock();
unsigned int i = 0;
for(i = 0;i<10000000;i++){
count_bits2(12345678);
}
printf("%d\n",count_bits2(12345678));
end = clock();
double seconds =(double)(end - start)/CLOCKS_PER_SEC;
fprintf(stderr, "Use time is: %.8f s\n", seconds);
return (0);
}
运行结果:
个人感受
从代码的可读性和维护上来说,我喜欢韦大神的写法,但是文章开头大神的代码从效率上来说比韦大神的好。各有优略,建议大家再使用的时候权衡利弊!
网友们的做法
u8 cnt;
while(value)
{
value &= value - 1;
cnt++;
}
return cnt;
public int NumberOf1(int n) {
int count = 0;
while (n != 0) {
n = n & (n - 1);
count += 1;
}
return count;}
至此,所有!
在此,再次说明,本文原创不是本人,有兴趣的话大家可以关注一下微信公众号“嵌入式Linux”!
叨叨几句... NOTHING