2023q1 Homework2 (quiz2)

contributed by < Jerejere0808 >

測驗一

將最高位元數下的 bits 改為 1 ，最後再加 1 進位，得到大於其值最接近的2的冪。

AAAA = 1
BBBB = 32
CCCC = x + 1

用 __builtin_clz() 簡化程式碼

#include <stdint.h>
#include <stdio.h>


uint64_t next_pow2(uint64_t x)
{
    int lz  =  __builtin_clz(x);
    return 1 << (64 - lz);
}

        .file   "q1.c"
        .text
        .p2align 4
        .globl  next_pow2
        .type   next_pow2, @function
next_pow2:
.LFB13:
        .cfi_startproc
        endbr64
        bsrl    %edi, %edi
        movl    $64, %ecx
        movl    $1, %eax
        xorl    $31, %edi
        subl    %edi, %ecx
        sall    %cl, %eax
        cltq
        ret
        .cfi_endproc
.LFE13:
        .size   next_pow2, .-next_pow2
        .ident  "GCC: (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.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:

上為產生的 x86 指令 其中指令 "bsrl %edi, %edi" 在暫存器 %edi 的值執行了 bit scan reverse operation ，尋找 %edi 值中最高位的設定位元（即最左邊的1位元），並將其位置存儲在 %edi 中。

在 Linux 核心原始程式碼找出類似的使用案例並解釋:

測驗二

DDD = i & (i - 1) == 0
判斷 i 是否為二的冪，ex: 100 & 011 = 0。 若為真 len 就加一，因為會多出一個bit

EEEE = (ans<<len) 移出 len 個 bits 的空間

用 __builtin_ctz() 改寫，若目前 len 跟 二進位的 i 右側連續的 0 bits 數量一樣就代表 len 必須加一 ans 才可以挪出足夠的空間給二進位的 i (因為i最前面會多出一個 1 bit)

int concatenatedBinary(int n)
{
    const int M = 1e9 + 7;
    int len = 0; /* the bit length to be shifted */

    long ans = 0;
    for (int i = 1; i <= n; i++) {

        len = len + (__builtin_ctz(i) == len);
        ans = (i | (ans<<len)) % M;
    }
    return ans;
}

改進 mod 1e9 + 7 的運算 (還在思考)

測驗三

因為用了 SWAR 增加效率，變成一次處理 64 bits(8 個 bytes)，所以先算最大 8 的倍數的 bytes 數量其已經利用 SWAR 算出 continuation byte(s) 數量 所以 count 就變成總量減去continuation byte(s) 數量也就是去除 continuation byte(s) 的bytes數 剩下不能利用 SWAR 的就使用 count_utf8 求出去除 continuation byte(s) 的bytes數，最後將其相加。
AAAA = 3
BBBB = 7
CCCC = 7

count = (1 << 3) * (len / 8)  - count;
count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;
return count;

在 Linux 核心原始程式碼找出 UTF-8 和 Unicode 相關字串處理的程式碼(還在找應該會從/include/linux/unicode.h 挑選)

測驗四

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

EEEE = ~x + 1
FFFF = x

符合 pattern 的二進位數在有效最大位數一定是 1' bit，且跟最低位的 1 之間不能有 0' bit，如也就是說若出現 1…01…0 這個情況就不符合，~x + 1 會讓 1…01…0 變成 1…11…0 透過(n ^ x) 會變成 1…10…0 會比原本 x 大。若是原本符合 pattern 的 x 透過這個操作就會變小。(想很久= =)