Try   HackMD

2020q3 Homework3 (quiz3)

contributed by < ptzling310 >

2020q3 第 3 週測驗題

測驗 1 ： 有號整數的跨平台 ASR 實作

依據 ISO/IEC 9899:TC2 (即 C99) 標準的 6.5.7 章節 (第 84 到第 85 頁):

“The result of E1 >> E2 is E1 right-shifted E2 bit positions. … If E1 has a signed type and a negative value, the resulting value is implementation-defined.”








int asr_i(signed int m, unsigned int n)
{
    const int logical = (((int) -1) OP1) > 0;
    unsigned int fixu = -(logical & (OP2));
    int fix = *(int *) &fixu;
    return (m >> n) | (fix ^ (fix >> n));
}
  • OP1： >> 1
  • OP2： m < 0

程式解析

const int logical = (((int) -1) OP1) > 0;

首先這邊先判目前所在的平台是採算數右移或是邏輯右移，藉由 -1 來測試。 所以 OP1= >>1。

  1. 算術右移： (-1) >> 1 = (1111)2 ， logical = 0
  2. 邏輯右移： (-1) >> 1 = (0111)2 ， logical = 1
unsigned int fixu = -(logical & (OP2));

接著判斷輸入的 m 是否需要進行 ASR 的修正， 如果 m > 0 ，表示 m 是正數，不論平台做邏輯或算數右移，其結果都是對的。
若m < 0，表示 m 是負數，若 logical == 1，就要對該數右移的結果進行修正。所以OP2 = ( m < 0 )。
故 logical & (m < 0) 之結果就可能為 (0000 0000)2 或者 (0000 0001)2，為了要讓最後產生 1 在 MSB 的位置， 所以在 logical & (m < 0) 前面加上 -。 最後 fixu 會有兩種可能，分別為 (0000 0000)2 = 0 或者 (1111 1111)2 = (-1)。

int fix = *(int *) &fixu;

就結果來看， fix 與 fixu 所存的值應該是一樣的，那為何要不要直接寫 int fix = = -(logical & (m < 0)); ？
參照 jserv 在 RinHizakura 中的回覆：避免編譯器進行過度 (aggressive) 最佳化

TODO：過度最佳化會帶來的影響

return (m >> n) | (fix ^ (fix >> n));

在 return 這階段來做右移修正， 當m >> n 後， m 的二進制的最左 n 個 bit 會為 0 ， 若 m 為負數時，這些最左 n 個 bits 應為 1 ，故藉由(fix ^ (fix >> n)) 來產生所需要的 n 個 1 補在 m >> n 的最左 n 個 bits。

數學證明和 Graphviz 製作的圖解

Question： 會有哪一類型的圖產生？

可參照 Swift: Advanced Operators 精美的圖示，用來說明算術位移，你可搭配數學證明解釋通用 (generic) 的狀況

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

logical 變化 - 考慮平台為邏輯右移







structs



int
(int) -1



struct_1

1

1

...

1

1



struct_12

0

1

...

1

1



struct_1:f0->struct_12:f1





struct_1:f1->struct_12:f2





struct_1:f3->struct_12:f4





int2
>>1

所以右移後的結果 >0 ，故 logical = 1







structs



int
logical



struct_1

0

0

...

0

1

fixu 變化： 假設 m = -5

因為 logical = 1 且 m = -5 < 0 ，logical & m < 0 為 1。
故 fixu = (1…1)2。







structs



int
input1: logical = 1



struct_1

0

0

...

0

1



result

0

0

...

0

1



struct_1:f4->result:f4





int2
input2: m < 0 = 1



struct_2

0

0

...

0

1



struct_2:f4->result:f4





res
logical & (m<0)

最後 fixu 是上圖結果再取 -。







structs



int2
fixu



struct_2

1

1

...

1

1

fix 變化：

其實就是 fixu 的值，但 fix 為 signed。







structs



int2
fix



struct_2

1

1

...

1

1

求最後的結果

假設 m = -5 ， n = 1







structs

m >> n


int
(int) -5



struct_1

1

...

1

0

1

1



struct_12

0

1

...

1

0

1



struct_1:f0->struct_12:f0





struct_1:f1->struct_12:f1





struct_1:f2->struct_12:f2





struct_1:f3->struct_12:f3





struct_1:f4->struct_12:f4





int2
-5 >> 1










structs

fix >> n


int
fix



struct_1

1

...

1

1

1

1



struct_12

0

1

...

1

1

1



struct_1:f0->struct_12:f0





struct_1:f1->struct_12:f1





struct_1:f2->struct_12:f2





