补码、反码、负数位移（二进制中1的个数）

补码与反码

考虑一个字节（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. 找到二进制数最右边的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;
}

2. 检查最右边的一位是否为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;
}