原碼备畦、反碼和補(bǔ)碼

在正常的運(yùn)算規(guī)則下低飒，我們熟悉的十進(jìn)制會(huì)轉(zhuǎn)化成二進(jìn)制在計(jì)算機(jī)中表示，這時(shí)的二進(jìn)制就是原碼表示懂盐，在計(jì)算機(jī)中褥赊，為了簡(jiǎn)化運(yùn)算單元的邏輯處理、降低硬件電路復(fù)雜度和成本莉恼，只有加法器的硬件電路拌喉，計(jì)算機(jī)的減法是通過(guò)數(shù)學(xué)變換把其轉(zhuǎn)化成加法運(yùn)算，比如5-2俐银，也就是5+(-2)尿背，但是如果用原碼形式去運(yùn)算5+(-2)得到的值卻不是我們想要的值，所以經(jīng)過(guò)探索捶惜，又出現(xiàn)了反碼和補(bǔ)碼田藐，至于他們有什么作用，繼續(xù)往下看吱七。

• 原碼

  原碼就是真值的二進(jìn)制表示汽久，最高位表示符號(hào)位，整數(shù)的符號(hào)位是0陪捷，負(fù)數(shù)的符號(hào)位是1回窘。

  比如十進(jìn)制真值是6，那么八位二進(jìn)制的原碼就是00000110市袖，最高位是0表示正數(shù)啡直；十進(jìn)制的-3的八位二進(jìn)制表示為10000011，最高位1表示負(fù)數(shù)苍碟。6-3 = 6+(-3) = 00000110+10000011 = 10001001 = -9酒觅，很顯然它不是正確值3。

• 反碼

  反碼的規(guī)則是正數(shù)的反碼是它本身微峰，負(fù)數(shù)的反碼是符號(hào)位不變舷丹，其余位取反。

  還是上面的例子蜓肆，6+(-3)的反碼表示為00000110 + 11111100 = 100000010颜凯，最高位符號(hào)位溢出舍掉，即00000010 = 2 仗扬，因?yàn)樯釛壓蟮淖罡呶皇?症概，所以不需要再取反恢復(fù)成原碼，但這也不是正確結(jié)果3早芭，但是他們之間好像有點(diǎn)聯(lián)系彼城，-3原碼10000011和其反碼11111100，一個(gè)是-3，一個(gè)是-124募壕，很多資料都是在補(bǔ)碼的時(shí)候引入<font color="red">“同余”</font>的概念调炬，但我覺(jué)得在反碼的時(shí)候引入更合理，因?yàn)樵谖铱催^(guò)一些資料之后舱馅，我還是不明白為什么是從反碼過(guò)渡到補(bǔ)碼而不是直接從原碼到補(bǔ)碼缰泡。

  • 同余和模的概念

    那同余的概念就是兩個(gè)數(shù)對(duì)同一個(gè)固定的值取余的結(jié)果是一樣的，則說(shuō)明這兩個(gè)值是同余的關(guān)系代嗤，這里的固定值通常是指一個(gè)系統(tǒng)中的最大值匀谣，類比生活中的鐘表，在鐘表系統(tǒng)中资溃，最大值就是12，過(guò)了十二就又會(huì)從1開始烈炭，如果此時(shí)的時(shí)間是3點(diǎn)整溶锭，那么要修改成6點(diǎn)有兩種方式，一種是順時(shí)針撥到6點(diǎn)符隙，此時(shí)指針走了3圈趴捅，另一種是逆時(shí)針撥到6點(diǎn)，此時(shí)指針走了9圈霹疫，那么3和9就是對(duì)于12的一對(duì)同余數(shù)拱绑，12就是這個(gè)系統(tǒng)的模。

  • 思想帶入二進(jìn)制

    回到八位二進(jìn)制丽蝎，因?yàn)榘宋欢M(jìn)制的最高位是符號(hào)位猎拨，所以它的真值表示范圍就是-127～127（即11111111～01111111），負(fù)數(shù)范圍相當(dāng)于逆時(shí)針屠阻，正數(shù)范圍相當(dāng)于順時(shí)針红省，所以它的模應(yīng)該是127，但并不是国觉，因?yàn)橄鄬?duì)于鐘表吧恃，它多了一個(gè)0，鐘表的12就等于0麻诀，0就等于12痕寓，所以它的模就是12，而這里的八位二進(jìn)制的0和127不表示同一個(gè)值蝇闭，所以它的模應(yīng)該是127+1 = 128呻率。

  • 按位取反就是得到同余數(shù)

    前面的-3和-124就是原碼反碼的關(guān)系，按照鐘表環(huán)形系統(tǒng)的模定義來(lái)說(shuō)丁眼，把0和-127兩端連接起來(lái)筷凤，這個(gè)點(diǎn)假設(shè)叫x，那-3到x的距離在兩個(gè)方向上的前進(jìn)步徑分別是-3和124（這里假設(shè)-3、-2藐守、-1挪丢、0的方向是負(fù)方向，-3卢厂、-4乾蓬、-5...-127的方向是正方向），所以按位取反就是取得同余數(shù)的絕對(duì)值慎恒。

  經(jīng)過(guò)上面的分析任内，那么上面的-3的反碼-124少加個(gè)一個(gè)值（0），所以應(yīng)該是-125融柬，也就是11111101死嗦，那最后的結(jié)果就是00000011 = 3，這正是我們的正確結(jié)果粒氧。