struct_1:f3->struct_12:f3





struct_1:f4->struct_12:f4





int2
fix >> 1










structs

fix ^ (fix >> n)


int
input1: fix



struct_1

1

1

...

1

1



result

1

0

...

0

0



struct_1:f0->result:f0





int2
input2: fix>>1



struct_2

0

1

...

1

1



struct_2:f0->result:f0





res
fix ^ (fix >> 1)










structs

(m>>n) | fix ^ (fix >> n)


int
input1: -5 >> 1



struct_1

0

1

...

1

0

1



result

1

1

...

1

0

1



struct_1:f1->result:f1





struct_1:f2->result:f2





struct_1:f3->result:f3





int2
input2: fix ^ (fix >> 1)



struct_2

1

0

...

0

0

0



struct_2:f0->result:f0





res
(-5>>1) | fix ^ (fix >> 1)

練習實作其他資料寬度的 ASR，可參照 C 語言：前置處理器應用篇 撰寫通用的巨集以強化程式碼的共用程度

Question：其他寬度的意思？

指 int16, int32, int64, 等等。width 就是「資料寬度」，不要因為讀了一堆對岸文章，就忘了繁體中文怎麼書寫

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

  1. #include
  2. #define

  • #define： #define 巨集名稱 算式

    • 被定義的內容就是巨集( macro )
    • 常用來定義一個模板，取代常用的程式片段
    • #define 若為多行，需在每一行最後加上\
    • 會定義在 #include 以及 main() 中間
    • \後不可有空格，否則會出現 warning: backslash and newline separated by space

  • 改寫

此版本程式雖然使用了 Macro ，卻沒程式碼共用！(因為我把不同 data width 都分開打) 











































#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int16_t asr_16(int16_t m, unsigned int n)
{
    const int16_t logical = (((int16_t) -1) >>1 ) > 0;
    uint16_t fixu = -(logical & (m<0));
    int16_t fix = *(int *) &fixu;
    return (m >> n) | (fix ^ (fix >> n));
}

int32_t asr_32(int32_t m, unsigned int n)
{
    const int32_t logical = (((int32_t) -1) >>1 ) > 0;
    int32_t fix = *(int *) &fixu;
    return (m >> n) | (fix ^ (fix >> n));
}

int64_t asr_64(int64_t m, unsigned int n)
{
    const int64_t logical = (((int64_t) -1) >>1 ) > 0;
    uint64_t fixu = -(logical & (m<0));
    int16_t fix = *(int *) &fixu;
    return (m >> n) | (fix ^ (fix >> n));
}

#define asr_i(m,n) \
    _Generic((m), \
             int16_t: asr_16, \
             int32_t: asr_32, \
             int64_t: asr_64 \
             )(m,n)
    
int main() {
    int16_t a = 8;
    int32_t b = 64;
    int64_t c = 128;
    printf("asr_i(8,1)= %d\n",asr_i(a,1));
    printf("asr_i(64,2)= %d\n",asr_i(b,2));
    printf("asr_i(128,3)= %ld\n",asr_i(c,3));
    return 0;
}











































#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define asr_i(m,n) \
    _Generic((m), \
                     int16_t: asr_16, \
		      int32_t: asr_32, \
		      int64_t: asr_64 \
	 )(m,n)


#define asr(type) \
    const type logical = (((type) -1) >>1 ) > 0; \
	u##type fixu = -(logical & (m<0)); \
	type fix = *(type *) &fixu; \
	return (m >> n) | (fix ^ (fix >> n))

int16_t asr_16(int16_t m, unsigned int n)
{
    asr(int16_t);
}

int32_t asr_32(int32_t m, unsigned int n)
{
    asr(int32_t);
}

int64_t asr_64(int64_t m, unsigned int n)
{
    asr(int64_t);
}

int main() {
    int16_t a = 8;
	int32_t b = 64;
	int64_t c = 128;
	printf("asr_i(8,1)= %d\n",asr_i(a,1));
	printf("asr_i(64,2)= %d\n",asr_i(b,2));
	printf("asr_i(128,3)= %ld\n",asr_i(c,3));
	return 0;
}

結果

asr_i(8,1)= 4
asr_i(64,2)= 16
asr_i(128,3)= 16

測驗 2 ：LeetCode 342. Power of Four

bool isPowerOfFour(int num)
{
    return num > 0 && (num & (num - 1))==0 &&
           !(__builtin_ctz(num) OPQ);  
}
  • OPQ： & 0x1

