C语言，如何快速得到一个数据里0或者1的个数？

冷雨夜

请教大家，如何快速判断一个数据里0或者1的个数？
比如送过来一个字节数据0x15，立马可以判断该数据里面含有3个1，和5个0？

ahong2hao

把0x15的高低四位分别查表，够快不。

什么，还不够，那你就把00~ff都建一个表吧

xiaobenyi

最快的速度就是先算个table出来,到时查表

jiangxingyuan

tab[256]={0,1,1……，1，0};
res=tab[n];

lindabell

tab[0]=0;
tab[1]=1;
tab[2]=1;
tab[3]=2;
tab[i]=i 中1的个数

res=tab[n];

RAMILE

直接查表快    其他的方法都不快

jiangxingyuan

实际点的算法：
res=0;
if(n|(~(1<<0))==(~(1<<0)))  res++;
if(n|(~(1<<1))==(~(1<<1)))  res++;
if(n|(~(1<<2))==(~(1<<2)))  res++;
if(n|(~(1<<3))==(~(1<<3)))  res++;
if(n|(~(1<<4))==(~(1<<4)))  res++;
if(n|(~(1<<5))==(~(1<<5)))  res++;
if(n|(~(1<<6))==(~(1<<6)))  res++;
if(n|(~(1<<7))==(~(1<<7)))  res++;
return res;

armstrong

查表，毫无疑问，且各平台通用。

sunplus

jiangxingyuan 发表于 2015-3-10 16:30
tab[256]={0,1,1……，1，0};
res=tab[n];

受教了

GYJ

查表最快

guowanling8061

这个方法应该很多吧！

Gallen.Zhang

楼主又没说数据一定是8位的，8位的倒是可以查表，16位，32位难道也去建立一个表吗，有这么大的空间建表吗。
倒是可以这样判断一个数中有多少个二进制1，假设数据为x，count为x中二进制1的个数。
int count = 0;
while(x)
{
     count++;
     x = x & (x - 1 );
}

techbaby

Gallen.Zhang 发表于 2015-3-10 16:52
楼主又没说数据一定是8位的，8位的倒是可以查表，16位，32位难道也去建立一个表吗，有这么大的空间建表吗。 ...

分段判断啊，可以看2楼的做法！

dzrs0620

for (unsigned char j = 0, unsigned char i = 0; i < 8; i ++)
{
    if (dat & (1  << i))
    {
        j ++;
    }
}

一个8次循环，不会比去查一个类似tab[256]={0,1,1……，1，0};这样的表格慢吧？

jiangxingyuan

dzrs0620 发表于 2015-3-10 17:03
for (unsigned char j = 0, unsigned char i = 0; i < 8; i ++)
{
    if (dat & (1

这个比查表慢太多了，移位比较慢的。还不如用立即做罗辑判别快。

cwei

只是不知这样做，实际意义何在？

lly10011

按高四位、低四位查表，兼顾速度与存储

冷雨夜

谢谢大家，看来分段查表是比较合适的方法了！

cece_co

查表最快，但是占用空间

bart

如果这样的运算你需要担心速度，我想你选错cpu了

0123456789

当然查表最快

abutter

没有 cache 的 CPU 基本上查表最快了。

dadatou

如果这样的运算你需要担心速度，我想你选错cpu了