一個算法的說明設置，清除和測試一個位

嘿，在編程珍珠書中，有一個源代碼用於設置，清除和測試一個int數組中的給定索引位，它實際上是一個設置表示。一個算法的說明設置，清除和測試一個位

的代碼如下：

#include<stdio.h> 
#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)); 
} 

void clr(int i) 
{ 
    a[i>>SHIFT] &= ~(1<<(i & MASK)); 
} 

int test(int i) 
{ 
    a[i>>SHIFT] & (1<<(i & MASK)); 
}

有人能解釋我的SHIFT和掩模限定的原因是什麼？他們在代碼中的目的是什麼？

我已經閱讀過以前的相關question。

來源

2008-11-06 jaircazarin-old-account

VonC發佈了一個關於位掩碼的一個很好的答案一般。以下是針對您發佈的代碼更具體的一些信息。

給定一個表示位的整數，我們計算出該數組的哪個成員保存那一位。即：位0至31生活在a[0]，位32至63生活在a[1]，等i>>SHIFT所做的是i/32。這可以計算出該位的哪個成員a。通過優化編譯器，這些可能是等效的。顯然，現在我們已經知道位標記所在的a的哪個成員，我們需要確保我們在該整數中設置正確的位。這是1 << i所做的。但是，我們需要確保我們不會嘗試訪問32位整數中的第33位，所以移位操作受到1 << (i & 0x1F)的限制。這裏的魔術是0x1F是31，所以我們絕不會將i所代表的位移到31位以上（否則它應該在a的下一位成員中去掉）。

來源

2008-11-06 07:22:27

+1，比我的一般答案更準確。 – VonC 2008-11-06 07:25:42

謝謝，那正是我所需要的。 – 2008-11-06 07:31:52

從Here（一般的回答讓這個線程開始）

位掩碼是一個值（其可以存儲在一個變量），使您可以整數類型中分離出一組特定的位。

正常情況下，被屏蔽的位將您感興趣的位設置爲1，並將所有其他位設置爲0.然後屏蔽允許您隔離位的值，清除所有位或設置所有位或爲這些位設置一個新值。

掩碼（特別是多位掩碼）通常有一個相關的移位值，這是位需要向左移位的數量，以便最低位掩碼位移到該類型中的最低位位。

例如，使用16位短數據類型假設您希望能夠屏蔽位3,4和5（LSB是數字0）。你掩蓋和轉移會看起來像

#define MASK 0x0038 
#define SHIFT 3

面具往往賦予十六進制因爲它更容易在基地與數據類型位的工作，而不是十進制。歷史上八進制也被用於位掩碼。

如果我有一個變量，VAR，包含數據，該面具是相關的話，我可以隔離這樣

var & MASK

位我都可以在其他位隔離這樣

var & ~MASK

我可以明確這樣

var &= ~MASK;

位，我可以清除所有其他位這樣

var &= MASK;

我可以設置這樣

var |= MASK;

所有位我可以設置所有其他位這樣

var |= ~MASK;

我可以提取比特的十進制值這樣

(var & MASK) >> SHIFT

我可以指定一個新的價值這樣的位

var &= ~MASK; 
var |= (newValue << SHIFT) & MASK;

來源

2008-11-06 07:15:40 VonC

很好的解釋！再有那個追蹤者...... – 2008-11-09 04:07:01

當你想設置一個位陣列內，你必須

尋求正確的數組索引和
設置相應的位這個數組的項目裏面。

有BITSPERWORD（= 32）在一個陣列中的項目，這意味着該索引i必須被分成兩個部分位：

最右邊的5位作爲在陣列項的索引和
其餘的位（最左邊的28）用作數組的索引。

你得到：

的最左邊的28位通過丟棄最右邊的5，這正是i>>SHIFT確實，和
的最右邊的五個位元掩蓋了什麼，但最右邊的五位，這是什麼i & MASK呢。

我想你瞭解其餘的。

來源

2008-11-06 07:25:38 zoul

Bitwise operation和Mask的引導段落是一個簡明的解釋，幷包含一些指針供進一步研究。

將8位字節看作是來自8個成員的Universe中的一組元素。一個成員是IN當相應位置位時置位。多設置一次不會修改set membership（一個位只能有2個狀態）。 bitwise operators in C提供對掩碼和移位的位訪問。

來源

2008-11-06 07:29:09 gimel

代碼試圖按數組存儲N位，其中數組的每個元素都包含BITSPERWORD（32）位。

因此，如果您嘗試訪問位i，您需要計算存儲它的數組元素的索引（i/32），這是i>>SHIFT所做的。

然後你需要訪問剛剛得到的數組元素中的那一位。

(i & MASK)給出數組元素（字）的位置。 (1<<(i & MASK))使該位置上的位置位。

現在您可以通過(1<<i & MASK))來設置/清除/測試a[i>>SHIFT]中的那一位。

你也可能認爲i是一個32位數字，第6〜31位是數組元素存儲它的索引，第0〜5位表示該單詞中的位位置。

來源

2008-11-06 07:50:59 tingyu

一個算法的說明設置，清除和測試一個位

回答

相關問題