分別來看 3 個判斷條件：

  1. num > 0：因為
    4n     > 0
  2. (num & (num - 1))==0：因為
    4n=(22)n=22n    ，所以若 num 是 4 的冪，則必為 2 的冪，其二進位必定長得像 (1xx…x)2，(num - 1) 長得會像 (011…1)2， 兩者在做&則必為 0。
  3. !(__builtin_ctz(num) OPQ)：__builtin_ctz(num) 是回傳 num 的二進制的尾巴有幾個 0。

觀察下面幾個

4n：

4n		 二進制
41		 (100)2
42		 (10000)2
43		 (1000000)2
44		 (100000000)2

觀察到尾數 0 的個數的變化是 2 → 4 →　6　→　8 … ，也就是說 0 的尾數應該要是偶數個。
故 (__builtin_ctz(num) OPQ) 判斷 __builtin_ctz(num) 的 0 的個數為奇數個。而奇數的特徵就是，其 b0(LSB) 為 1，利用 &(0..01)2 來讀取 b0看是否為 1 。 得OPQ = & 0x1。

改寫上述程式碼，提供等價功能的不同實作，儘量降低 branch 的數量

  • 觀察
    4n
  1. 只有一個 bit 1，可利用__builtin_popcount來確認。而且也可以排除0的情況，就可以不用做num > 0。
  2. 且 bit 1 會位在 b偶數 的位置(這樣後面一定跟著偶數個 0 )，所以會在 b2、b4、b6…等位子。利用 0x55555555 = (0101 0101 ... 0101)2 與 num 做 AND 來確認 bit 1 是否位在 b偶數。
bool isPowerOfFour(int num){
    return  __builtin_popcount(num) == 1  && (num & 0x55555555);
}

LeetCode 1009. Complement of Base 10 Integer

  • 求補數，即是把 input 二進制中的0↔1。
  • 把某一個數與(1...1)2 做XOR即可得 0 、 1 互換。

input = 5 = (0101)2
input ^ (1111)2 = (1010)2 = -6
expect output = 2 = (010)2

所以應該是要找到最左的 bit 1 後才做XOR！

  • 所以我們先找出由左至右有幾個 0 (利用__builtin_clz)，再針對這些 0 以後的 bits 做XOR。
int bitwiseComplement(int N){
   if (N==0) return 1;  
   unsigned int mask = 0xffffffff ;
   mask = mask >> __builtin_clz(N);
   return mask ^ N; 
}

LeetCode 41. First Missing Positive

  • 若第 i 個元素不等於 i+1， i+1 就是要找的。
  • 若第 i 個元素皆等於 i+1，則回傳 numsSize+1。
int firstMissingPositive(int* nums, int numsSize){
  if(nums==NULL || numsSize==0)
       return 1;  
  //欲查看 nums 中的每個數字
  for(int i = 0; i<numsSize; i++){
      //值為正數，且未超過範圍(1~numsSize)
      if(nums[i] > 0 && nums[i]<numsSize ){
          //當 nums[i] != nums[nums[i] - 1
          if(nums[i] != nums[nums[i] - 1]){
              //交換nums[i]跟nums[nums[i]-1]
              int j = nums[i]-1;
              int tmp = nums[i];
              nums[i] = nums[j];
              nums[j] = tmp;
              i--;
          }
       }
  }
    //值不對
    for(int i = 0 ; i<numsSize; i++)
    {
        if(nums[i] != i+1)
            return i+1;
    }
    //皆正確
    return numsSize+1;
}

研讀 2017 年修課學生報告，理解 clz 的實作方式，並舉出 Exponential Golomb coding 的案例說明，需要有對應的 C 原始程式碼和測試報告

TODO

測驗 3： LeetCode 1342. Number of Steps to Reduce a Number to Zero

計算出將 number 藉由 /2 以及 -1 計算至 0 的步驟數。
假設 int 寬度為 32 位元

int numberOfSteps (int num)
{
    return num ? AAA + 31 - BBB : 0;
}
  • AAA = __builtin_popcount(num)
  • BBB = __builtin_clz(num)

假設 num 為 32 bits ，假設每個 bit 都會做右移(/2)，則至少做 32-1 次 (因為最後一個留下的 bit 並不用在右移，頂多只要 -1)，但如果在 num 中 bn = 1 時，必須多花一個步驟做 -1 ，所以 AAA 應為 __builtin_popcount(num)。
如： (00010010)2)，最左只會做到最左邊的那個 1 就會停止，則不用再做右移，我們就將不用右移的次數扣除，所以 BBB 為 __builtin_clz(num)。

測驗 4 ： 64-bit GCD (greatest common divisor, 最大公因數)























#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 (XXX);
    return YYY;
}
  • XXX = v
  • YYY = u << shift



