Try   HackMD

2024q1 Homework4 (quiz3+4)

contributed by <brian049>

Quiz 3

測驗三

在測驗三當中針對 ilog 有三種版本,第一種版本透過不斷向右位移二進位位元來計算以 2 為底的對數。

int ilog2(int i)
{
    int log = -1;
    while (i) {
        i >>= 1;
        log++;
    }
    return log;
}

第二種版本與第一種版本相似,但是是透過比較較大數字開始,一步一步將二進位位元向右位移到 0。

static size_t ilog2(size_t i)
{
    size_t result = 0;
    while (i >= 65536) {
        result += 16;
        i >>= 16;
    }
    while (i >= 256) {
        result += 8;
        i >>= 8;
    }
    while (i >= 16) {
        result += 4;
        i >>= 4;
    }
    while (i >= 2) {
        result += 1;
        i >>= 1;
    }
    return result;
}

相對於第一種方式,第二種方式較為快速,我透過 Linux shell command time 指令來計算執行時間。

針對兩種方式我透過用兩種測資,一個測資為 65536,另一個測資為 87654321。

$ time ./v1
The logarithm base 2 of 65536 is: 16

real    0m0.006s
user    0m0.002s
sys     0m0.004s

$ time ./v2
ilog2 of 65536 is 16

real    0m0.008s
user    0m0.001s
sys     0m0.007s
$ time ./v1
The logarithm base 2 of 87654321 is: 26

real    0m0.027s
user    0m0.009s
sys     0m0.018s

$ time ./v2
ilog2 of 87654321 is 26

real    0m0.007s
user    0m0.001s
sys     0m0.006s

經過測試發現,若是測資較小,執行時間較無差異,但是若是測資較大,則執行時間差異較大。

第三種方式是透過呼叫 __builtin_clz 巨集來計算在二進位當中最高位元為 1 的位置,來得到以 2 為底的對數。

int ilog32(uint32_t v)
{
    return (31 - __builtin_clz(v | 1));
}

測驗三延伸問題

linux/log2.h 當中有 ilog2 巨集的定義。

其實作的方法是暴力法(Brute force) 從 63 位元開始比對,若是向左位移 63 位元得到 1 時則是 2 的 63 次方,以此類推直到比對到第 2 位元。

/**
 * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
 * @n - parameter
 *
 * constant-capable log of base 2 calculation
 * - this can be used to initialise global variables from constant data, hence
 *   the massive ternary operator construction
 *
 * selects the appropriately-sized optimised version depending on sizeof(n)
 */
#define ilog2(n)				\
(						\
	__builtin_constant_p(n) ? (		\
		(n) < 2 ? 0 :			\
		(n) & (1ULL << 63) ? 63 :	\
		(n) & (1ULL << 62) ? 62 :	\
		...
		(n) & (1ULL <<  4) ?  4 :	\
		(n) & (1ULL <<  3) ?  3 :	\
		(n) & (1ULL <<  2) ?  2 :	\
		1 ) :				\
	(sizeof(n) <= 4) ?			\
	__ilog2_u32(n) :			\
	__ilog2_u64(n)				\
 )

透過 Github 搜尋欄位查詢到在 linux/lib/math/div64.c 當中有應用到 ilog2 這個巨集。

#ifndef mul_u64_u64_div_u64
u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 c)
{
	u64 res = 0, div, rem;
	int shift;

	/* can a * b overflow ? */
	if (ilog2(a) + ilog2(b) > 62) {
        ...

mul_u64_u64_div_u64 函式當中運用 ilog2 巨集來判斷兩數 a, b 是否在相乘之後是否會溢位。

測驗五

測驗五是測驗三的延伸,改變的點是添加了 ceilling 的功能。

int ceil_ilog2(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;       
}

r 以及 shift 是用作紀錄因給定數字 x 分別大於 0xFFFF, 0xFF, 0xF, 0x3 的時候,需要進行下一步判斷需要位移的數量。

其中 r, shift 都是 2 的指數所以 r | shift 就相當於 r + shift

最後的 x > 1 是為了判斷 x 若是大於 1 且小於等於 0x3 時的狀況。

測驗五延伸問題

判斷 x = 0 in branchless

若是 x 為 0,在進入函式一開始的時候會因為 x-- 變成 0xFFFFFFFF,所以在做減法前就需要判斷是否為 0。

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

+   x -= (x > 0);
-   x--;

commit: 0095464