# 位元運算 ###### tags: `C++Book` ## 負數表示 :::info **補數** 補數(Complement)：是指兩數字加起來等於某數時，則二數互為某數的補數。 例如3的10補數為7，7的10補數為3。 ::: ### 1的補數(1‘ Complement): :::info 指兩數的和為每個bit 為 1，則此兩數互為1 的補數，即1和0互為1的補數。 ::: ==即將原數的0變1，1變0,即為 ~b == | 原數為 | 1 | 0 | 1 | 1 | 0 | 1 | |---|---|---|---|---|---|---|---| | 1補數為 | 0 | 1 | 0 | 0 | 1 | 0 | ### 2的補數(2’ Complement)： :::info 指二兩數的和使每一位均為0而產生溢位(進位)。 ::: ==先取該數的1補數，再加1即可,即為 -x+1== | 原數為 | 0 | 1 | 1 | 0 | 1 | |---|---|---|---|---|---|---| | 1補數為 | 1 | 0 | 0 | 1 | 0 | | 1的補數再加1 | 1 | 0 | 0 | 1 | 1 | 數x加數x的1補數 →.....1111111 再加1 → 全部進位 ### MSB :::info 符號位元 ::: 補數系統裡是將 MSB (最左邊的位元)，表示符號位元，剩下的位元才拿來算值，是負數才須要轉補數。 將 MSB 符號位元視為區別到底「此數為正數」還是「此數為某數的某種補數」。 ## 奇數判斷 運用位元遮罩,右邊的1 → 00000...001 x除了最後一個位元都會被 _ and 0遮罩掉 ```cpp (x & 1)//如果是奇數值是true ``` ## 二的次冪 **2nx** ```cpp x << n ``` 利用左移運算，即可輕易將整數 x 乘以 2^n。 **x/2n** ``` cpp x >> n ``` 利用右移運算，即可輕易將整數 x 除以 2n。需要注意的是，該除法會**直接捨去浮點數部分**。 :::warning 注意overflow ::: ## 末端連續N個1 ```cpp (1 << n) - 1 ``` ## 尋找最低位的1 ```cpp x & -x ``` **對任何數加上 1，在位元的意義即為將最低位的位元 0 變為位元 1，且低於該位的位元1都將被設定為 0** `ex 011111 + 1 → 100000` x的最低位1為 & (~x的最低位0 →通過+1變成 1) → 只有最低位1為1,其餘為零(高於最低1的不會被改,一定是0) x=10100 ~x=01011 -x=01==1==00 x&-x=00100 ### 是否為二的次冪 ```cpp (x & -x) == x ``` 如果只有1個1,那最低1必定為他本身 ## 將第n個位元設定為1 or 0 ```cpp x|(1<<n) x&~(1<<n) ``` ## 整數交換 ```cpp x^=y^=x^=y ``` 拆開來看即為： ```cpp x = x ^ y; y = y ^ x;...(1) x = x ^ y;...(2) ``` 這個方法基於 xor(^) 的特性： - 任何數對本身做 xor 運算都會等於 0 - 任何數對 0 做 xor 運算都會等於本身 令x,y原本的值為x',y' (1)中,y=y'^y'^x', y'^y'必為0,求x'^0 1^0=1,0^0=0,如此y=x' (2)中,x=x'^y'^x',同理x=y' ## 引用 >[https://welkinchen.pixnet.net/blog/post/41360237-%E8%A3%9C%E6%95%B8](https://welkinchen.pixnet.net/blog/post/41360237-%E8%A3%9C%E6%95%B8) >[https://blog.kuoe0.tw/posts/2012/01/26/bitwise-operation-utlization/](https://blog.kuoe0.tw/posts/2012/01/26/bitwise-operation-utlization/)