• 補(bǔ)碼

  正數(shù)的補(bǔ)碼是它本身越除，負(fù)數(shù)的補(bǔ)碼等于其反碼+1，之所以加1就是因?yàn)槎M(jìn)制和鐘表不一樣的它是線性結(jié)構(gòu)外盯，-127和0不是同一個(gè)值摘盆，所以我覺(jué)得補(bǔ)碼的補(bǔ)在于補(bǔ)差的那個(gè)0，同余的概念應(yīng)該存在于反碼的按位取反中饱苟，負(fù)數(shù)x的補(bǔ)碼的絕對(duì)值也就是2的n次冪+x（注意x是負(fù)數(shù)）孩擂。

邏輯位運(yùn)算符&、|箱熬、～类垦、^、<<坦弟、>>

在很多源碼的閱讀中护锤，較深入的部分、接近底層的部分都會(huì)看到一些二進(jìn)制中的邏輯運(yùn)算符酿傍，有的時(shí)候簡(jiǎn)單的邏輯運(yùn)算符就能表達(dá)一種動(dòng)作烙懦、一個(gè)含義，出于求知欲赤炒，這里整理一下基本的邏輯運(yùn)算符的意義和在開發(fā)中他們通常來(lái)做些什么氯析。

• 與運(yùn)算‘&’

  兩個(gè)二進(jìn)制位相與，二者都為1的時(shí)候才得1莺褒，比如1101&0111 = 0101掩缓。

• 或運(yùn)算‘|’

  兩個(gè)二進(jìn)制位相或，有一個(gè)為1即得1遵岩，比如1101 | 0001 = 1101你辣。

• 異或運(yùn)算‘^’

  兩個(gè)二進(jìn)制位異或運(yùn)算巡通，二者不同才得1，比如1101 ^ 0111 = 1010舍哄。

• 非運(yùn)算‘～’

  單目運(yùn)算符宴凉，一個(gè)二進(jìn)制位非運(yùn)算，本以為是按位取反表悬，其實(shí)并沒(méi)有這么簡(jiǎn)單弥锄，c語(yǔ)言中unsigned修飾的整型非運(yùn)算就相當(dāng)于按位取反，但是對(duì)于非unsigned修飾的整數(shù)來(lái)講蟆沫，比如java中的整型都是有符號(hào)的籽暇，這些有符號(hào)的整數(shù)進(jìn)行非運(yùn)算的結(jié)果卻別有洞天，比如在java中～5得到的卻是-6饭庞，而按照按位取反的邏輯它應(yīng)該是010=2戒悠。

  原因在于無(wú)符號(hào)的數(shù)都是正數(shù)，相當(dāng)于你取反的值就是你的真值舟山，但是有符號(hào)數(shù)的運(yùn)算是帶著符號(hào)位一起做的救崔，比如說(shuō)有符號(hào)數(shù)5，二進(jìn)制應(yīng)該是0101捏顺，最高位0代表正數(shù)，～運(yùn)算會(huì)轉(zhuǎn)成1010纬黎，因?yàn)槭钦龜?shù)幅骄，所以補(bǔ)碼也是這個(gè)，計(jì)算機(jī)的有符號(hào)數(shù)都是通過(guò)補(bǔ)碼運(yùn)算的本今，無(wú)論是不是負(fù)數(shù)拆座，所以這里會(huì)把1010當(dāng)成負(fù)數(shù)補(bǔ)碼對(duì)待，那它的真值就是1110=-6冠息，這就是～5 = -6的由來(lái)挪凑。