for (shift = 0; !((u | v) & 1); shift++) {
    u /= 2, v /= 2;
}

for 的終止條件是 !((u | v) & 1 ，表 u 或 v 之 b0 不為 1，才進入for迴圈，簡單來說就是否兩者皆為偶數。這邊是進行

gcd(u,v)=2×gcd(u2,v2)=2×gcd(u′,v′) 。利用 shift 來記錄有幾個 2 要乘在
gcd 前 (可利用左移來完成！)。所以接下還的
gcd(u′,v′) 頂多
u′ 或
v′ 是偶數。



while (!(u & 1))
    u /= 2;

如果

u′ 是偶數，則一樣/2，進行
gcd(u′,v′)=gcd(u′2,v′)。













do {
     while (!(v & 1))
         v /= 2;
       if (u < v) {
         v -= u;
     } else {
         uint64_t t = u - v;
         u = v;
         v = t;
     }
   } while (XXX);
return YYY;

Line 11 如果

v′ 是偶數，則/2，進行
gcd(u′,v′)=gcd(u′,v′2)。
所以 line 11 後，
gcd 內的數都是奇數了！
再來又分兩種情況，一個是 u < v ，此時我們就不斷將 v - u；另一個是 u > v，我們利用變數 t 的幫助，轉換為 u < v 的 case 去做。而 whiel 的結束點就是 v，所以 XXX = v 。而 u 會記錄在一連串輾轉相處法的過程中所得出的最大公因數。
但在 line 5 ~ 7 中，我們有利用 shift 來記錄我們要補回幾次 2 ，這樣才會是正確結果。故 YYY = u << shift。

測驗 5 ： 找 bit array (aka bit map, bit set, bit string, or bit vector) 中 bn=1 的位址

版本一

#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;
}

參數：

  • uint64_t *bitmap ： bitmap point to a bit array.
  • size_t bitmapsize ： 有 bitmapsize 個 bitmap ，每一個 bitmap 有 64 bits 。
  • uint32_t *out ： 要將結果儲存在 out 中
    程式：
for (int i = 0; i < 64; i++) {
    if ((bitset >> i) & 0x1)
        out[pos++] = p + i;

從這段可以看出來，我們每次都是去比較 1 個 bit (每次把 bitset 往右移動，在取 b0 看是否為 1 )，當遇到 1 時，我們就把這個位子記錄到 out 中。
不過這樣的處方法，可以再改進，最右的 bit 0 個數如果很多，就乾脆都不要看，最快的方法是我們直接找到最右邊的 bit 1 ，且紀錄位子。 此作法及可透過 __builtin_ctzll 來達成。

版本二：透過 ctz 改寫

















#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 = KKK;
            int r = __builtin_ctzll(bitset);
            out[pos++] = k * 64 + r;
            bitset ^= t;                           
        }
    }
    return pos;
}

  • KKK = bitset & -bitset

  • 程式理解





size_t pos = 0;
uint64_t bitset;
for (size_t k = 0; k < bitmapsize; ++k) {
     bitset = bitmap[k];

藉由 k 來記錄我們應該確認的 bitmap (共 bitmapsize 個)。
bitset 就是一次取一個 bitmap 來看。



int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;

__builtin_ctzll ： Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
所以透過 builti_ctzll 我可以推算出最右的 bit 1 在哪個位子。

x = (1101 1000)
builti_ctz(x) = 3
則最右的 bit 1 會位於第 3+1=4 個位子

bitset ^= t;

為了找到第二個 bit 1 ，那會希望可以將第一個 bit 1 先忽略掉，所以這裡會希望能夠將目前最右的 bit 1 設置為 0，而其他不變。 故 t 希望為 (0...0 1 0..0)2 而 1 的位子正好是與目前最右 bit 1 的位子相同。

uint64_t t = KKK;

所以 KKK = bitset & -bitset ， 因為 -bitset 的結果是由右至左，遇到第一個 bit 1 保留，其餘的 0 ↔ 1 。

  bitset 1101 1000
&-bitset 0010 1000
--------------------
         0000 1000
時間表
  • 2020/09/28 測驗 1、2、3 程式理解。
  • 2020/09/29 測驗 4 程式理解、浮點數運算
  • 2020/09/30 測驗 5 程式理解、測驗 1 延伸問題_2
  • 2020/10/01 測驗 1 延伸問題_3、C 語言：前置處理器應用篇
  • 2020/10/02 測驗 2 延伸問題_1、2
tags: sysprog2020
Last changed by 
 
ptzling310
ฅ●ω●ฅ
0
415
Published on HackMD