2011-08-28 47 views
7

我今天開始閱讀「Programming Pearls」,在做練習時我遇到了這個問題「你將如何實現自己的位向量?」。當我看着它的解決方案是這樣的:編程珍珠下面程序中的位掩碼用法

#define BITSPERWORD 32 
#define SHIFT 5 
#define MASK 0x1F 
#define N 10000000 

int a[1 + N/BITSPERWORD]; 

void set(int i) { a[i >> SHIFT] |= (1 << (i & MASK)); 

當我收到的困惑是這種說法

1 << (i & MASK) 

可能有人請給我解釋一下這是怎麼回事呢?

回答

4

注意MASK被設定爲使得它具有最低SHIFT位設置,其中SHIFT恰好的BITSPERWORD基2對數。

因此(i & MASK)將選擇i的最低5位,這與除以32後的餘數相同(考慮如何用十進制數的最低兩位數除以100後給出餘數,例)。這使該位數內一個字,我們感興趣的問題。

1 << (i & MASK))(這是順便說一下,一個表達,不是聲明)現在創建一個值,完全位我們感興趣的是設置。將此值與|=合併到內存字中將設置位向量的所需位。

+0

感謝Henning的回覆。如果我用'(i%32)'替換'(i&MASK)''這會有效嗎?如果它是有效的但不是優雅的,那麼你能否說出爲什麼'i&MASK'比'i%32'更受歡迎?非常感謝。 – test123

+0

是的 - 只要你確定'我'不是負面的,''我&MASK'和'I%32'是同樣的事情。按位AND通常比具有餘數的分組更高效,因此已成爲傳統選擇。或者至少當編譯器愚蠢的時候,它會被更高效地利用。今天,你甚至可以期望即使是一個適度優化的編譯器,在這種情況下內部重寫'i%32'到'i&31'(它可以證明'i'不是負數,在這種情況下重寫總是安全的,或者它無論如何,可以推斷出一個負面結果會引發轉變中的未定義行爲)。 –

+0

太好了。非常感謝解釋。 – test123

2

0x20是32,所以i & 0x1F需要i模32,所以你永遠不會移位32位。這是一種保障措施,因爲通過任何並非嚴格小於該類型大小的內容進行轉移都是未定義的行爲。

+0

感謝您的回覆Kerrek! – test123