OnTheWay2012
埋葬昨天的我，迎来重生的我！
posts - 15,  comments - 89,  trackbacks - 0
一道面试题（求一个unsigned int 数的二进制表示中有多少个1？）

求一个unsigned int 数的二进制表示中有多少个1？
这是一道面试题可以用以下的一些方案。
第一种是很容易想到的采用循环的方式并且与1进行位与运算，具体代码如下。

 1unsigned int GetBitNumOfOne_ByLoop1(unsigned int nValue)
 2{
 3 const unsigned int nNumOfBitInByte = 8;
 4 unsigned int nBitMask = 1;
 5 unsigned int nBitNum = 0;
 6 for(unsigned int i = 0 ; i < sizeof(nValue) * nNumOfBitInByte ; i++)
 7 {
 8  (0 < (nValue & nBitMask)) ? nBitNum++ : 0;
 9  nBitMask<<=1;
10 }
11 return nBitNum;
12}
13unsigned int GetBitNumOfOne_ByLoop2(unsigned int nValue)
14{
15 const unsigned int nNumOfBitInByte = 8;
16 unsigned int nBitMask = 1;
17 unsigned int nBitNum = 0;
18 for(unsigned int i = 0 ; i < sizeof(nValue) * nNumOfBitInByte ; i++)
19 {
20  (0 < (nValue & nBitMask)) ? nBitNum++ : 0;
21  nValue>>=1;
22 }
23 return nBitNum;
24}

这两种做法很相像，却别就是在是对nBitMask进行左移还是对nValue进行右移。
当然了以上的两个方法存在一个问题：不管如何这个函数肯定要循环32次（对于32平台来说）。
那又没有更好的方法？当然有，请看下面：
 1unsigned int GetBitNumOfOne_ByLoop3(unsigned int nValue)
 2{
 3 unsigned int nBitNum = 0;
 4 while(0 < nValue)
 5 {
 6  nValue &=(nValue - 1);
 7  nBitNum++;
 8 }
 9 return nBitNum;
10}

假如使用参数12345（二进制是11000000111001）调用该函数，该函数的执行情况如下：
第一次进入循环
0 < 11000000111001
11000000111001 &= (11000000111001 - 1) 之后 nValue 的值 是 11000000111000
nBitNum 的值是1
经过本次循环之后11000000111001 变成了 11000000111000 比之前少了一个1
第二次进入循环
0 < 11000000111000
11000000111000 &= (11000000111000 - 1) 之后 nValue 的值 是 11000000110000
nBitNum 的值是2
经过本次循环之后11000000111000 变成了 11000000110000 比之前少了一个1
第三次进入循环
0 < 11000000110000
11000000110000 &= (11000000110000 - 1) 之后 nValue 的值 是 11000000100000
nBitNum 的值是3
经过本次循环之后11000000110000 变成了 11000000100000 比之前少了一个1
经过以上3次循环情况的说明，我相信你一定看出了些什么吧。nValue &=(nValue - 1)，这句
代码实际上就是把nValue 的某位及其以后的所有位都变成0，当nValue最后变成0的时候循环结束，
且nBitNum 记录的就是1的个数。
上面的做法已经很不错了，但是作为程序员的你是否会有疑问，“还有其他的方法吗？”。
有，当然有！请看下面的代码：
 1unsigned int GetBitNumOfOne(unsigned int nValue)
 2{
 3 nValue = ((0xaaaaaaaa & nValue)>>1) + (0x55555555 & nValue);
 4 nValue = ((0xcccccccc & nValue)>>2) + (0x33333333 & nValue);
 5 nValue = ((0xf0f0f0f0 & nValue)>>4) + (0x0f0f0f0f & nValue);
 6 nValue = ((0xff00ff00 & nValue)>>8) + (0x00ff00ff & nValue);
 7 nValue = ((0xffff0000 & nValue)>>16) + (0x0000ffff & nValue);
 8 
 9 return nValue;
10}


假如你是第一次看到这些代码，你是否能看明白？呵呵，本人第一次看到这些代码的时候看了好久才感觉
好像有点明白。下面我就以一个例子来说明上面的代码是如何做到的。
假如参数是0xffffffff。
第一行代码：
nValue = ((0xaaaaaaaa & nValue)>>1) + (0x55555555 & nValue);
a的二进制表示是：1010
5的二进制表示是：0101
0xffffffff 与 0xaaaaaaaa 进行与运算之后是0x10101010101010101010101010101010
然后再进行左移操作后是0x01010101010101010101010101010101
0x55555555 & nValue 进行与运算之后是0x01010101010101010101010101010101
然后0x01010101010101010101010101010101 & 0x01010101010101010101010101010101
得到0x10101010101010101010101010101010
我们把得到的结果分成16组0x10  10  10  10  10  10  10  10  10  10  10  10  10  10  10  10
每组的10单独来看是不是十进制的2
我们0x01010101010101010101010101010101和0x01010101010101010101010101010101这两个数也按照上面的方法分成
16个组0x01  01  01  01  01  01  01  01  01  01  01  01  01  01  01  01
      0x01  01  01  01  01  01  01  01  01  01  01  01  01  01  01  01
