解法一：
对于一个正整数如果是偶数，该数的二进制数的最后一位是 0 ，反之若是奇数，则该数的二进制数的最后一位是 1 。因此，可以考虑利用位移、判断奇偶来实现。
?
?
public int bitCount(int x){
int count = 0;
while(x!=0){
if(x%2!=0){ //说明是偶数
count++;
}
x = x>>>1;
}
return count;
}
?
==============================================================
?
?
解法二：
知道了位移操作同样可以判断奇偶，且效率高于除法操作（“ % ”求余操作最后还是化为除法操作）那就可以用位移来代替上的求余运算。
????? 因为 x & 1 的结果为 1 或 0 ，为 1 的时候 count+=1 ，为 0 的时候 count+=0
则：
???? If(x&1==1){
???????? count++;
???? }
可简化为： count+ = x&1;
?
public int bitCount2(int x){
int count = 0;
while(x!=0){
count+ = x&1;
x = x>>>1;
}
return count;
}
?
?
解法三：
?? 正整数的二进制数最高位为 0 ，负整数和二进制数最高们为 1 ，则可利用左移、判断正负来实现 1 的个数的计算。
?
?
public int bitCount3(int x){
int count = 0;
while(x!=0){
if(x<0){
count++;
}
x = x<<1;
}
return count;
}
?
?
? ?
解法四：
前面的三种解法，运算的次数为二进制数的位数，时间复杂度仍为 O(log2 v) ，然而我们要计算 1 的个数，若让算法的运算次数只与“ 1 ”的个数有关，那复杂度就能进一步降低。
?
思想： x & (x-1) 可以消去 x 二进制数的最后一位 1
?
?
public int bitCount4( int x )
{
int count = 0;
while ( x != 0 )
{
x &= x - 1;
count++;
}
return count;
}
?
?
解法五：
?? JAVA 的 JDK 库里 Integer 有个 bitCount 方法，其代码是这样实现的
?
? ?
private int pop(int x)
{
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
?
==============================================================
?
二分法，两两一组相加，之后四个四个一组相加，接着八个八个，最后就得到各位之和了。
第一行是计算每两位中的
1
的个数
,
并且用该对应的两位来存储这个个数
,
如
: 01101100 -> 01011000 ,
即先把前者每两位分段
01 10 11 00 ,
分别有
1 1 2 0
个
1,
用两位二进制数表示为
01 01 10 00,
合起来为
01011000.
第二行是计算每四位中的
1
的个数
,
并且用该对应的四位来存储这个个数
.
如
: 01101100
经过第一行计算后得
01011000 ,
然后把
01011000
每四位分段成
0101 1000 ,
段内移位相加
:
前段
01+01 =10 ,
后段
10+00=10,
分别用四位二进制数表示为
0010 0010,
合起来为
00100010 .
下面的各行以此类推
,
分别计算每
8
位
,16
位
,32
位中的
1
的个数
.
将
0x55555555, 0x33333333, 0x0f0f0f0f
写成二进制数的形式就容易明白了
.
?
?
解法六：
?? HAKMEM 算法
?
private int pop2(int x) {
int n;
n = (x >> 1) & 033333333333;
x = x - n;
n = (n >> 1) & 033333333333;
x = x - n;
x = (x + (x >> 3)) & 030707070707;
x = x%63;
return x;
}
?
首先是将二进制各位三个一组，求出每组中 1 的个数，然后相邻两组归并，得到六个一组的 1 的个数，最后很巧妙的用除 63 取余得到了结果。
因为 2^6?=?64 ，也就是说 ?x_0?+?x_1?*?64?+?x_2?*?64?*?64?=?x_0?+?x_1?+?x_2?(mod?63) ，这里的等号表示同余
?
?
?
参考资料：
1. http://blog.csdn.net/justpub/article/details/2292823
2. http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item169
3. http://tekpool.wordpress.com/category/bit-count/
4. gurmeet.net/puzzles/fast-bit-counting-routines/
5. http://www.tekpool.com/node/2675
6. http://hi.baidu.com/rangemq/blog/item/9f918c8f83997eecf11f367b.html
7. http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer
8. http://mindprod.com/jgloss/bitcount.html
?
相关文章
