# 2023q1 Homework2 (quiz2)
contributed by <`Urbaner3`>
###### tags: `linux2022` `Linux Kernal`

測驗 `1`
------

uint64_t next_pow2(uint64_t x)
{
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
	x |= x >> 1; /*add a line to make it work*/
    x |= x >> AAAA;
    x |= x >> 16;
    x |= x >> BBBB;
    return CCCC;
}

將 x 右移並與 x 做或運算，會從有1的位數，右移後加回本為零的位數，增加顯示1的位元。題目有提示說到，依次右移1,2,4,8,16,32,64。因為一旦到達指定數字樣式，即1...1，右移多少位元，因為沒有零的位數，數字都不會變，且是我們要的樣式。若不是按照2的等比數列，如1,3,5,...中間會有零的位數，就不是冪減一了，不是全位數1的2進位數。所以 AAAA = 1。 奇怪這樣有落差，少了一行右移一，加入一行。AAAA = 8, BBBB = 32, CCCC = x+1

#### 延伸問題
1. 解釋上述程式碼原理，並用 [`__builtin_clzl`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 改寫
(程式POW)

#include <stdint.h>
static unsigned long int next_pow2(unsigned long int x)
{
    int zs = __builtin_clzl(x); /*zeros;*/
    return 1 << (sizeof(unsigned long int)-zs);
} 

解釋如前段，為了得到相同輸出，直接對1做左移。
2. 在 Linux 核心原始程式碼找出類似的使用案例並解釋
[weak clz/ctz](https://github.com/torvalds/linux/commit/4df87bb7b6a22dfc6fdd5abb3dd362b3af2c164d)

int __weak __clzdi2(long val)
{
	return 64 - fls64((u64)val);
}

[fls64](https://github.com/analogdevicesinc/linux/blob/master/tools/include/asm-generic/bitops/fls64.h) not in <linux/export.h, kernel.h> = linux/include/linux/kernel.h [better eq.](https://www.daemon-systems.org/man/fls64.3.html) 函數回傳由右向左數的非零位數，用64減去該數，得到左邊開始連續0的位數數量。
3. 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？
參考 [aaron](https://hackmd.io/@aaron881011/rkZbh-zyn) ，執行 `cc`

	.file	"next_pow2.c"
	.text
	.ident	"GCC: (Ubuntu 12.2.0-3ubuntu1) 12.2.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:

沒有出現，圖例為對程式POW執行的結果。

測驗 `2`
------
參考[作業](https://hackmd.io/@p4uHLG53RQ2mdlxeWiipWg/linux-2023-quiz2)發現 len 與 i 有關聯，但沒有進一步想到，一起合併，紀錄在 ans 並每次更新，以致於一時之間沒有發現。有些對2進位表示不習慣，我以為還要經過一個函數，有個固定語法的印象，一沒找到就認不出來，沒有想法了。也可說是對串接數字的方式沒有清楚的概念。
[實驗共筆](https://hackmd.io/PO1-iGQfT_OUQSFYUGkLLA?view#%E6%B8%AC%E9%A9%97-3)

測驗 `3`
------
解釋原理：
因為2進位補數 0b10111111 是負數，所以更大的數，數值較小，第六第七位會是後續位元組開頭的樣式。所以用-65當作 magic number 這個演算法可以算出是否為後續位元組。
參考[範本](https://hackmd.io/@willwillhi/quiz2#%E6%B8%AC%E9%A9%97%E4%B8%89)
AAAA=3, BBBB=7, CCCC=7
新演算法把8個數字串在一起，當作一個數字運算，如同題目開頭2數字串接的例子一樣，範本中，使用題目的說法，利用位元運算的性質，反轉再經過 mask 讓其他六位數字歸零，再繼續整理，讓目標樣式輸出一，計算一的數量。 [好解釋](https://hackmd.io/@yanjiew/linux2023q1-quiz2#%E6%B8%AC%E9%A9%97-3)

測驗 `4`
------
參考[列表](https://hackmd.io/@willwillhi/quiz2#%E6%B8%AC%E9%A9%97%E5%9B%9B)

pattern: 0x8000 = 0b1000 0000 0000 0000
pattern: 0xc000 = 0b1100 0000 0000 0000
pattern: 0xe000 = 0b1110 0000 0000 0000
pattern: 0xf000 = 0b1111 0000 0000 0000
pattern: 0xf800 = 0b1111 1000 0000 0000
pattern: 0xfc00 = 0b1111 1100 0000 0000
pattern: 0xfe00 = 0b1111 1110 0000 0000
pattern: 0xff00 = 0b1111 1111 0000 0000
pattern: 0xff80 = 0b1111 1111 1000 0000
pattern: 0xffc0 = 0b1111 1111 1100 0000
pattern: 0xffe0 = 0b1111 1111 1110 0000
pattern: 0xfff0 = 0b1111 1111 1111 0000
pattern: 0xfff8 = 0b1111 1111 1111 1000
pattern: 0xfffc = 0b1111 1111 1111 1100
pattern: 0xfffe = 0b1111 1111 1111 1110
pattern: 0xffff = 0b1111 1111 1111 1111

[同義解](https://hackmd.io/@ItisCaleb/HyTEU5j0i#%E6%B8%AC%E9%A9%97-4)，

bool is_pattern(uint16_t x)
{
    const uint16_t n = ~x+1;
    return (n ^ x) < x;
}

改寫程式碼為 pattern 的生成器：

bool is_pattern(uint16_t x)
{
    int n = __builtin_popcountll(x ^ 0x8000llu);
	uint16_t gen = 0x8000llu;
	for (int i=0; i<n; i++)
		gen |= gen>>1;
	
	return gen;
}

考慮到
0x8000 = $-2^{15}$ (mod $2^{16}$)，每一行都是前一行右移1位元，也就是除以二，這裡要邏輯位移，補上 MSB digit =1，所以新程式碼告訴我們邏輯位移的實做，`x |= x>>1`，我想也是除以2的實做。
x^-x = x<<1 = x * 2 = x - (-x)