那么这两个数的每一个组都是01 那么两个01 里面有几个1，是不是2个。这是2是不是二进制的10，然后16个10组合起来是不是
0x10101010101010101010101010101010

第二行代码：
nValue = ((0xcccccccc & nValue)>>2) + (0x33333333 & nValue);
此时nValue是0x10101010101010101010101010101010
c的二进制表示是：1100
3的二进制表示是：0011
0xcccccccc 与 nValue) 进行与运算之后是0x10001000100010001000100010001000
然后再进行左移操作后是0x00100010001000100010001000100010
0x33333333 & nValue 进行与运算之后是0x00100010001000100010001000100010

然后0x00100010001000100010001000100010 & 0x00100010001000100010001000100010
得到0x01000100010001000100010001000100
我们把得到的结果分成8组0x0100 0100 0100 0100 0100 0100 0100 0100
每组的0100单独来看是不是十进制的4 总共有多少个4？是不是8个，8×4=32。

以下的代码：
 nValue = ((0xf0f0f0f0 & nValue)>>4) + (0x0f0f0f0f & nValue);
 nValue = ((0xff00ff00 & nValue)>>8) + (0x00ff00ff & nValue);
 nValue = ((0xffff0000 & nValue)>>16) + (0x0000ffff & nValue);
请自己按照上面的方法做一遍，就会发现规律：第一次32位数分成32组，第二次分成16组，第三次分成8，第四次分成4，第五次分成2组。
如果还是不明白请多看看，然后多选择几个参数进行试验，多试几次肯定会明白的。


看了这么多解法是不是有中很过瘾的感觉，当我知道有这么多解法是也很过瘾，也很遗憾。遗憾什么呢？遗憾当时我碰到这道面试题的时候
只想到了采用循环的方法，可是那个面试题上明确说明不准使用循环！！当时很郁闷！！
郑重声明：上面最后两个解法非本人原创，本人只是总结归纳，向想出这么好方法的前辈高人致敬！

posted on 2010-03-24 18:02 OnTheWay 阅读(6140) 评论(15)  编辑 收藏 引用 所属分类: 面经

FeedBack:
# re: 一道面试题（求一个unsigned int 数的二进制表示中有多少个1？）
2010-03-25 17:00 | 乐蜂专卖店
案件的骄傲是巨大  回复  更多评论
  
# re: 一道面试题（求一个unsigned int 数的二进制表示中有多少个1？）
2010-03-25 17:01 | hoodlum1980
一个UINT32，写成16进制字符串，是“00000000”，“FFFFFFFF”。
“0”到“F”，可以做一个16个元素的数组，该数组提供每个字母中 1 的个数。

这样我们把这个数字格式化成16进制的字符串，然后用查表法，累加每个字母位于数组中的1的个数即可。

例如：“0”： 0000; 1的个数 = 0, “F”：1111; 1的个数=4；

不知可行否？  回复  更多评论
  
# re: 一道面试题（求一个unsigned int 数的二进制表示中有多少个1？）
2010-03-25 18:10 | OnTheWay
不可行。
你的方法的思想是有点类似于桶排序的思想，但是是不可行的。
首先从时间效率和空间效率上看与上述的任何一个方案相比都没有优势。
另外在计算机里数据是按照二进制的方式进行存储的，按照你的方案还需要把二进制再转换成16进制的，如果你能进行转换的话，很可能说明此时你已经知道了这些二进制位中有多少个1了。  回复  更多评论
  
# re: 一道面试题（求一个unsigned int 数的二进制表示中有多少个1？）
2010-03-25 18:11 | OnTheWay
@乐蜂专卖店
别在这里做广告了。  回复  更多评论
  
