關於 C/C++ 負整數的 shift 以及 arithmetic right shift 的小技巧

在看 《Tonc: Whirlwind Tour of ARM Assembly》 的時候學到一個小技巧: 若 n 是有號 32bit 整數, 則 n>>31 相當於 n >= 0 ? 0 : -1。

看完 arithmetic shift 的定義後, 才發現我沒弄懂 arithmetic right shift, 原來是一直補進 signed bit (most significant bit), 當它是負數時, 等於一直補 1 進來。所以, -1 不管右移幾次, 結果仍是 -1, 不是 0。

將這訊息發到 G+plurk 後, 看到許多人提到 C、C++ 沒定義 signed shift 的行為, 所以用的時候要小心。jserv 提到 compiler 可以加參數改變位元運算的結果。

查看 gcc 的說明, 得知 gcc 有實作 arithmetic right shift, 但看不懂 left shift 的部份。Scott 提到這篇有解釋, 然後我明白了一件事: 關於 C99、C++0x draft 的定義, 我都看不太懂啊 ...。孩子的教育不能等, 要好好學英文。

btw, Louis 提到一個有趣的應用, ((n>>31)^n) - (n>>31) 等同於 abs(n)。拆解這個式子可得知, n 是正數時:

  • n>>31 是 0
  • n^0 仍是 n
  • n - 0 仍是 n

n 是負數時:

  • n>>31 是 -1
  • -1 以 2 補數表示為 0xFFFFFFFF
  • n^(-1) 等同於 1 補數運算
  • 最後再減 -1, 得到 2 補數運算的值

順便試著寫了以下的 C code, 再編成 assembly code, 想說看看會差多少:

int abs1(int n) {
    return n >= 0 ? n : -n;
}

int abs2(int n) {
    if (n >= 0)
        return n;
    return -n;
}

int abs3(int n) {
    return ((n>>31)^n) - (n>>31);
}

結果 abs1 和 abs3 差不多, 以下是 abs1 用 gcc 4.4.3 -O3 編後的結果:

abs1:
 pushl %ebp
 movl %esp, %ebp
 movl 8(%ebp), %eax
 popl %ebp
 movl %eax, %edx
 sarl $31, %edx
 xorl %edx, %eax
 subl %edx, %eax
 ret

gcc 偷吃步用 arithmetic right shift 避免使用 branch。不知這是針對特例的最佳化, 還是用某種神祕的機制算出來的。附帶一提, 我用不同版本的 gcc 編出來的結果不同, 用 4.5.2 最佳化編譯後, abs1 和 abs3 的結果完全一樣, 只差在用的 register 不同。

另外, 若用 ARM assembly 的話, abs() 可以寫成:

@@ 參數由 r0 傳入, 結果寫到 r0
cmp     r0, #0
sublt     r0, 0, r0

而用 arithmetic right shift 的版本則是:

eor     r1, r0, r0, asr #31
sub     r0, r1, r0, asr #31

都是兩個算數指令, 速度應該一樣吧。我沒裝 ARM 開發環境, 應該沒寫錯吧。藉機練習寫看看, 體會指令附加 branch 以及 barrel shifter 的便利之處。指令詳細說明, 見這篇的 "23.3.2. Data instructions"。"r0, asr #31" 那部份是 Op2, 可在同一 cycle 內取得 shift 後的值。

留言

  1. 我決的scott說得那篇, 應該是指因為C並沒有規定是用1補數或是2補數, 所以在處理negative number left shift的時候, 沒辦法直接left shift, 所以通常是logic left shift (也就是照底層實做, 然後決定要不要多做事), 不過sepc上面也就只有說是沒有定義而已阿~

    回覆刪除
  2. 我看得懂那篇文章的意思, 看不懂的是標準規範的意思 Orz

    回覆刪除
  3. @fcamel: 我看過最容易讀,收穫最多的標準文件是 POSIX: http://pubs.opengroup.org/onlinepubs/9699919799/。ISO C, C++ 標準特別難讀,比以來 MPEG 的標準, ISO-13818,都好讀很多。

    回覆刪除
  4. @fcamel: 學 Assembly 還是要試,我習慣至少看自己寫的 C code,如『工研六題』,編譯出來的結果。在 Windows 或 Mac 下,用 Android SDK 中的 qemu based 模擬器,加上 Android NDK 中的 gcc 即可開發。

    我應該 blog 一下這個怎麼用,但該做的正事還不少 ...

    回覆刪除

張貼留言

這個網誌中的熱門文章

(C/C++ ) 如何在 Linux 上使用自行編譯的第三方函式庫

熟悉系統工具好處多多

virtualbox 使用 USB 裝置