“马行无力皆因瘦，人不风流只为贫。”
正文
在上一篇中详细介绍了Android中的Integer类，其中有一个方法bitCount(int i)，他表示返回二进制中1的个数 ，我们看一下
1
2
3
4
5
6
7
8
public static int countBit(int i) {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
如果不明白可以看一下Integer源码详解，如果不太好理解那么就再改一下。
1
2
3
4
5
6
7
8
public static int countBit(int i) {
i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = (i & 0x0f0f0f0f) + ((i >> 4) & 0x0f0f0f0f);
i = (i & 0x00ff00ff) + ((i >> 8) & 0x00ff00ff);
i = (i & 0x0000ffff) + ((i >> 16) & 0x0000ffff);
return i & 0x3f;
}
这个就比较通俗易懂，更好理解。那么除了bitCount方法以外还有没有其他的方法来求二进制中1的个数呢，那么这一篇就来详细介绍一下求二进制中1的个数的其他方法。
1
2
3
4
5
6
7
8
9
10
public static int countBit(int i) {
int sum = 0;
while (i != 0) {
if (i % 2 == 1) {
sum++;
}
i /= 2;
}
return sum;
}
这是最简单的方法，乍一看好像还很对，我们看一下
1
2
3
4
System.out.println(countBit(33));
System.out.println(countBit(15));
System.out.println(countBit(0));
System.out.println(countBit(-1));
运行结果
1
2
3
4
2
4
0
0
因为负数是通过补码的形式存在的，-1的补码是32个一，很明显最后一个是错误的。那么在修改一下
1
2
3
4
5
6
7
8
9
10
public static int countBit(int i) {
int sum = 0;
while (i != 0) {
if (i % 2 == 1) {
sum++;
}
i = (i >>> 1);
}
return sum;
}
既然负数是通过补码形式存在的，那么通过移位是不是就没问题了，再看一下运行结果
1
2
3
4
2
4
0
31
可是这样发现也不对，明明是32个1的，这里为什么是31个，其实这里犯了一个大忌，因为判断一个数是否是奇偶数不能用等号，要用不等号，为什么这么说，因为负奇数对2求余是得-1的，这里再改一下，用不等号
1
2
3
4
5
6
7
8
9
10
public static int countBit(int i) {
int sum = 0;
while (i != 0) {
if (i % 2 != 0) {
sum++;
}
i = (i >>> 1);
}
return sum;
}
再看一下运行结果
1
2
3
4
2
4
0
32
所以这种写法才是正确的。当然还可以这样写
1
2
3
4
5
6
7
8
9
10
public static int countBit(int i) {
int sum = 0;
while (i != 0) {
if ((i&1)!= 0) {
sum++;
}
i = (i >>> 1);
}
return sum;
}
运行结果也是正确的，当然还可以这样写
1
2
3
4
5
6
7
8
public static int countBit(int i) {
int sum = 0;
while (i != 0) {
sum+=i&1;
i = (i >>> 1);
}
return sum;
}
下面这样写也对
1
2
3
4
5
6
7
8
public static int countBit(int i) {
int sum = 0;
while (i != 0) {
i &= i - 1;
sum++;
}
return sum;
}
这样可能不太好理解，如果你随便写几个就会明白，他会把最后的1一个个消除，直到变为0为止。还有下面这种方式
1
2
3
4
5
6
7
8
public static int countBit(int i) {
int count = 0;
for (int j = 0; j < 32; j++) {
if ((i & (1 << j)) >>> j == 1)
count++;
}
return count;
}
原理很简单就是通过1与各位上的数字与运算，如果为1就count++，当然还可以改为下面这种方式
1
2
3
4
5
6
7
8
public static int countBit(int i) {
int count = 0;
for (int j = 0; j < 32; j++) {
if ((i & (1 << j)) != 0)
count++;
}
return count;
}
判断每个位置上是否有1，还可以下面修改
1
2
3
4
5
6
7
8
9
public static int countBit(int i) {
int count = 0;
for (int j = 0; j < 32; j++) {
if ((i & 1) == 1)
count++;
i >>= 1;
}
return count;
}
这个使用i»=1,严格来说应该使用i»>=1更合适，但为什么前面一种方式也不会差错是因为for循环中就循环了32次，即使是负数也没关系，结果一样正确，下面再看一下其他方式。
1
2
3
4
5
6
7
8
9
10
public static int countBit(int i) {
//table是0到15转化为二进制时1的个数
int table[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
int count = 0;
while (i != 0) {//通过每4位计算一次，求出包含1的个数
count += table[i & 0xf];
i >>>= 4;
}
return count;
}
注释很明显就不在详述，上面只是4个一组求的，还可以八个一组，当然数组元素也很多，这里就不在列出。通过发现，只要认真挖掘总还能找到，那就继续，在上一篇讲到bitCount方法的时候，第一步是每两位存储1的个数，那么能不能每3位存储呢，当然可以，看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
public static int countBit(int i) {
// 每3个计算存储
int tmp = (i - ((i >>> 1) & 033333333333) - ((i >>> 2) & 011111111111));
// 因为Integer是32位，这里最前面是2个一个组合，后面的10个是每3个组合，正好是32位，总共11组，后面的每2组相加，
// 最前面的一组不动，所以下面的与运算最前面的3把它保留了（030707070707每3位一组，这里是8进制）
tmp = ((tmp + (tmp >>> 3)) & 030707070707);
// 每6位数相加，即2组
tmp = ((tmp + (tmp >>> 6)) & 07700770077);
tmp = ((tmp + (tmp >>> 12)) & 037700007777);
// 这里为什么要与63进行与运算，按说如果与077777777进行与运算也没错，8进制的8个7相当于24个1
//但因为Integer最多也就32个1，所以取后几位也就足够了
return ((tmp + (tmp >>> 24))) & 63;
}
这个方法也是可以的，只不过在最开始的时候他是每3个存放，原理很简单，主要把上面的8进制换成二进制就一目了然。那么既然能每3个存储，每四个是不是也可，当然可以，看代码
1
2
3
4
5
6
7
public static int countBit(int i) {
int tmp = i - ((i >>> 1) & 0x77777777) - ((i >>> 2) & 0x33333333)
- ((i >>> 3) & 0x11111111);
tmp = ((tmp + (tmp >>> 4)) & 0x0f0f0f0f);
tmp = ((tmp + (tmp >>> 8)) & 0x00ff00ff);
return ((tmp + (tmp >>> 16)) & 0x0000ffff) % 63;
}
这个比上面一个更简单，因为4个一组正好分成8组，不会像上面3个一组出现分不均的情况。当然还有其他方法也可以求，这里就不在介绍，也可以参考一下Hamming weight
