补码与反码
考虑一个字节（8位）数据的取值范围：
若不需要表达正负，则8位都可用于表示数值；
若需要表达正负，则令首位为符号位（0表示正数，1表示负数），其余7位表示数值；
无符号：2^8-1+1 = 256，即取值范围是0~255；（+1是因为0）
有符号：（2^7-1+1）*2=256，即取值范围是-128~127；（+1是因为0，*2表示符号位的两种取值）
此时理论上表达了+0和-0两个数值。但-0是没有意义的，因此用它来表示-128。即+127=0|1111111，若试图+1，则将变为1|0000000，此二进制序列表示-128，即127+1=-128
反码：正数的反码与原码相同，负数的反码为将所有数值位取反，如：-119=1|1110111，其反码为：1|0001000
补码：正数的补码与原码相同，负数的补码为其反码+1，即-119的补码为：1|0001001
作用：观察补码与原码之和：1|1110111+1|0001001=11|0000000=1|0000000=0（截断1位），即原码+补码=一个周期，此性质可以将减法转换为加法。
用时钟做类比：当前时间为10:00，倒退2小时（做减法）相当于前进22小时（转换位加法）
所以在计算机中都是存储数值的补码
java中的负数位移
左移：右端补0，可能会改变符号
public static void main(String[] args){
int a = -29;
System.out.println(Integer.toBinaryString(a));
System.out.println(Integer.toBinaryString(a<<3)+"\n"+(a<<3));
}
右移：左端补1，保持了负号
public static void main(String[] args){
int a = -29;
System.out.println(Integer.toBinaryString(a));
System.out.println(Integer.toBinaryString(a>>3)+"\n"+(a>>3));
}
题目：
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。即完善函数：
public int NumberOf1(int n) {}
解
- 找到二进制数最右边的1，使之为0，count++，直到整个二进制数变为0（最优解）
实现上述操作可以利用 减1的性质：二进制数-1相当于将最右边的1以及再右边的0全部取反。此后与原码进行按位与操作，则可实现将最右边的1变为0
public int NumberOf1(int n) {
int count = 0;
while(n!=0){
count ++;
n = n & (n-1);
}
return count;
}
- 检查最右边的一位是否为1然后右移1位，若是则count++。可以通过和1进行按位与来实现
但此方法不能应用于负数，因为负数右移是补1.
避免这个问题可以反过来想：将1左移而不是将考察的数右移
public int NumberOf1(int n) {
int count = 0;
int index = 1;
while(index!=0){
if((n & index) != 0)
count ++;
index = index << 1;
}
return count;
}