# re: 一道面试题（求一个unsigned int 数的二进制表示中有多少个1？）
2010-03-25 18:12 | hoodlum1980
补全一下代码：
#include <stdio.h>
#include <string.h>
int GetBitNumOfOne_ByHoodlum(unsigned int nValue)
{
size_t i;
int count = 0;
char *CharSet = "0123456789ABCDEF";

//每个字符中含有的1的个数
int table[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
char str[12];
sprintf(str, "%X", nValue);
size_t length = strlen(str);
for(i=0; i < length; i++)
{
count += table[ strchr(CharSet, str[i]) - CharSet ];
}
return count;
}  回复  更多评论
  
# re: 一道面试题（求一个unsigned int 数的二进制表示中有多少个1？）
2010-03-25 18:32 | OnTheWay
@hoodlum1980
呵呵，我的理解有误，按照你的方案确实可以实现。
不过时间效率和空间效率确实不是太高。
另外如果可以使用这么多系统函数的话，那还是使用标准库的bitset方便些。
代码如下：
#include <iostream>
#include <bitset>
#include <algorithm>

using namespace std;

size_t GetBitNumOfOne_ByBitSet(unsigned int nValue)
{
const size_t sizeBitNum = 8;
bitset<sizeof(unsigned int) * sizeBitNum> TestBitSet(nValue);
string strContent = TestBitSet.to_string();
return std::count(strContent.begin(), strContent.end(), '1');
}

void main()
{
//测试数据
cout<<GetBitNumOfOne_ByBitSet(0)<<endl;
cout<<GetBitNumOfOne_ByBitSet(1)<<endl;
cout<<GetBitNumOfOne_ByBitSet(2)<<endl;
cout<<GetBitNumOfOne_ByBitSet(123)<<endl;
cout<<GetBitNumOfOne_ByBitSet(0xff)<<endl;
}  回复  更多评论
  
# re: 一道面试题（求一个unsigned int 数的二进制表示中有多少个1？）[未登录]
2010-03-26 09:52 | hh
先计算出结果, 找规律

之后重写程序, 两字: 查表  回复  更多评论
  
# re: 一道面试题（求一个unsigned int 数的二进制表示中有多少个1？）
2010-03-29 12:53 | 小时候可靓了
查表吧，反正是有限位，建一个表
比如 0 0 ,1 1, 2 1 , 3 2...  回复  更多评论
  
# re: 一道面试题（求一个unsigned int 数的二进制表示中有多少个1？）[未登录]
2010-03-31 14:54 | tom
试过std::bitset没？可以用int直接构造，再循环调用std::bitset::test()测试每一位就齐活。  回复  更多评论
  
# re: 一道面试题（求一个unsigned int 数的二进制表示中有多少个1？）
2010-04-04 22:29 | ARush
#include "stdafx.h"
#include <stdio.h>
//得到一个unsigned int整数的二进制表示中1的数目
int GetNO(unsigned int number);
int _tmain(int argc, _TCHAR* argv[])
{
int number;
puts("input a int number");
while(scanf("%d",&number)==1)
{
int result=0;
result=GetNO(number);
printf("\nthe length of %d is %d\n",number,result);
puts("input a int number");
}
return 0;
}
int GetNO(unsigned int number)
{
int size=sizeof(unsigned int)*8;
int result=0;
for(int i=0;i<size;i++,number>>=1)
{
if(number==0)
break;
if((01&number)==01)
result++;
}
return result;
}  回复  更多评论
  
# re: 一道面试题（求一个unsigned int 数的二进制表示中有多少个1？）
2010-04-08 11:53 | jmchxy
调用任何系统函数都会增加时间空间效率， 循环调用 bitset::test 不会比第一种方法更好。 sprintf 转换到16进制本身就需要进行一次循环除法取余， std::count 同样是循环算法. 第三种方法是常数复杂度，最快的。  回复  更多评论
  
# re: 一道面试题（求一个unsigned int 数的二进制表示中有多少个1？）
2010-04-29 17:05 | D
int countbit(int n)
{
int c;
for(c=0;n;n>>=1) c+=n&1;
return c;
}
  回复  更多评论
  
# re: 一道面试题（求一个unsigned int 数的二进制表示中有多少个1？）[未登录]
2010-05-29 11:26 | hdqqq
unsigned long val ;
int count = 0;
while(val) {
count += (val & 1) ;
val >>= 1;
}  回复  更多评论
  
# re: 一道面试题（求一个unsigned int 数的二进制表示中有多少个1？）[未登录]
2010-05-29 11:30 | hdqqq
@hdqqq
上面已经贴了类似的，我的作废。  回复  更多评论
  
# re: 一道面试题（求一个unsigned int 数的二进制表示中有多少个1？）
2010-11-24 23:22 | triangle
@OnTheWay
第一行代码：nValue = ((0xaaaaaaaa & nValue)>>1) + (0x55555555 & nValue);
将32位数分为16组，判断出每两位中有多少个1,并用两位来表示结果。
(0xaaaaaaaa & nValue)>>1) 计算偶数位是否为1; 如10&10>>1 = 01
(0x55555555 & nValue) 计算基数为是否为1; 如10&01= 00
两数相加得出10中包含的1的个数为0x01;
后面的代码则是如何将16组2位数相加得出最后的结果。
第二行代码：((0xcccccccc & nValue)>>2) + (0x33333333 & nValue);
将nValue的分成8组，每组中的两两相加;
如(0110 & 1100)>>2 + (0110 & 0011) = 0011; 即 01 + 10 = 0011;
同理：
第三行代码： 将nValue分成4组，每组中的两两相加，也就是每4位相加，结果保存在8位数中。
第四行代码： 将nValue分成2组，每组中的两两相加，也就是每8位相加，结果保存在16位数中。
第五行代码： 将nValue分成1组，每组中的两两相加，也就是每16位相加，结果保存在32位数中。






  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理



<2010年11月>
日一二三四五六
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

常用链接

留言簿(4)

随笔分类

随笔档案

友情连接

搜索

  •  

最新评论

阅读排行榜

评论排行榜

Copyright ©2024 OnTheWay Powered By博客园 模板提供：沪江博客