重新理解數值

主講人: jserv / 課程討論區: 2016 年系統軟體課程

數字背後的道理

  • 0.1 - 0.3 + 0.2 的結果竟然不等於 0 ?!
  • 在 KTV 唱歌時,若唱不上去,我們常會「低八度」,這時雖然聲音低多了,但與原唱並不衝突,與伴奏也依然和諧。為什麼「八度」如此特別呢?更明確來說,差了八度的聲音聽起來如此相似呢?
    • 差距八度的兩個音的頻率正好差 2 倍!
    • 中音 do (記作 c’) 是 261.6Hz; 高音 do (記作 c’’) 是 523.3Hz
    • 訊號處理 (signal proccessing)

二進位

  • George Boolean 在1800年介紹「邏輯代數」,後來成為「布林代 數」(Boolean Algebra)
  • Claude E. Shannon 於 1938 年發表布林代數對於二進制函數的應用

Integer Overflow

  • 神一樣的進度條
  • 波音 787 不再「夢幻」
    • 波音 787 的電力控制系統在 248 天電力沒中斷的狀況下,會自動關機,為此 FAA (美國聯邦航空管理局) 告知應每 120 天重開機,看來「重開機治百病」放諸四海都通用?這當然是飛安的治標辦法,我們工程人員當然要探究治本議題。
    • 任教於美國 Carnegie Mellon University (CMU) 的 Phil Koopman 教授指出,這其實就是 integer overflow,再次驗證「失之毫釐,差之千里」的道理。
    • 我們先將 248 天換成秒數:
    • 248 days 24 hours/day 60 minute/hour * 60 seconds/minute = 21,427,200
    • 這個數字若乘上 100,繼續觀察:
      • 0x7FFFFFFF (32-bit 有號數最大值) = 2147483647 / (24 60 60) = 24855 / 100 = 248.55 days.
    • 看出來了嗎?每 1/100 秒紀錄在 32-bit signed integer,然後遇到 overflow
    • Counter Rollover Bites Boeing 787
    • 飛行控制系統和軟體工程/編譯器的關聯
    • 航空太空科技是科技發展的火車頭
  • Deep Impact (2005)
  • Ariane 5 (1996)
    • detail report : a data conversion from 64-bit floating point to 16-bit signed integer value

其他 integer overflow 案例:

gdb 顯示 FLAGS register

邏輯和算術的差異

When exactly do side-effects take place in C and C++?

int a = 41; a++; printf("%d\n", a);              42
int a = 41; a++ & printf("%d\n", a);             undefined
int a = 41; a++ && printf("%d\n", a);            42
int a = 41; if (a++ < 42) printf("%d\n", a);     42
int a = 41; a = a++; printf("%d\n", a);          undefined
  • 以下的差異呢?

    • int a=41; a++ & printf("%d\n", a);
    • int a=41; a++ && printf("%d\n", a);
    • int a=41; a=a++; printf("%d\n", a);
  • 語法/語意分析

    • Left & Right 中 (位元運算),關於是先對 Left 還是 Right 取值,沒有明確順序
    • 但對於 Left && Right 來說 (邏輯運算),一定是先確保 Left 成立,才會作 Right

以下程式碼中:

a++ && printf();

左邊先運算 a++,倘若為真,接著才會作右邊的 printf()

運用 bit-wise operator

  • C 語言中,x & (x - 1) == 0 的數學意義

    • power of two
    • signed v.s. unsigned
  • C 語言中,x | (x + 1) 又表示什麼?

    • x with lowest cleared bit set
  • 以下 C 語言程式的 DETECT 巨集能做什麼?

    #if LONG_MAX == 2147483647L
    #define DETECT(X) \
      (((X) - 0x01010101) & ~(X) & 0x80808080)
    #else
    #if LONG_MAX == 9223372036854775807L
    #define DETECT(X) \
      (((X) - 0x0101010101010101) & ~(X) & 0x8080808080808080)
    #else
    #error long int is not a 32bit or 64bit type.
    #endif
    #endif
    
  • 巨集 DETECT 在偵測什麼?
    • Detect NULL

測試這程式時,要注意到由於 LONG_MAX 定義在 <limits.h> 裡面,因此要記得作 #include

這個巨集的用途是在偵測是否為 0 或者說是否為 NULL char ’\0’,也因此,我們可以在 iOS 的原始程式碼 strlen 的實作中看到這一段。那,為什麼這一段程式碼可以用來偵測 NULL char ?

