補(bǔ)碼與反碼

考慮一個(gè)字節(jié)（8位）數(shù)據(jù)的取值范圍：
若不需要表達(dá)正負(fù)，則8位都可用于表示數(shù)值；
若需要表達(dá)正負(fù)，則令首位為符號(hào)位（0表示正數(shù)，1表示負(fù)數(shù)），其余7位表示數(shù)值；
無(wú)符號(hào)：2^8-1+1 = 256，即取值范圍是0~255；（+1是因?yàn)?）
有符號(hào)：（2^7-1+1）*2=256，即取值范圍是-128~127；（+1是因?yàn)?，*2表示符號(hào)位的兩種取值）
此時(shí)理論上表達(dá)了+0和-0兩個(gè)數(shù)值。但-0是沒(méi)有意義的，因此用它來(lái)表示-128。即+127=0|1111111，若試圖+1，則將變?yōu)?|0000000，此二進(jìn)制序列表示-128，即127+1=-128
反碼：正數(shù)的反碼與原碼相同，負(fù)數(shù)的反碼為將所有數(shù)值位取反，如：-119=1|1110111，其反碼為：1|0001000
補(bǔ)碼：正數(shù)的補(bǔ)碼與原碼相同，負(fù)數(shù)的補(bǔ)碼為其反碼+1，即-119的補(bǔ)碼為：1|0001001
作用：觀察補(bǔ)碼與原碼之和：1|1110111+1|0001001=11|0000000=1|0000000=0（截?cái)?位），即原碼+補(bǔ)碼=一個(gè)周期，此性質(zhì)可以將減法轉(zhuǎn)換為加法。
用時(shí)鐘做類(lèi)比：當(dāng)前時(shí)間為10:00，倒退2小時(shí)（做減法）相當(dāng)于前進(jìn)22小時(shí)（轉(zhuǎn)換位加法）
所以在計(jì)算機(jī)中都是存儲(chǔ)數(shù)值的補(bǔ)碼

java中的負(fù)數(shù)位移

左移：右端補(bǔ)0，可能會(huì)改變符號(hào)

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));
 }

右移：左端補(bǔ)1，保持了負(fù)號(hào)

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));
}

題目：

輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示。即完善函數(shù)：

public int NumberOf1(int n) {}

解

1. 找到二進(jìn)制數(shù)最右邊的1，使之為0，count++，直到整個(gè)二進(jìn)制數(shù)變?yōu)?（最優(yōu)解）
   實(shí)現(xiàn)上述操作可以利用 減1的性質(zhì)：二進(jìn)制數(shù)-1相當(dāng)于將最右邊的1以及再右邊的0全部取反。此后與原碼進(jìn)行按位與操作，則可實(shí)現(xiàn)將最右邊的1變?yōu)?

public int NumberOf1(int n) {
        int count = 0;
        while(n!=0){
            count ++;
            n = n & (n-1);
        }
        return count;
}

2. 檢查最右邊的一位是否為1然后右移1位，若是則count++?？梢酝ㄟ^(guò)和1進(jìn)行按位與來(lái)實(shí)現(xiàn)
   但此方法不能應(yīng)用于負(fù)數(shù)，因?yàn)樨?fù)數(shù)右移是補(bǔ)1.
   避免這個(gè)問(wèn)題可以反過(guò)來(lái)想：將1左移而不是將考察的數(shù)右移

public int NumberOf1(int n) {
        int count = 0;
        int index = 1;
        while(index!=0){
            if((n & index) != 0)
                count ++;
            index = index << 1;
        }
        return count;
}