题目

计算在一个 32 位的整数的二进制表示中有多少个 1.
http://www.lintcode.com/zh-cn/problem/count-1-in-binary/

分析

先考虑正整数的情况（负数以补码的形式存储）。
由于位数确定是32位，其实可以进行简单的分治。32位整数由4个字节组成，如果知道每个字节二进制表示时，其中包含的1的个数，4个字节的总和，就是这个整数包含的1的数量。

如何计算出一个字节中包含的1的数量呢？可以继续将字节划分成高4位和低4位两组，四个比特位的情况已经很容易枚举了，高低4字节的和就是这个字节的1的数量。

知道了正整数的计算，负数又应该怎么处理呢？很简单，将负数的补码形式按位取反，记为x，计算出x转化为二进制时1的含量，假设为y，32-y就是我们想要的结果。

代码

public class Solution {

    int c4bit(byte v){
        switch(v){
            case 0x1:
            case 0x2:
            case 0x4:
            case 0x8:
                return 1;
            case 0x3:
            case 0x5:
            case 0x6:
            case 0x9:
            case 0xA:
            case 0xC:
                return 2;
            case 0x7:
            case 0xB:
            case 0xD:
            case 0xE:
                return 3;
            case 0xF:
                return 4;
            default:
                return 0;
        }
    }

    int count(byte v){
        return c4bit((byte)(v&0x0F) ) + c4bit((byte)((v&0xF0)>>4) );
    }

    int countPositive(int num){
        byte[] data = new byte[4];
        data[0] = (byte) ((num & 0xFF000000) >> 24);
        data[1] = (byte) ((num & 0x00FF0000) >> 16);
        data[2] = (byte) ((num & 0x0000FF00) >> 8);
        data[3] = (byte)(num & 0x000000FF);

        return count(data[0]) + count(data[1]) + count(data[2]) + count(data[3]);
    }
    /*
     * @param num: An integer
     * @return: An integer
     */
    public int countOnes(int num) {
        // write your code here
        if(num < 0){
            num = ~num;
            return 32 - countPositive(num) ;
        }
        return countPositive(num);
    }

    public static void main(String[] args){
        Solution s = new Solution();
        int v = s.countOnes(2147483647);
        System.out.print(v);
    }
};