我們先思考 strlen() 該怎麼實做,以下實作一個簡單的版本

unsigned int strlen(const char *s)
{
    char *p = s;
    while (*p != ’\0’) p++;
    return (p - s);
}

這樣的版本有什麼問題?雖然看起來精簡,但是因為他一次只檢查 1byte,所以一旦字串很長,他就會處理很久。另外一個問題是,假設是在 32-bit 的 CPU 上,一次是處理 4-byte (32-bit) 大小的資訊,不覺得這樣很浪費嗎?

為了可以思考這樣的程式,我們由已知的計算方式來逆推原作者可能的思考流程,首先先將計算再簡化一點點,將他從 (((X) - 0x01010101) & ~(X) & 0x80808080) 變成

((X) - 0x01) & ~(X) & 0x80

還是看不懂,將以前學過的笛摩根定理套用上去,於是這個式子就變成了

~( ~(X - 0x01) | X ) & 0x80

再稍微調整一下順序

~( X | ~(X - 0x01) ) & 0x80

所以我們就可進行分析

  • X | ~(X - 0x01) => 取得最低位元是否為 0 ,並將其他位元設為 1
    • X = 0000 0011 => 1111 1111
    • X = 0000 0010 => 1111 1110
  • 想想 0x80 是什麼? 0x80 是 1000 0000 ,也就是 1-byte 的最高位元

上面這兩組組合起來,我們可以得到以下結果

  • X = 0 => 1000 0000 => 0x80
  • X = 1 => 0000 0000 => 0
  • X = 2 => 0000 0000 => 0
  • .......
  • X = 255 => 0000 0000 => 0

於是我們知道,原來這樣的運算,如果一個 byte 是 0,那經由這個運算得到的結果會是 0x80,反之為 0。

再將這個想法擴展到 32-bit,是不是可以想到說在 32bit 的情況下,0 會得到 0x80808080 這樣的答案?我們只要判斷這個數值是不是存在,就可以找到 ’\0’ 在哪了!

參考資料:

應用:

算術完全可用數位邏輯實做

只能使用位元運算子和遞迴,在C程式中實做兩個整數的加法,可行嗎?

先回顧加法器 的實做,思考以下程式碼:

int add(int a, int b)
{
    if (b == 0) return a;
    int sum = a ^ b; /* 相加但不進位 */
    int carry = (a & b) << 1; /* 進位但不相加 */
    return add(sum, carry);
}

延伸閱讀: How to simulate a 4-bit binary adder in C

Count Leading Zero

Fast computing of log2 for 64-bit integers

  • 類似 De Bruijn 演算法

  • 64-bit version

    const int tab64[64] = {
    63,  0, 58,  1, 59, 47, 53,  2,
    60, 39, 48, 27, 54, 33, 42,  3,
    61, 51, 37, 40, 49, 18, 28, 20,
    55, 30, 34, 11, 43, 14, 22,  4,
    62, 57, 46, 52, 38, 26, 32, 41,
    50, 36, 17, 19, 29, 10, 13, 21,
    56, 45, 25, 31, 35, 16,  9, 12,
    44, 24, 15,  8, 23,  7,  6,  5
    };
    int log2_64 (uint64_t value)
    {
    value |= value >> 1;
    value |= value >> 2;
    value |= value >> 4;
    value |= value >> 8;
    value |= value >> 16;
    value |= value >> 32;
    return tab64[((uint64_t)((value - (value >> 1 ))*0x07EDD5E59A4E28C2)) >> 58];
    }
    
  • 32-bit version

    const int tab32[32] = {
    0,  9,  1, 10, 13, 21,  2, 29,
    11, 14, 16, 18, 22, 25,  3, 30,
    8, 12, 20, 28, 15, 17, 24,  7,
    19, 27, 23,  6, 26,  5,  4, 31
    };
    int log2_32 (uint32_t value)
    {
    value |= value >> 1;
    value |= value >> 2;
    value |= value >> 4;
    value |= value >> 8;
    value |= value >> 16;
    return tab32[(uint32_t)(value*0x07C4ACDD) >> 27];
    }
    

gcc 提供 built-in Function:

可用來實做 log2:

#define LOG2(X) ((unsigned) \
   (8 * sizeof (unsigned long long) -
    __builtin_clzll((X)) - 1))

