Bit-TrickCGDB

利用 Bit-Trick 實作分支陳述式

根據 C 語言規格書中 6.8.4 所定義的 Context-free grammar

selection-statement:
          if ( expression ) statement
          if ( expression ) statement else statement
          switch ( expression ) statement

倘若我們選擇了第一條 production rule,那麼 gcc 一定會產生 Branch Instructions。基於效能上的需求,可以使用以下實作。

假設存在兩個有號整數: int32_t a, b; 和分支陳述式 if (b < 0) a++; , 那麼分支陳述式可以取代為 a -= b >> 31;

一開始我們定義 b 是一個有號整數,因此 b 右移 31 位後,其值必為 Sign Bit 。也就是說,如果 b > 0, 那麼 b >> 31 必為 0。如果 b < 0, 那麼 b >> 31 必為 -1。a -= -1; -> a = a - (-1) -> a = a + 1; -> a++;

可以用 GDB 來觀察

7 a = 3; b = -5; c = 7; d = 11;
8 a -= b >> 31;
9 c -= d >> 31;

p/x b
$1 = 0xfffffffb
p/x d
$2 = 0xb
p/x b >> 31
$3 = 0xffffffff
p/x d >> 31
$4 = 0x0

-完-

Advertisements
標準

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s