题目描述：
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
分析：
先复习几个知识点：
- 补码： 在计算机中所有的整数都是以二进制形式存储的，其中正整数用原码表示，负数用其正值的补码表示。
补码的计算机方式：对该负数的正值的原码，进行取反后加一，得到补码。
例如-6在计算机中的补码表示如下：（以32位计算机为例）
-6 的正值 6 的二进制：
00000000 00000000 00000000 00000110
取反，得反码：
11111111 11111111 11111111 11111001
+1 ，得补码，即 -6 在计算机中的二进制表示：
11111111 11111111 11111111 11111010
- 补码的性质：在计算机中，加法器实现最为简单，很多运算最终都要转化为加法运算，而，减去一个数相当于加上这个数的补码。（非常巧妙的设计，让人佩服冯诺依曼的天才创意！关于补码的详细介绍）
负数的右移：因为负数在内存中是以补码形式存在的，所有首先根据负数的原码求出负数的补码(符号位不变，其余位按照原码取反加1)，然后保证符号位不变，其余位向右移动到X位，在移动的过程中，高位补1.等移位完成以后，然后保持符号位不变，其余按位取反加1，得到移位后所对应数的原码。即为所求。详见
正数的左移与右移、负数的无符号右移，就是相应的补码移位所得，在高位补0即可。
负数的右移，就是补码高位补1,然后按位取反加1。左移、右移：
在不溢出的情况下
左移n位后的值 等于原值乘以2的n次方
例如 4 <<2 就是16，二进制就是 00000100 <<00010000
-4<<2 就是-16 二进制就是 11111100 <<11110000
右移n位后的值 等于原值除以2的n次方的商
例如 4 >>2 就是1，二进制就是 00000100 >>00000001
-4>>2 就是-1 二进制就是 11111100 <<11111111
代码：
- 将二进制转化为数组，然后一位一位进行判断（重点：熟悉java中相应的API）
public class Solution {
public int NumberOf1(int n) {
int result =0;
char[] array = Integer.toBinaryString(n).toCharArray();
for(char c:array){
if(c=='1'){
result ++;
}
}
return result;
}
}
- 改进，既然熟悉java的API,就会发现JAVA 的 JDK 库里 Integer 有个 bitCount 方法,直接调用即可：
public class Solution {
public int NumberOf1(int n) {
return Integer.bitCount(n);
}
}
查看Integer.bitCount(）的源码如下：
/**
* Returns the number of one-bits in the two's complement binary
* representation of the specified {@code int} value. This function is
* sometimes referred to as the <i>population count</i>.
*
* @return the number of one-bits in the two's complement binary
* representation of the specified {@code int} value.
* @since 1.5
*/
public static int bitCount(int i) {
// HD, Figure 5-2
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
二分法，两两一组相加，之后四个四个一组相加，接着八个八个，最后就得到各位之和了。
第一行是计算每两位中的 1 的个数 , 并且用该对应的两位来存储这个个数 , 如 : 01101100 -> 01011000 , 即先把前者每两位分段 01 10 11 00 , 分别有 1 1 2 0 个 1, 用两位二进制数表示为 01 01 10 00, 合起来为 01011000.
第二行是计算每四位中的 1 的个数 , 并且用该对应的四位来存储这个个数 . 如 : 01101100 经过第一行计算后得 01011000 , 然后把 01011000 每四位分段成 0101 1000 , 段内移位相加 : 前段 01+01 =10 , 后段 10+00=10, 分别用四位二进制数表示为 0010 0010, 合起来为 00100010 .
下面的各行以此类推 , 分别计算每 8 位 ,16 位 ,32 位中的 1 的个数 .
将 0x55555555, 0x33333333, 0x0f0f0f0f 写成二进制数的形式就容易明白了 .
3.根据上面的源码，可以类似的使用二分法写出 HAKMEM 算法的解法
public class Solution {
public int NumberOf1(int n) {
int num;
num = (n >> 1) & 033333333333;
n = n - num;
num = (num >> 1) & 033333333333;
n = n - num;
n = (n + (n >> 3)) & 030707070707;
n = n%63;
return n ;
}
}
这个通过率只有40%，应该是哪里有问题。
- 通过位移判断奇偶数并计数，标志位初始为1，将其和输入值相与，n & 1 的结果为 1 或 0 ，为 1 的时候 count+=1 ，为 0 的时候 count+=0
public class Solution {
public int NumberOf1(int n) {
int count = 0;
int flag = 1;
while(flag!=0){
if((n&flag)!=0){
count++;
}
flag = flag<<1;
}
return count;
}
}
- 正整数的二进制数最高位为 0 ，负整数和二进制数最高们为 1 ，则可利用左移、判断正负来实现 1 的个数的计算。
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n!=0){
if(n<0){
count++;}
n=n<<1;//左移一位,左边的最高位为符号位，根据正负数来判断符号位的0,1，从而得到1的个数
}
return count;
}
}
这种方法最容易理解.
- 思想： x & (x-1) 可以消去 x 二进制数的最后一位 1
n : 10110100
n-1 : 10110011
n&(n-1) : 10110000
public class Solution {
public int NumberOf1(int n) {
int cnt = 0;
while (n != 0) {
cnt++;
n &= (n - 1);
}
return cnt;
}
}
把一个整数减去1，再和原整数做运算，会把该整数最右边一个1变成0，那么一个整数的二进制表示有多少个1，就可以进行多少次这样的操作.
O(logM) 时间复杂度解法，其中 M 表示 1 的个数。
