2023q1 Homework2 (quiz2)

contributed by < DokiDokiPB >

測驗 1

重新梳理 next_pow 數值

• next_pow2(7) = 8
• next_pow2(8) = 16
• next_pow2(42) = 64

這裡有個疑問是：輸入數值只能小於 0x8000000000000000，最高位元必須為 0，沒有定義大於此數值應該輸出什麼？

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 >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return x + 1;
}

直覺想到思路可以寫為：

uint64_t next_pow2(uint64_t x)
{
    for(int i = 0; i < 63; i++){
        x |= x >> 1;
    }
    return x + 1;
}

假設變數

$x$ 的設定為 1 的最高位元為

$y_1$，每個被設定 1 的位元為

$y_1$,

$y_2$,

$y_3$ …

$y_i$,

$1\le i<64$，next_pow(x) 的最高有效位元為

$y_0$
每次 x |= x >> 1; 相當於每個

$y_i$ 向右傳播一次，最終，從

$y_1$ 到最低位元皆為 1，再加上 1，即獲得

$y_0$

另外，可以把程式碼改成以下形式

uint64_t next_pow2(uint64_t x)
{
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return x + 1;
}

延伸問題

使用 __builtin_clzl 改寫

在原本的函式中

• 輸入 0 會獲得 1
• 沒有定義 0x8000000000000000 以上會發生什麼事情

於是改寫成：

uint64_t next_pow2(uint64_t x)
{
    if (!x) {
        return 1;
    }
    int clz = __builtin_clzl(x);
    return 0x8000000000000000 >> (clz - 1);
}

在 C99 規格書中

6.5.7 Bitwise shift operators
The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

如果 shift count 為負數，會有未定義行為

考量了 right shift 有未定義行為，改寫成：

uint64_t next_pow2(uint64_t x)
{
    if (!x) {
        return 1;
    }
    int l = 64 - __builtin_clzl(x);
    /* 一定要 1UL */
    return 1UL << l;
}

當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？

cc -O2 -std=c99 -S next_pow2.c
擷取部份組合語言

next_pow2:
.LFB0:
	.cfi_startproc
	endbr64
	movl	$1, %eax
	testq	%rdi, %rdi
	je	.L1
	bsrq	%rdi, %rdi
	movl	$64, %ecx
	xorq	$63, %rdi
	subl	%edi, %ecx
	sall	%cl, %eax
	cltq

---

測驗 2

取自 LeetCode 1680. Concatenation of Consecutive Binary Numbers

int concatenatedBinary(int n)
{
    const int M = 1e9 + 7;
    int len = 0;
    long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!(i & (i - 1)))
            len++;
        ans = (i | (ans << len)) % M;
    }
    return ans;
}

將變數 i 與變數 len 之間的關係列出來，會發現每次 len++ 發生在 i 為 2 的冪：

i   binary   len  !(i & (i - 1))
1   0b   1    1         1
2   0b  10    2         1
3   0b  11    2         0
4   0b 100    3         0
5   0b 101    3         0
6   0b 110    3         0
7   0b 111    3         0
8   0b1000    4         1

i & (i - 1) 可用來移除最低位元的 1。

嘗試使用 __builtin_{clz,ctz,ffs} 改寫，並改進取餘數的運算

第一個想法是可以將分支 (branch) 移除

len += !(i & (i - 1));

有些線索可以去思考

• const int M = 1e9 + 7; 是質數
• (i | (ans << len)) % M; 可化為 ((i % M) + (ans << len) % M) % M

很好，你發現質數這個重要屬性，接著要搭配數論去思考，參見 Modulo a Prime Number
jserv

想了幾種可能性：

• 第一種是輸入參數 n 足夠大令與 n 的差距大的數字可忽略；不過比對 n = 1023 的輸出數值是錯的
  • 例如 __builtin__clz(n) = 22; // 512 <= n <= 1023，考量輸出為 32 位元的整數可以想成，只要考量附近的數字

n = 1023
i    1020  1021 1022 1023
bits    2    10   10   10

• 第二種是考量 ((i % M) + (ans << len) % M) % M，其中的 ans << len，可以經由手算出 2 的乘法反元素，可算出
  $ans\times 2^{len}\equiv ans/2^{-1}(mod{10}^9+7)$，不過還是牽涉到除法
• 第三種建立表格，建立 0 ~ 10e9 + 6 對應的乘法反元素；不過輸入甚麼輸出固定，也可以很乾脆建立表格。

---

測驗 4

以正規表達式顯示符合的二進制表示字串：

$1^{\ast }{0}^{\ast }$ ，例如：

$0b1000$,

$0b1100$,

$0b1110$,

$0b1111$

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

目前想到的是，先將套用數值進去，查看數值間的關係：

• 若變數
  $x$ 符合
  $1^{\ast }{0}^{\ast }$
  • ~x 變為
    $0^{\ast }{1}^{\ast }$
  • ~x + 1 會變為 2 的冪，只有一個位元被設定為 1，且此位元位置與
    $x$ 的最低有效位元位置相同
  • n ^ x 會設定該相同位置的位元為 0
  • n < x 成立
• 若變數
  $x$ 不符合
  $1^{\ast }{0}^{\ast }$
  • ~x + 1 不會是 2 的冪
  • n ^ x 產生大於 x 的數值