---
# System prepended metadata

title: 位元運算
tags: [C++Book]

---

# 位元運算
###### 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/)

