---
tags: NCKU Linux Kernel Internals, C語言
---
# C 語言： bitwise 操作
[你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)
## bit-wise operator
* 搭配[C語言：數值系統篇](https://hackmd.io/@RinHizakura/HJ0rPhxyD)一同服用
### Shift operator
Shift operator的兩種undefined behavior
* 左移超過變數長度，其結果未定義
```c=
int i=0xFFFFFFFF;
i = i << 32; // 此結果未定義
```
* 右移一個負數時，可能是邏輯位移或是算術位移，C 語言標準未定義;
* `0b1000 >> 1` = `0b1100` or `0b0100` ?
* 有些編譯器可以有編譯選項可改變此語意，gcc 的實作上是使用 arithmetic shift。
### Unsigned and signed
* 當unsigned與singed混合在 C 語言中的單一表示式時，signed會被轉換為unsigned。
* 因此，執行這個程式得到的結果為1。
``` c=
#include <stdio.h>
int main()
{
signed int a = -1;
unsigned int b = 5;
printf("%d",a > b);
return 0;
}
```
* 這個程式是一個無限迴圈。問題發生在`sizeof`雖然看起來像是一個function，但其實是operator!
* [sizeof 在語言層面的陷阱](http://blog.linux.org.tw/~jserv/archives/001876.html)
* 程式設計者預期的應該是i = 0的時候，0 - 1 < 0會跳出迴圈。
* 然而，sizeof(char)會得到 unsigned int 型態的數值，導致i 變數也會被轉換為 unsigned 的形式，無號數 0 再減 1 就會變為 0xFFFFFFFF 而產生無窮迴圈。
```c=
int n = 10;
for (int i = n - 1 ; i - sizeof(char) >= 0; i--)
printf("i: 0x%x\n",i);
```
## bitwise 練習題
趕快來運轉一下腦袋！
### [2018q1 第 1 週測驗題](https://hackmd.io/@sysprog/rJh9U4Guf?type=view)
[參考解答](https://hackmd.io/@jD9XFdyQS0iyAaFMPYi5Ww/S1f0tSyTG?type=view)
#### 測驗`1`
考慮以下程式碼:
```c=
#include <stdlib.h>
int isMultN(unsigned int n) {
int odd_c = 0, even_c = 0; /* variables to count odd and even SET bits */
if (n == 0) // return true if difference is 0.
return 1;
if (n == 1) // return false if the difference is not 0.
return 0;
while (n) {
if (n & 1) // odd bit is SET, increment odd_C
odd_c++;
n >>= 1;
if (n & 1) // even bit is SET, increment even_c
even_c++;
n = n >> 1;
}
/* Recursive call till you get 0/1 */
return(isMultN(abs(odd_c - even_c)));
}
```
其作用為檢查輸入整數是否為 N 的倍數，那麼 N 為多少？
Ans: 3
解法：
* ~~因為原題是選擇題直接把數字代下去用刪去法~~
* 從程式內容可以看出，要算的東西是N的二進位表示中`奇數的1和偶數的1的差距`
* 回傳的true的條件是: 上述的差距必須是0，或者差距是N的倍數
* 透過這個條件代入一些數字去考慮，不難發現N = 3
* 要逆回去推理為甚麼會這樣，我們可以思考二進位中1放在奇數或偶數位置的區別:
* 2進位表示法中，奇數的1表示1、4、16...，對應a0 = 1、a1 = 4、a2 = 16...ai = 3pi + **1**
* 2進位表示法中，偶數的1表示2、8、32...，對應a0 = 2、a1 = 8、a3 = 32...aj = 3pj + **2**
* 因此只要考慮怎麼把**1**跟**2**搭配成3的倍數即可
* 則搭配的方法就是奇數的1比偶數的1少/多3的倍數個，或者相同。
:::info
:bell:
如果我表達的太差搞不懂，或者想了解延伸問題的解答，請看[參考解答](https://hackmd.io/@jD9XFdyQS0iyAaFMPYi5Ww/S1f0tSyTG?type=view)。
:::
#### 測驗 `2`
給定 B 為 2 的某次方 (power of 2)，那麼是否 A % B 等價於 (A & (B - 1))?
Ans: 是
* 若B = 2^N，則A % B就是A的後N個bits
* (B-1)即是後N個bits為1，其他bits為0的mask，因此&之等價A % B
#### 測驗 `3`
在 C 程式中，表達式 1 << 2 + 3 << 4 求值後為何？
Ans: 1 << 5 << 4 = 512
* 得知道是 `<<` 先算還是 `+` 先算。最輕鬆的方法就是直接google。
* 為了避免google騙你，我們應該透過[規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)來了解。在頁碼67頁提到:
> The syntax specifies the precedence of operators in the evaluation of an expression, which is the same as the order of the major subclauses of this subclause, highest precedence first.
* 也就是說，規格書先寫的優先權最高，照順序翻下來 `+` 的優先權比較高。
#### 測驗 `4`
考慮某些硬體平台執行乘法的時間較長，我們會以 (x << 5) - (x) 取代 * 31，那麼 * (-6) 該如何用 shift 搭配 add/sub 實作呢？
Ans: 2 個 shift 搭配 1 個 add/sub
* (-6) 可以寫成 (2 - 8)，及 (x << 1) - ( x << 3)
#### 測驗 `5`
考慮以下整數乘法的實作程式碼:
```c=
int mul(int n, int m) {
int ret = 0;
for (int c = 0; m; c++, m /= 2)
if (!(m % 2 - 1)) OP
return ret;
}
```
上述 OP 對應到下方哪個程式敘述呢？
ANS: ret += n << c
* 即把m拆成2^n的組合一個一個乘。舉例來說 * 7 可以拆成 * (4 + 2 + 1)
:::warning
需注意當m<0時會有問題! 規格書的82頁說:
> When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a
也就是說a % b = a - (a / b) * b。當m為負時，`m - ( m / 2) * 2`只能得到0或-1，則if內的指令不會被執行，行為與預期的會有不符。
當然要使m<0也可以運行也很簡單，加上額外的branch處理即可。
:::
### [2018q3 第 1 週測驗題](https://hackmd.io/@sysprog/S1a9-YO_Q?type=view)
[參考解答](https://hackmd.io/@rhFNoUDRQZGzNV1UYUBUxg/By5KCaZam?type=view)
#### 測驗 `1`
考慮以下程式碼:
```c=
int my_xor(int x, int y) { return (x | y) OP1 (OP2 x OP3 OP4 y); }
int main() {
int x = 3, y = 5;
return my_xor(x, y);
}
```
my_xor 嘗試不用 XOR 運算子做出等效的 XOR 運算，其中 OP1, OP2, OP3, OP4 都是 operator，請補完實作。
Ans: x ^ y = (x | y) & (~x | ~y)
* ~~OP2跟OP4超明顯只能填~~~
* 我們可以從OR跟XOR的真值表去思考，其實有差的地方只有1 | 1 = 1跟1 XOR 1 = 0
* 也就是`A XOR B` = `A | B 的結果，再把原本A、B中位元都是1的位置變成0`
* 而A、B中位元都是1的位置用A & B就可以知道了
* 因此就可以推理出 `A XOR B` = `(A | B) & (~(A & B))`
* 再套用迪摩根，就可以得到 `A XOR B` = `(A | B) & (~A | ~B))`
#### 測驗 `2`
(原題敘述介紹parity bit的意思與作用，請直接參照)
考慮到以下判斷 parity bit 的程式碼
```c=
#include <stdio.h>
/* Generate look-up table while pre-processing */
#define P2(n) n, n ^ 1, n ^ 1, n
#define P4(n) P2(n), P2(n ^ 1), P2(n ^ 1), P2(n)
#define P6(n) P4(n), P4(n ^ 1), P4(n ^ 1), P4(n)
#define LOOK_UP P6(0), P6(1), P6(1), P6(0)
/* LOOK_UP is the macro expansion to generate table */
unsigned int table[256] = { LOOK_UP };
int parity(int num) {
/* Number is considered to be of 32 bits */
int max = 16;
// Dividing the number into 8-bit
// chunks while performing XOR
while (max >= 8) {
num = num ^ (num >> max);
max /= N;
}
// Masking the number with 0xff (11111111)
// to produce valid 8-bit result
return table[num & 0xff];
}
int main() {
unsigned int num = 1742346774;
/* Result is 1 for odd parity, 0 for even parity */
int result = parity(num);
printf("%s parity\n", parity(num) ? "odd" : "even");
return 0;
}
```
補完程式碼。
Ans: N = 2
* 判斷奇數個1還是偶數個1，其實就是把所有的bits做XOR運算!
* 因此while迴圈中要做的事就是:`每個iteration把bit兩兩配對XOR，直到所有的bits XOR 在最後8bits，再去查表`，N = 2。
* P2(0) = 0、1、1、0，對應到的就是用2bits表示的0b00、0b01、0b10、0b11該return的值。對應增加bits該return值的規律遞迴，就是LOOK_UP的作用。
* [參考解答](https://hackmd.io/@rhFNoUDRQZGzNV1UYUBUxg/By5KCaZam?type=view)有圖解，應該會更容易了解。
### [2019q1 第 1 週測驗題](https://hackmd.io/@sysprog/SyrZMGYr4)
[參考解答](https://hackmd.io/@chenishi/S1DHQ3KrE)
#### 測驗 `1`
透過 bitwise 演算法 改寫為以下 C 程式:
#include <stdio.h>
```c=
#include <stdlib.h>
static int sol_count = 0;
void recursive_solver(int row, int maj_con, int min_con, int col_con, int n)
{
int queen_position;
int conflicts = min_con | maj_con | col_con;
int i = 0;
min_con &= 65535;
while (i < n) {
queen_position = 1 << (A1 - i);
if (!(queen_position & conflicts)) {
if (row == n - 1)
sol_count++;
else
recursive_solver(row + A2, (maj_con | queen_position) >> A3,
(min_con | queen_position) << A4,
col_con | queen_position, n);
}
i++;
}
}
void solve_queens(int n)
{
int minor_dconflict = 0, major_dconflict = 0, column_conflict = 0;
recursive_solver(0, column_conflict, major_dconflict, minor_dconflict, n);
printf("solutions = %d\n", sol_count);
}
```
Ans: `A1 = 16, A2 = 1, A3 = 1, A4 = 1`
透過一個4 * 4的棋盤來思考一下程式的邏輯:
初始的maj_con, min_con, col_con都是0b0000。首先，把旗子放在第一個row的第一個column。所以queen_position是0b1000
接著，我們要移動到下一個row，然後從第一個column開始搜尋，因此需要更新專屬於這個row的mask。
對於這個row來說:
* 第1個column不能放，即col_con = 0b1000 即 col_con = (col_con | queen_position)
* 在`/`方向上，所有位置都可以放，因此min_con = 0b0000 即 min_con = (min_con | queen_position) << 1
* 在`\`方向上，第二個column不能放，即maj_con = 0b0100 即 maj_con = (maj_con | queen_position) >> 1
移動到下一個row後，透過mask我們知道棋子要放在第三個column，對應的queen_position是0b0010。
然後和前面相同: 更新專屬於下一個row的mask。
* 第1、3個column不能放，即col_con = 0b1010 即 col_con = (col_con | queen_position)
* 第2個column不能放，即maj_con = 0b0100 即 min_con = (min_con | queen_position) << 1
* 第3、4個column不能放，即 min_con = 0b0011 即 maj_con = (maj_con | queen_position) >> 1
循著相同的步驟，就可以遞迴求解。
#### 測驗 `2`
考慮到以下程式碼:
```c=
#include <stdint.h>
#define ALIGN_uint32(x, a) __ALIGN_MASK(x, ((uint32_t)(a)) - 1)
#define __ALIGN_MASK(x, mask) (((x) + (mask)) & ~(mask))
```
考慮 4-byte boundary，當 x 是 0x1006, a 是 4, 那麼 ALIGN(x, a) 會得到什麼數值？
Ans: X = 0x1008
* 0x1000是一個aligned的數字，因此事實上只要考慮`0x6 = 0b0110`的aligned
* mask = 3 - 1 = 0b0011
* `(0b0110 + 0b0011) & (0b1100) = 0b1000 = 0x8`
### [2019q1 第 2 週測驗題](https://hackmd.io/@sysprog/H1Pik8M8E)
[參考解答](https://hackmd.io/@1IzBzEXXRsmj6-nLXZ9opw/B1vrcKcu4#%E7%AC%AC-2-%E9%80%B1%E6%B8%AC%E9%A9%97-2)
#### 測驗 `1`
考慮以下程式碼，回傳給定整數乘上 3.5 的結果:
```c=
int mul3_5(int x) {
return (((8 A x) B x ) C 1);
}
```
請補完。A, B, C 都是 operator。
Ans: A = *, B = -, C = >>
#### 測驗 `2`
[population count](https://en.wikichip.org/wiki/population_count)對應到 C 程式的實作:
```c=
unsigned popcnt_naive(unsigned v) {
unsigned n = 0;
while (v)
v &= (v - 1), n = -(~n);
return n;
}
```
可改寫為以下常數時間的實作:
```c=
unsigned popcnt(unsigned v)
{
unsigned n;
n = (v >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
v = (v + (v >> X)) & Y;
v *= 0x01010101;
return v >> 24;
}
```
請補完。
Ans: X = 4, Y = 0x0F0F0F0F
* `v &= (v - 1)`有沒有覺得熟悉? 之前曾經提過其功能是**把二進位表示中最靠右邊位的1變成0**
* -n = ~(n) + 1，所以 -(~n)其實就是n = n + 1
::: warning
我解不出來QQ 請直接閱讀[參考解答](https://hackmd.io/@1IzBzEXXRsmj6-nLXZ9opw/B1vrcKcu4#%E7%AC%AC-2-%E9%80%B1%E6%B8%AC%E9%A9%97-2)
:::
#### 測驗 `3`
考慮以下程式碼:
```c=
#include <stdio.h>
#define cons(x, y) E
struct llist { int val; struct llist *next; };
int main() {
struct llist *list = cons(9, cons(5, cons(4, cons(7, NULL))));
struct llist *p = list;
for (; p; p = p->next)
printf("%d", p->val);
printf("\n");
return 0;
}
```
預期執行時期輸出 9547，補完 E。
Ans: E = `(struct llist[]){{x, y}}`
(d)選項的寫法應該修正成`&(struct llist){.val = x, .next = y}`或者`&(struct llist){x, y}`。
Sign in with Wallet
Connect another wallet