• 左移‘<<’

  二進(jìn)制所有位整體左移若干位，若高位溢出則舍棄逛艰，低位補(bǔ)0躏碳。

  比如5 << 1= 101 << 1 = 1010 = 10，可以發(fā)現(xiàn)這里的10是5的2倍散怖，101 << 2 = 10100 = 20菇绵，所以左移n位就是擴(kuò)大至原來(lái)的2的n次冪倍。

• 右移‘>>’

  和左移相反镇眷，整體右移n位咬最，數(shù)值減小2的n次冪，如果是正數(shù)欠动，左邊補(bǔ)0永乌，如果是負(fù)數(shù)左邊補(bǔ)1，因?yàn)槭钦停詴?huì)舍棄小數(shù)點(diǎn)后面的翅雏，譬如5>>1 = 101>>1=10 = 2圈驼。

• 無(wú)符號(hào)右移‘>>>’

  相比于>>，不同的是左邊都是補(bǔ)0枚荣。

• 實(shí)際開發(fā)場(chǎng)景應(yīng)用

  現(xiàn)在考慮一個(gè)場(chǎng)景碗脊，Java中有4個(gè)int型變量NONE = 0 = 00、A = 1 = 01橄妆、B = 2 = 10衙伶、ANY = 3 = 11，他們分別代表不同的模式害碾，可能需要通過(guò)switch根據(jù)這個(gè)模式去做不同的事情矢劲，ANY = A | B，NONE = A & B慌随，那么假設(shè)現(xiàn)在傳進(jìn)來(lái)一個(gè)mode是x芬沉，我們要求x是A或者ANY，那么可以通過(guò)x & A 阁猜！= 0 來(lái)確定丸逸。這種方式就是通過(guò)按照不同的二進(jìn)制位來(lái)代表不同的東西，通過(guò)邏輯運(yùn)算判斷屬不屬于剃袍。

  實(shí)際RxJava中requestFusion用到了這種方式：

  @Override
  public int requestFusion(int mode) {
      if ((mode & ASYNC) != 0) {
          outputFused = true;
          return ASYNC;
      }
      return NONE;
  }
  

• LeetCode中的一個(gè)題

  給定一個(gè)包含n+1個(gè)整數(shù)的數(shù)組黄刚，其數(shù)字在1到n之間，內(nèi)部存在唯一的一個(gè)重復(fù)數(shù)民效，請(qǐng)找出它憔维。

  做法有很多種，我們這里使用位運(yùn)算符來(lái)做：

  int test(int[] nums){
    int base = 0;
    for(i : nums){
      if(base == (base | (1 << i)))
        return i;
      base |= (1 << i);
    }
  }
  

  首先從第一個(gè)元素開始畏邢，比如是3业扒，則1<<3 = 1000，base|1000 = 1000舒萎，不相等程储，所以base = 1000，此時(shí)第4位已經(jīng)是1了臂寝，表示這個(gè)位置有過(guò)記錄了虱肄，假如再次讀到3的時(shí)候，還是只是會(huì)在第4位變成1交煞，也就是說(shuō)讀到重復(fù)數(shù)的時(shí)候咏窿，同樣位置的二進(jìn)制位已經(jīng)變成過(guò)1了，base | (1 << i)和之前的base才會(huì)相同素征。