Try   HackMD

Bitwise Operator的奇淫巧技

tags: NTU-CE Computer Programming Java Programming Language Hacks

在Java舉凡能夠視為整數值的型別(int、long、short、byte、char)變數都可以被轉成二進位制以Bitwise Operator操作,例如

int a=1;
a *= 2;

等價

a <<= 1;

為什麼要用Bitwise Operator?

因為a <<= 1a *= 2快,所以通常越是底層的Library就越常看見開發人員偏好二進位操作,我們不希望一個很基本的函式由於實作方式太耗時間就拖垮了那些使用它的程式。

先備知識

  1. ^ XOR Bitwise Operator:
Operand1Operand2Result
110
000
101
011
  1. & AND Bitwise Operator
Operand1Operand2Result
111
000
100
010
  1. | OR Bitwise Operator
Operand1Operand2Result
111
000
101
011
  1. << Left Shift Operator
    「a<<b」代表a向左移b個位置,其右邊補b個0。

  2. >>> Unsigned (Logical) Right Shift Operator
    「a>>>b」代表a向右移b個位置,其左邊補b個0。

  3. >> Signed (Arithmetic) Right Shift Operator
    「a>>b」代表a向右移b個位置,其左邊補原本最左邊的位元值。

二補數(2's Complement)系統

Java的int變數佔4個byte,也就是32個bit,每個bit上面不是0就是1。
例如

(00000000000000000000000000000001)2=(1)10
(00000000000000000000000000000010)2=(2)10

(00000000000000000000000000000100)2=(4)10

(00000000000000000000000000000111)2=(7)10

聰明如你,那負整數怎麼辦?
所謂的二補數系統,就是在能夠表達負整數的那麼多種系統中的其中一個系統而已。
它的特徵就是把最左邊的位元當作正負號,1代表負數,0代表正數。
例如

(10000000000000000000000000000001)2是負的。
(00000000000000000000000000000001)2
是正的。

再來是知道正負號之後,它的絕對值怎麼算呢?

  • 正整數之前講過了
  • 負整數的遊戲規則就是,遮掉最左邊的負號,把剩下的位元值取補數,再加1
    例如
    (10000000000000000000000000000001)2

    =(1)10×((1111111111111111111111111111110)2+1)

    =(1)10×(21+22+23+...+229+230+1)=2147483647

從二進位的角度,我們可以輕易地猜出int的最大正整數值及最小負整數值。

  • int最大正整數

    (01111111111111111111111111111111)2=2147483647

  • int最小負整數

    (10000000000000000000000000000000)2=(2147483647+1)=2147483648

  • 那0呢?

    (00000000000000000000000000000000)2=0

基本的經典操作

  • 把左移 << 看成是 乘2的幾次方

例如

(00000000000000000000000000000110)2=(6)10
往左移4個位置
(00000000000000000000000001100000)2=(96)10=6×24

但是!!!移過頭就不見了喔
如果把6左移100個位置,答案會是0喔(不會循環的意思)。

  • 把右移 >>> 看成是 除2的幾次方

例如

(00000000000000000000000001100000)2=(96)10
往右移4個位置
(00000000000000000000000000000110)2=(6)10=96÷24

但是!!!失去的不一定能找回來
如果把

(11111000000000000000000000000000)2=134217728
向左移4個位置
(10000000000000000000000000000000)2=2147483648

再向右移4個位置
(00001000000000000000000000000000)2=134217728

答案可是不會變回來的喔

  • 把右移 >> 看成是 除2的幾次方 並且 保留原來的正負號

例如

(11111111111111111111111111111110)2=2
往右移4個位置,右邊再補滿原本的符號,即1(負號)
(11111111111111111111111111111111)2=12÷2

原本是負的右移之後還是負的喔
聰明如你,原本是正的右移之後也會是正的。

進階的經典撥弄

Bit Twiddling Hacks

小工具

進位換算計算機