二进制中的1的位数

剑指offer系列

复制代码package com.study; /* *求二进制中1的个数 *输入：整数 *返回： 1 的个数 * */ public class suanfa8 { /**常规解法*/ public static int OneNumber(long num) { int Counter = 0; long flag = 1; while(flag != 0) { if((num & flag )!= 0) Counter ++; flag = flag << 1; } return Counter; } /*新的解法*/ public static int OneBits(long num) { int count = 0; while(num != 0) { num = (num - 1) & num; count ++; } return count; } public static void main(String[] args) { System.out.println(OneNumber(-1)); System.out.println(OneBits(-1)); } }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

package com.study;
/*
*求二进制中1的个数
*输入：整数
*返回： 1 的个数
* */
public class suanfa8 {
/**常规解法*/
public static int OneNumber(long num) {
int Counter = 0;
long flag = 1;
while(flag != 0) {
if((num & flag )!= 0)
Counter ++;
flag = flag << 1;
}
return Counter;
}
/*新的解法*/
public static int OneBits(long num) {
int count = 0;
while(num != 0) {
num = (num - 1) & num;
count ++;
}
return count;
}
public static void main(String[] args) {
System.out.println(OneNumber(-1));
System.out.println(OneBits(-1));
}
}

备注

1.常规解法需要注意两点：一，移位操作尽量左移，因为右移会比较麻烦（有符号的情况下，补符号位，没有符号的情况下，补零）；二，为什么要让flag左移，而不是让num左移呢？因为负数是以补码的形式存储在机器中，如果是一个比较特殊的数比如是-1，它的存储形式是全1，所以这样会引起死循环。

2.新的解法采用的下面这样的思路：

让一个数减去1，如果末尾是1的话，只有最后一位会变，相与，会让这个数减少一个1位，达到效果；如果末尾是0的话，从最右边的1位开始到末尾，全部取反，也会减少一个1位，所以也能达到效果。这种方法的好处就是能减少运算的次数，第一种方法必须循环一个整数的位数的次数（有点饶舌，假如整数1在机器中存储的是32bit，则循环32次），但是第二种方法，只要循环该数中1的个数的次数就行了（如果该数为0，则干脆不循环了。），效率会比较高一点。