当前位置： 查字典图书网> 编程> 编程之美> “求二进制数中1的个数”

“求二进制数中1的个数”

knowcraft 对 编程之美 的书评 发表时间：2010-05-05 15:05:00

 求二进制中1的个数。对于一个字节（8bit）的变量，求其二进制表示中"1"的个数，要求
算法的执行效率尽可能的高。

解法四，查表法，因为只有数据8bit，直接建一张表，包含各个数中1的个数，然后查表就
行。复杂度O(1)。

   1: int countTable[256] = { 0, 1, 1, 2, 1, ..., 7, 7, 8 };
   2:
   3: int Count(int v) {
   4: return countTable[v];
   5: }

这个思路与hash表相近。
关于查表，我想到了做这个表的一个方法
现有一数组a[255],a[i]表示数字i中1的个数，假设i是处于[2^b,2^(b+1))这个左闭右开的
区间，那么有a[i]=a[i-2^b]+1,因为i与i-2^b相比，除了最高位前者为1，后者为0，后几
位都相同，这样就能递归推出所有数字了。
#include <iostream.h>
#include <math.h>
int a[255]={0,1};
void main()
{
cout<<0<<endl<<1<<endl;
for(int i=2;i<=255;i++)
{
        int b=log(i)/log(2);
a[i]=a[i-(1<<b)]+1;
cout <<a[i]<<endl;
}
}

有用 4 无用 1

您对该书评有什么想说的？

对““求二进制数中1的个数””的回应

knowcraft
knowcraft 2010-05-11 14:59:36

一个朋友的思路，另一种递归
void count_bit_4 (vector<int> & a)
{
a[0]=0;
a[1]=1;
for(int i=2;i<=255;i++)
{
a[i]= a[i>>1] + i&0x01;
}
}

回应他

《编程之美》热门书评

编程之美

书名： 编程之美
作者： 程之美》小组  |  《
出版社： 电子工业出版社
副标题： 微软技术面试心得
出版年： 2008-3
页数： 327
定价： 40.00元
装帧： 平装
ISBN： 9787121060748