2022q1 Homework4 (quiz4)

contribute by < Korin777 >

測驗一

int ceil_log2(uint32_t x)
{
    uint32_t r, shift;

    x--;
    r = (x > 0xFFFF) << 4;                                                                                                                                    
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (r | shift | x >> 1) + 1;       
}

• 此函式要求
  $\lceil lo{g}_2(x)\rceil$
• 先將 x-- ， 避免最後向上取整時 ， 當
  $\lceil lo{g}_2(x)\rceil$ =
  $\lfloor lo{g}_2(x)\rfloor$ ， 我們算出來的
  $\lceil lo{g}_2(x)\rceil$ 會多 1
• 2 進位表示中最高位為 1 之 bit 的位置(此位置從 0 開始)就是
  $\lfloor lo{g}_2(x)\rfloor$) ， 函式的第 6 行到第 15 行還有 EXP1 就是在求它
  eg : 對照
  ${39}_{10}={00100111}_2$
  x-- =>
  ${00100110}_2$
  0010 | 0110 => x > 0xf , x >> 4 , r = 0 + 4 = 4 => 0010
  00 | 10 => x <= 0x3 => 10
  10 => r + x >> 1 = 4 + 1 = 5
  向上取整 5 + 1 = 6

測驗二

#define BITS_PER_BYTE 8
#define BITS_PER_LONG (sizeof(unsigned long) * BITS_PER_BYTE)

#include <stddef.h>

static inline size_t ffs(unsigned long x)
{
    if (x == 0)
        return 0;

    size_t o = 1;
    unsigned long t = ~0UL;
    size_t shift = BITS_PER_LONG;

    shift >>= 1;
    t >>= shift;

    while (shift) {
        if ((x & t) == 0) {
            x >>= shift;
            o += shift;
        }

        shift >>= 1;
        t >>= shift;
    }

    return o;
}

• Find first set: 找出最低位且為 1 的 bit 位置 ， 此位置從 1 開始
• 題目透過二分搜來找出最低位的 1 的位置 ， 將 x 尚未檢查過的 bit 分為左右兩半 ， 並檢查右半邊是否有 bit 為 1 來判斷 first set 在左半邊還右半邊 ， 如果在左半邊的話 o 會加上 shift(即 first set 所在位置至少會大於右半邊檢查過的 bit) ， 重複此動作直到 尚未檢查的 bit 只剩一個
  e.g : 對照
  ${74}_{10}={01001010}_2$
  0100 | 1010 => first set 在右半邊 ， 檢查右半邊 => 1010
  10 | 10 => first set 在右半邊 ， 檢查右半邊 => 10
  1 | 0 => first set 在左半邊 ， 檢查左半邊 ， o = 1 + 1 = 2 => 1 ， 尚未檢查的 bit 只剩一個 ， 函式結束

第 4 週測驗題