程式真的要寫成這麼聰明嗎?

Alan Perlis, Alan Perlis Quotes

A programming language is low level when its programs require attention to the irrelevant.

《代码执行的效率》裡頭提到一個效率問題,

《代码执行的效率》有效率的改法

if (data[j] >= 128)
sum += data[j];
变成：
int t = (data[j] - 128) >> 31;
sum += ~t & data[j];

這個看似聰明的改法帶來了什麼樣難以察覺的陷阱呢?

不想看答案的可以先想想看。

b.cpp

 1 #include <stdio.h>
 2 #include <stdint.h>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 
 7 int main(int argc, char *argv[])
 8 {
 9   int data[10] = {1,2,3,4,200,6,7,8,300,10};
10   int sum=0;
11 
12   for (int j=0 ; j < 10 ; ++j)
13   {
14     int t = (data[j] - 128) >> 31;
15     //printf("     %u ## t: %u, ~t: %u, ~t & data[j]: %u\n", j, t, ~t, ~t & data[j]);
16     cout << "cout " << j << " ## t: " << t << ", ~t: " << ~t << ", ~t & data[j]: " << (~t & data[j]) << endl;
17     sum += ~t & data[j];
18     #if 0
19     if (data[j] >= 128)
20       sum += data[j];
21     #endif
22   }
23   //printf("sum: %u\n", sum); 
24   cout << "sum: " << sum << endl;
25   return 0;
26 }

b.cpp 執行結果

cout 0 ## t: -1, ~t: 0, ~t & data[j]: 0
cout 1 ## t: -1, ~t: 0, ~t & data[j]: 0
cout 2 ## t: -1, ~t: 0, ~t & data[j]: 0
cout 3 ## t: -1, ~t: 0, ~t & data[j]: 0
cout 4 ## t: 0, ~t: -1, ~t & data[j]: 200
cout 5 ## t: -1, ~t: 0, ~t & data[j]: 0
cout 6 ## t: -1, ~t: 0, ~t & data[j]: 0
cout 7 ## t: -1, ~t: 0, ~t & data[j]: 0
cout 8 ## t: 0, ~t: -1, ~t & data[j]: 300
cout 9 ## t: -1, ~t: 0, ~t & data[j]: 0
sum: 500

哇! 真的可以計算正確結果耶! 估計你開始佩服想出這個寫法的人了。再來看看另外的例子 a.cpp。

a.cpp

 1 #include <stdio.h>
 2 #include <stdint.h>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 
 7 int main(int argc, char *argv[])
 8 {
 9   uint32_t data[10] = {1,2,3,4,200,6,7,8,300,10};
10   uint32_t sum=0;
11 
12   for (int j=0 ; j < 10 ; ++j)
13   {
14     uint32_t t = (data[j] - 128) >> 31;
15     //printf("     %u ## t: %u, ~t: %u, ~t & data[j]: %u\n", j, t, ~t, ~t & data[j]);
16     cout << "cout " << j << " ## t: " << t << ", ~t: " << ~t << ", ~t & data[j]: " << (~t & data[j]) << endl;
17     sum += ~t & data[j];
18     #if 0
19     if (data[j] >= 128)
20       sum += data[j];
21     #endif
22   }
23   //printf("sum: %u\n", sum); 
24   cout << "sum: " << sum << endl;
25   return 0;
26 }

a.cpp 執行結果<

cout 0 ## t: 1, ~t: 4294967294, ~t & data[j]: 0
cout 1 ## t: 1, ~t: 4294967294, ~t & data[j]: 2
cout 2 ## t: 1, ~t: 4294967294, ~t & data[j]: 2
cout 3 ## t: 1, ~t: 4294967294, ~t & data[j]: 4
cout 4 ## t: 0, ~t: 4294967295, ~t & data[j]: 200
cout 5 ## t: 1, ~t: 4294967294, ~t & data[j]: 6
cout 6 ## t: 1, ~t: 4294967294, ~t & data[j]: 6
cout 7 ## t: 1, ~t: 4294967294, ~t & data[j]: 8
cout 8 ## t: 0, ~t: 4294967295, ~t & data[j]: 300
cout 9 ## t: 1, ~t: 4294967294, ~t & data[j]: 10
sum: 538

發現結果不正確了, 僅僅是 type 的不同, 程式就不正確了。你願意用這個演算法嗎? 這個演算法在某些時候是對的, 某些時候是錯的, 你能掌握在什麼時機才是正確的嗎?

第一點: 這寫法很難懂
第二點: 不一定總是正確

如果你能掌握型別的話, 那還有一個規則是你不能掌握的。最後在提醒一個 c 語言規則, 有號數的右移運算, 是 implementation-defined (ref: 1.2. 移位运算)。

當然查閱 c 規格書最具有權威性, 但那個不好看, 如果要在精確一點的中文資料, 可以參考《标准C语言指南》6.18 (p341), 將移位運算式做了詳細的說明, 看完之後應該會覺得, 嗯 ... c 真難。

相信這麼一來, 之前的佩服感應該是完全消失了, c 沒有這麼簡單, 她是程式語言, 不是數學。

我不熟習 java, 有人可以說說 java 的行為嗎?

既然談到 Bitshift Operators 順便說說之前遇到的一個問題。

t.c

 1 #include <stdio.h>
 2 #include <stdint.h>
 3 int main(int argc, char *argv[])
 4 {
 5   uint64_t temp;
 6
 7   temp = (1 << 32);
 8   printf("temp: %lu\n", temp);
 9   return 0;
10 }

t.c 看似理所應當的程式碼, c 編譯器發出了 warning:

warning

1 t.c: In function 'main':
2 t.c:7:13: warning: left shift count >= width of type [-Wshift-count-overflow]
3    temp = (1 << 32);

怎麼回事? 1 的 type 是 int, 不是 uint_64_t, 也不是其他 type, 就是 int, 在我的平台, 是 32bit, 而 shift 32 bit 超出了 32bit 的範圍, 這是 Undefined (ref: 1.2. 移位运算), 這回我參考了 c 標準規格書 (ref: figure 1, 第 3 點), 而不是如人所想因為等號左邊有個 uint64_t temp 就會將結果轉型成 uint64_t, 這是 c 語言很難相處之道。

figure 1. N1570 6.5.7

解法: 1ul << 32, 明白告訴 c 編譯器, 我的 1 是 unsigned long (在我的環境是 64bit)