跳到主要內容

關於 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 上使用自行編譯的第三方函式庫

以使用 LevelDB 為例。 抓好並編好相關檔案,編譯方式見第三方函式庫附的說明:$ ls include/ # header files leveldb/ $ ls out-shared/libleveldb.so* # shared library out-shared/libleveldb.so@ out-shared/libleveldb.so.1@ out-shared/libleveldb.so.1.20* 下面的例子用 clang++ 編譯,這裡用到的參數和 g++ 一樣。 問題一:找不到 header$ clang++ sample.cpp sample.cpp:5:10: fatal error: 'leveldb/db.h' file not found #include "leveldb/db.h" ^ 1 error generated. 解法:用 -I 指定 header 位置 問題二:找不到 shared library$ clang++ sample.cpp -I include/ /tmp/sample-2e7dd8.o: In function `main': sample.cpp:(.text+0x1e): undefined reference to `leveldb::Options::Options()' sample.cpp:(.text+0x6f): undefined reference to `leveldb::DB::Open(leveldb::Options const&, std::string const&, leveldb::DB**)' sample.cpp:(.text+0x10c): undefined reference to `leveldb::Status::ToString() const' sample.cpp:(.text+0x7d0): undefined reference to `leveldb::Status::ToString() const' clang: error: linker command failed with exit code 1 (u…

熟悉系統工具好處多多

記一下以前很困擾, 現在秒殺的小事。 更新這篇的時候, 忘了函式庫用的 man page 裝在那個 package。以前就會想辦法 google, 運氣好一下會找到, 運氣不好會多找一會兒。 這回我想到新作法:$ strace -e open man 3 printf > /dev/null # 發現是讀 /usr/share/man/man3/printf.3.gz $ dpkg --search /usr/share/man/man3/printf.3.gz # 找到套件名稱 manpages-dev $ aptitude show manpages-dev # 確認描述符合, 收工

virtualbox 使用 USB 裝置

2012-12-16 更新 現在 (4.x 版) 似乎無需做任何設定, 只要有裝 Oracle VM VirtualBox Extension Pack, 在 VirtualBox 視窗右下角按 USB 的圖示, 再點目標裝置, 即可加入或移除該裝置 同一時間只有 host 或 guest 可擁有該裝置, 所以從 guest OS 移除, 相當於接回 host OS 目前 VirtualBox 只支援 USB 2.0 的插槽, 若偵測不到時, 注意一下是否為這個問題 有時拔拔插插, VirtualBox 會進入奇怪的狀態, 接上去 guest OS 無法連接且跳出 device is busy 的錯誤訊息。試看看拔除該裝置, 重開 guest OS (續上則) 若重開 guest OS 無效, 並且 host OS 已移除該裝置, VirtualBox 的 USB 清單卻仍顯示 "captured", 試看看拔除該裝置, 重開 host OS原文網路上搜一下, 比較多是 Ubuntu 當 host 的解法, 我的情況是 Win7 當 host, Ubuntu 當 guest。 這兩篇說明很詳細《Learn How to Set Up USB and Networking Options in VirtualBox》《幻影千瞳的部落格: VirtualBox 使用筆記(二):使用 USB 裝置》 現在的版本圖形介面很好用了, 不用像第二篇說的那樣用指令操作。這裡記下我的操作步驟: 關掉 guest OS 在 VirtualBox 選單, 選擇 guest OS -> Settings -> USB -> Enable USB 2.0 會出現訊息框, 說明要安裝 Oracle VM VirtualBox Extension Pack。下載後安裝它 host OS 插入 USB 隨身碟 在 VirtualBox 選單, 選擇 guest OS -> Settings -> USB, 點右邊有綠色 "+" 的 USB 頭的圖示, 選擇該 USB 隨身碟, 加入它的 filter 從 host OS 移除 USB 隨身碟 開啟 guest OS 插入 USB 隨身碟, 於是 guest OS 會自動偵測…