剑指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，则干脆不循环了。），效率会比较高一点。