题目
计算在一个 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);
}
};