HackMD
2022q2 Homework (quiz4)
contributed by <ray90514>
測驗1
求 log2 相當於求最高位的 1 在第幾位，以 uint32_t 為例，如果某數 x 最高位的 1 在高16位，則該數會大於 0xFFFF ，最高位的 1 會在 16 + n 位，這個 n 用二分搜尋法對 x 以同樣的方法求得。因為是求 ceil 所以結果要 +1 ，對於特殊情況也就是 2 的冪則是一開始先減一處理。
這段程式碼照邏輯少了以下
r |= shift;
shift = x > 0x1;
r |= shift
合併之後為 r | shift | x >> 1 ，因為此時 x 的值只可能是 0 ~ 3 ， x > 0x1 可用 x >> 1 取代。
測驗2
程式的運作為二分搜尋，使用一個可以取得右半邊的值的 bitmask t ，如果 x 最低位的 1 在右半邊，則 x & t 非 0 ，反之，若該值為 0 ，則最低位的 1 會在 shift + n 。因此 EXP2 為 x & t ， EXP3 為 o += shift 。
改進
#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 = 0;
size_t shift;
shift = ((x & 0xFFFF) == 0) << 4;
x >>= shift;
o |= shift;
shift = ((x & 0xFF) == 0) << 3;
x >>= shift;
o |= shift;
shift = ((x & 0xF) == 0) << 2;
x >>= shift;
o |= shift;
shift = ((x & 0x3) == 0) << 1;
return (o | shift | !(x & 0x1)) + 1;
}
測驗3
con 是一個指向指標的指標，在走訪的過程中他會指向節點的 next 指標，所以 EXP4 為 &(*con)->next。當條件成立時，這個 next 指標指向要被移除節點，將該 next 指標指向要被移除節點的 next ，就可將該節點移除。因此 EXP5 為 fc->next