那該如何實做 clz 呢?

  • [ ] iteration version

    int clz(uint32_t x) {
      int n = 32, c = 16;
      do {
          uint32_t y = x >> c;
          if (y) { n -= c; x = y; }
          c >>= 1;
      } while (c);
      return (n - x);
    }
    
  • [ ] binary search technique

    int clz(uint32_t x) {
      if (x == 0) return 32;
      int n = 0;
      if (x <= 0x0000FFFF) { n += 16; x <<= 16; }
      if (x <= 0x00FFFFFF) { n += 8; x <<= 8; }
      if (x <= 0x0FFFFFFF) { n += 4; x <<= 4; }
      if (x <= 0x3FFFFFFF) { n += 2; x <<= 2; }
      if (x <= 0x7FFFFFFF) { n += 1; x <<= 1; }
      return n;
    }
    
  • [ ] byte-shift version

    int clz(uint32_t x) {
      if (x == 0) return 32;
      int n = 1;
      if ((x >> 16) == 0) { n += 16; x <<= 16; }
      if ((x >> 24) == 0) { n += 8; x <<= 8; }
      if ((x >> 28) == 0) { n += 4; x <<= 4; }
      if ((x >> 30) == 0) { n += 2; x <<= 2; }
      n = n - (x >> 31);
      return n;
    }
    
  • ffs() 會回傳給定數值的 first bit set 的位置

    • 例如 128 在 32-bit 表示為 0x10000000,ffs(128)會回傳 8
    • 129 在 32bit 表示為 0x10000001,ffs(129) 會回傳 1

延伸閱讀: Bit scanning equivalencies

省去迴圈

考慮以下 C 程式,解說在 32-bit 架構下具體作用(不是逐行註解),以及能否避開用迴圈?

int func(unsigned int x) {
    int val = 0; int i = 0;
    for (i = 0; i < 32; i++) {
        val = (val << 1) | (x & 0x1);
        x >>= 1;
    }
    return val;
}

簡單來說這段程式碼就是拿來顛倒輸入數字的位元順序,如下面測試所示,顛倒後位元不足 32bit 者,全部補 0

------input number 99--------
2bit= 1100011
val = 11000110000000000000000000000000
------output number -973078528--------

------input number 198--------
2bit= 11000110
val = 1100011000000000000000000000000
------output number 1660944384--------

------input number 297--------
2bit= 100101001
val = 10010100100000000000000000000000
------output number -1803550720--------

------input number 396--------
2bit= 110001100
val = 110001100000000000000000000000
------output number 830472192--------

------input number 4294967281--------
2-bit= 11111111111111111111111111110001
val   = 10001111111111111111111111111111
------output number -1879048193--------

參考 Reverse integer bitwise without using loop,將原本的 for 迴圈變更為 bit-wise 操作:

new = num;
new = ((new & 0xffff0000) >> 16) | ((new & 0x0000ffff) << 16);
new = ((new & 0xff00ff00) >> 8) | ((new & 0x00ff00ff) << 8);
new = ((new & 0xf0f0f0f0) >> 4) | ((new & 0x0f0f0f0f) << 4);
new = ((new & 0xcccccccc) >> 2) | ((new & 0x33333333) << 2);
new = ((new & 0xaaaaaaaa) >> 1) | ((new & 0x55555555) << 1);

在不使用迴圈的情況下,可以做到一樣的功能。

加解密的應用

  • [ ] Caesar shift cipher
  • 把 A-Z 這 26 個字母表示成 A=0, B=1, ..., Z=25,然後給任意一個 KEY,把訊息的字母加上 KEY 之後 mod 26 就會得到加密之後的訊息。假設 KEY=19,那麼原本的訊息例如 HELLO (7 4 11 11 14) 經過 cipher 後 (26 23 30 30 33) mod 26 => (0 23 4 4 7) 會變成 AXEEH 的加密訊息。

  • [ ] XOR

  • 假設有一張黑白的相片是由很多個0~255的pixel組成(0是黑色,255是白色),這時候可以用任意的 KEY (00000000~2~ - 11111111~2~) 跟原本的每個 pixel 做運算,如果使用 AND (每個bit 有75% 機率會變成 0),所以圖會變暗。如果使用 OR (每個 bit有 75% 機率會變 1),圖就會變亮。這兩種幾乎都還是看的出原本的圖片,但若是用 XOR 的話,每個 bit 變成 0 或 1 的機率都是 50%,所以圖片就會變成看不出東西的雜訊。

上圖左 1 是原圖,左 2 是用 AND 做運算之後,右 2 是用 OR 做運算之後,右 1 是用 XOR,可見使用 XOR 的加密效果最好。

參考資料:Ciphers vs. codes