HackMD
2020q3 Homework3 (quiz3)
contributed by < quantabase13 >
程式運作原理
測驗 1
int asr_i(signed int m, unsigned int n)
{
const int logical = (((int) -1) >>1/*OP1*/) > 0;
unsigned int fixu = -(logical & ( m < 0/*OP2*/));
int fix = *(int *) &fixu;
return (m >> n) | (fix ^ (fix >> n));
}
這題的目標是要實作跨平台算術右移(arithmetic right shift, 簡稱asr)。由於在 C 語言中對有號型態的物件(且值為負) asr 屬於 unspecified behavior (程式行為仰賴編譯器實作和平台特性而定)，因此實作過程中必須要對可能出現的情況做出補償。
此題思路如下：
- 對有號型態的負數算術右移後， most significat bit (MSB) 可能為 0 或 1 。
- 根據原本的有號型態物件值是否大於0，決定是否該對算術右移後的結果做出補償。
列出表格來討論：
| logical | Is signed object < 0 ?｜ | MSB(the output of our implementation) |
|---|---|---|
| 1 | yes | 1 |
| 0 | yes | 1 |
| 1 | no | 0 |
| 0 | no | 0 |
| 發現不論 logical 值為何，只要 signed object < 0 的話，就必須讓 MSB 等於 1 。 | ||
| 把 logical 去掉後，程式碼如下： |
int asr_i(signed int m, unsigned int n)
{
unsigned int fixu = -( m < 0/*OP2*/);
int fix = *(int *) &fixu;
return (m >> n) | (fix ^ (fix >> n));
}
只要 m < 0 ，就把 (m >> n) 最左邊的 n 個 bits 設為1。
測驗 2
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) & 0x1 /*OPQ*/);
}
分為兩個方向討論：
(num & (num -1)) == 0:
四的冪次可以寫成
故只要 num 為4的冪次，(num & (num -1))為0。
!(__builtin_ctz(num) & 0x1 /*OPQ*/):
我們只要檢查__builtin_ctz(num)是不是偶數即可，方法就是檢查其 less significant bit 是否為 1。
測驗 3
int numberOfSteps (int num)
{
return num ? __builtin_popcount(num)/*AAA*/ + 31 - __builtin_clz(num)/*BBB*/ : 0;
}
閱讀 LeetCode 上關於 numberOfSteps 的說明後，可以歸納出程式碼的運作流程：
由此，我們其實可以發現：
- 2 進位表示的 num 中 1 的個數就是
num = num -1的執行次數。 - 32 - (leading zero bit 的數目) -1 就是
num = num >> 1的執行次數。
測驗 4
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v) {
if (!u || !v) return u | v;
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
while (!(u & 1))
u /= 2;
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v/*XXX*/);
return u << shift/*YYY*/;
}
這題的實作利用了 Binary GCD algorithm。參考了維基百科上的資料後，得知可以重複利用以下四條恆等式將問題化簡：
1. gcd(0, v) = v
2. gcd(2u, 2v) = 2·gcd(u, v)
3. gcd(2u, v) = gcd(u, v)
4. gcd(u, v) = gcd(|u − v|, min(u, v))
程式碼的第一部份：
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
對應到恆等式(1)，將兩數共有的 2 的冪次提出。
程式碼的第二部份中的：
while (!(u & 1))
u /= 2;
和
while (!(v & 1))
v /= 2;
對應到恆等式(3)。
另外
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
對應到恆等式(4)。
過程中，v 存的是 | u - v | 的值，也就是說透過 v 可以確定何時離開 while 迴圈。
另外， u 存的就是還沒 shift 的 gcd。
測驗 5
這題原始的實作如下：
#include <stddef.h>
size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
size_t pos = 0;
for (size_t k = 0; k < bitmapsize; ++k) {
uint64_t bitset = bitmap[k];
size_t p = k * 64;
for (int i = 0; i < 64; i++) {
if ((bitset >> i) & 0x1)
out[pos++] = p + i;
}
}
return pos;
}
bitmap array 裡存了 bitmapsize 個 類型為uint64_t 的 object，
bitmap 中的第 i 個 bitset ，其第 j 個 bit 對應到數字 output[pos] 存入數字時，如果此 bit 為 0，代表 output[pos] 的將是下一個非0 bit 所對應的數。
以此作為基礎，可以試著分析使用 clz 改寫的程式碼：
#include <stddef.h>
size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
size_t pos = 0;
uint64_t bitset;
for (size_t k = 0; k < bitmapsize; ++k) {
bitset = bitmap[k];
while (bitset != 0) {
uint64_t t = bitset & -bitset/*KKK*/;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
改寫後的程式碼主要目的是為了去掉判斷 bit 是否為 1 的 for loop。
原先的程式碼必須1個 bit 1 個 bit 的檢查，直到有非 0 bit 才能將對應的數字存入 out ; 改良後的程式碼使用 ctz 一次取得非 0 bit 在 64 bits 表示中的相對位置，並將對應的數字存入 out 。
由於 ctz 是算從 least sigificant bit 向左遇到第一個 1 之前的 0 數量，因此若要得知下一個 1 在 64 bits 表示中的相對位置，必須利用額外的技巧才能達到目的，這就是
uint64_t t = bitset & -bitset
這段程式碼的作用。
分析bitset，可分為兩種 case :
-
bitset(1~63) bitset(0) xxx…xxx 1 -
bitset(1~63) bitset(0) xxx…xxx 0
-
若 bitset 屬於 case 1 ，則 -bitset 可以表示成如下：
-bitset(1~63) -bitset(0) ～bitset(1~63) 1 這樣 bitset & -bitset就可表示成：bitset & -bitset(1~63) bitset & -bitset(0) - - 1 如此 bitset^=(bitset & -bitset)後就能利用ctz找出下一個 bit 1 的相對位置。 -
若 bitset 屬於 case 2 ， 則 -bitset 可以表示如下：
-bitset(n+1~63) -bitset(n) -bitset(0~n-1) ～bitset(n+1~63) 1 由右數來第 n 個 bit 的位置就是原本的 bitset 第一個非 0 bit 所在位置。 bitset^=(bitset & -bitset)一樣能利用ctz找出下一個 bit 1 的相對位置。
