# 2023q1 Homework3 (quiz3) contributed by < `Korin777` > ## 測驗四 ```c 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 log_{2}(x) \rceil$ 分為以下兩種情況: 1. `x` 是 2 的冪 : $\lceil log_{2}(x) \rceil$ 為位元中 1 所在的最高位位置 2. `x` 不是 2 的冪: $\lceil log_{2}(x) \rceil$ 為位元中 1 所在的最高位位置加一 * 透過二分搜尋來找出 1 所在的最高位位置 * `x--` 確保 `x` 的位元中 1 所在的最高位位置小於 $\lceil log_{2}(x) \rceil$,因此不管 `x` 是否為 2 的冪,位元中 1 所在的最高位位置加一就是 $\lceil log_{2}(x) \rceil$ * 當 `x` 為 1 時輸出應為 0 ,不過這個實作會輸出 1 ,因為 `x--` 後位元中 1 所在的最高位位置應該不為 0 , 下面的實作可以改善這個問題 ```c int ceil_log2(uint32_t x) { uint32_t r, shift; int ceil = !((x & x-1) == 0); 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) + ceil; } ``` * `(x & x-1) == 0` 可以判斷 x 是否為 2 的冪,也就可以判別 $\lceil log_{2}(x) \rceil$ 的兩種情況, 因此找出 `x` 位元中 1 所在的最高位位置再加上 `!((x & x-1) == 0)` 就可以求得 $\lceil log_{2}(x) \rceil$ [題目連結](https://hackmd.io/@sysprog/linux2023-quiz3#%E6%B8%AC%E9%A9%97-3)
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up