问题描述:对于一个字节的无符号整型变量,求其二进制表示中1的个数。
解答:
看到这个问题,一个最直接的想法就是%2来统计1的个数了,实现如下:
int count(type n)
{
int count = 0;
while(n != 0)
{
if(n%2 == 1)
{
count++;
}
n = n/2;
}
return count;
}
解法二:
int count(type n)
{
int count = 0;
while(n != 0)
{
n = n & (n-1);
count++;
}
return count;
}
这个其实是很经典而且常见的一个解法
当然,对于题目要求的byte类型,可以使用书上推荐的查表法来解决,这样是使用空间来换时间的做法,但对于16位或者更多位的数来说,查表法基本是不可能的。
===============================华丽的分割线===============================
上面的几个解法是比较常见的答案,但深入研究发现,这个问题其实是经典的Hamming weight(http://en.wikipedia.org/wiki/Hamming_weight) ,其定义是 The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. 而且wiki上给出了一种神奇的高效率的解法,不得不佩服hamming!
其做法是采用这样的思想,类似归并的做法。对于相邻的两位,先计算这两位的1的个数(最大是2),比如对于32位的数来说,分成 16组,每组计算的是相邻两位的1的个数和,并且将这个和用新得到的数的两位表示(2位可以最大表示4,所以可以存得下这个和,和此时最大为2);然后对相邻四位进行操作,计算每两位两位的和(这样操作后其实是计算了原来32位数的相邻四位的1的个数);这样依次类推,对于32位的数来说,只要操作到将其相邻16位的1的个数相加就可以得到其包含的1的个数了。
对于这种思想,wiki上给出了大概的解法:
int count(int num) //假设int是32位
{
int count = num;
int a = 0x55555555; //010101010101010101010101010101 //用于相邻的两位相加
int b = 0x33333333; //用于相邻的四位相加
int c = 0x0f0f0f0f;
int d = 0x00ff00ff;
int e = 0x0000ffff;
count = (count & a) + ((count>>1) & a);
count = (count & b) +((count>>2) & b);
count = (count & c) + ((count>>4) & c);
count = (count & d) + ((count>>8) & d);
count = (count & e) + ((count>>16) & e);
return count;
}
另外还有一个解法,MIT HAKMEM算法,没有去研究,囧
还有一个更巧妙的HAKMEM算法
1: int Count(unsigned x) {
2: unsigned n;
3:
4: n = (x >> 1) & 033333333333;
5: x = x - n;
6: n = (n >> 1) & 033333333333;
7: x = x - n;
8: x = (x + (x >> 3)) & 030707070707;
9: x = modu(x, 63);
10: return x;
11: }
首先是将二进制各位三个一组,求出每组中1的个数,然后相邻两组归并,得到六个一组的1的个数,最后很巧妙的用除63取余得到了结果。
因为2^6 = 64,也就是说 x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63),这里的等号表示同余。
这个程序只需要十条左右指令,而且不访存,速度很快。
由此可见,衡量一个算法实际效果不单要看复杂度,还要结合其他情况具体分析。
关于后面的两道扩展问题,问题一是问32位整型如何处理,这个上面已经讲了。
问题二是给定两个整数A和B,问A和B有多少位是不同的。
这个问题其实就是数1问题多了一个步骤,只要先算出A和B的异或结果,然后求这个值中1的个数就行了。
=====================华丽的分割线========================
问题扩展:
给定两个正整数A和B,问把A变成B需要改变多少位?也就是A和B的二进制中有多少位是不同的?
解法:其他这个问题是hamming weight的扩展,先将A和B进行异或操作(^),那么就得到的这个数的hamming weight就是A变成B需要改变的位数。
参考资料:
联系客服