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

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

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