按位操作的實際應用

Question

1. 你有什麼使用按位操作的？
2. 他們爲什麼這麼得心應手？
3. 有人可以請推薦一個非常簡單的教程？

Answer 1

儘管每個人似乎都掛在了標誌usecase上，但這並不是位運算符的唯一應用（儘管可能是最常見的）。另外C＃是一種足夠高級別的語言，其他技術可能很少使用，但仍然值得了解它們。這是我能想到的：

---

的<<和>>運營商可以迅速地乘的2場的力量，.NET JIT優化可能會爲你做這些（和另一種語言的任何像樣的編譯器同樣），但是如果你真的在每微秒都感到煩惱，那麼你可以寫這個來確定。

這些運算符的另一個常見用途是將兩個16位整數填充到一個32位整數中。像：

int Result = (shortIntA << 16) | shortIntB; 

這對於Win32函數，有時用這一招遺留原因直接接口常見。

而且，當然，如果你想混淆沒經驗的人，比如當提供作業問題的答案時，這些操作員是有用的。:)

在任何實際的代碼，雖然你會好得多用乘法來代替，因爲它有一個更好的可讀性和JIT它，所以沒有性能損失優化到shl和shr說明反正。

---

不少好奇的招數對付^操作（XOR）。這實際上是一個非常強大的運營商，因爲以下屬性：

• A^B == B^A
• A^B^A == B
• 如果你知道A^B那麼它是不可能告訴什麼A和B的，但如果你知道他們中的一個，你可以計算其他。
• 運算符不會遇到任何溢出，如乘法/除法/加法/減法。

一些技巧我一直在使用該運營商看到：

交換兩個整數變量，而中介變量：

A = A^B // A is now XOR of A and B 
B = A^B // B is now the original A 
A = A^B // A is now the original B 

雙向鏈表，每個項目只有一個額外的變量。這在C＃中幾乎沒有用處，但它對於每個字節數的嵌入式系統的低級編程都可能派上用場。

這個想法是你跟蹤第一個項目的指針;最後一項的指針;併爲每個項目跟蹤pointer_to_previous^pointer_to_next。通過這種方式，您可以從任一端遍歷列表，但開銷只是傳統鏈表的一半。下面是遍歷C++代碼：

ItemStruct *CurrentItem = FirstItem, *PreviousItem=NULL; 
while ( CurrentItem != NULL) 
{ 
    // Work with CurrentItem->Data 

    ItemStruct *NextItem = CurrentItem->XorPointers^PreviousItem; 
    PreviousItem = CurrentItem; 
    CurrentItem = NextItem; 
} 

從你只需要的第一行改變從FirstItem到LastItem結束遍歷。那是另一個記憶。

另一個我在C＃中定期使用^運算符的地方是當我必須爲我的類型（它是一個複合類型）計算一個HashCode。如：

class Person 
{ 
    string FirstName; 
    string LastName; 
    int Age; 

    public int override GetHashCode() 
    { 
     return (FirstName == null ? 0 : FirstName.GetHashCode())^
      (LastName == null ? 0 : LastName.GetHashCode())^
      Age.GetHashCode(); 
    } 
} 

Answer 2

我在我的應用程序中使用按位運算符來確保安全性。我會存儲不同層次的枚舉內：

[Flags] 
public enum SecurityLevel 
{ 
    User = 1, // 0001 
    SuperUser = 2, // 0010 
    QuestionAdmin = 4, // 0100 
    AnswerAdmin = 8 // 1000 
} 

，然後分配一個用戶自己的水平：

// Set User Permissions to 1010 
// 
// 0010 
// | 1000 
// ---- 
// 1010 
User.Permissions = SecurityLevel.SuperUser | SecurityLevel.AnswerAdmin; 

再檢查所執行的動作的權限：

// Check if the user has the required permission group 
// 
// 1010 
// & 1000 
// ---- 
// 1000 
if((User.Permissions & SecurityLevel.AnswerAdmin) == SecurityLevel.AnswerAdmin) 
{ 
    // Allowed 
} 

Answer 3

1. 它們可以用於通過一個有限大小的變量將許多參數傳遞給函數。
2. 優勢在於低內存開銷或低內存成本：因此提高了性能。
3. 我不能當場寫教程，但他們在那裏我確定。

Answer 4

它們可以用於不同應用的整體負載，這裏是我以前在這裏發表的問題，它使用位運算：

Bitwise AND, Bitwise Inclusive OR question, in Java

對於其他例子，看看（比如說）標記枚舉。

在我的示例中，我使用按位操作將二進制數的範圍從-128 ... 127更改爲0..255（將其表示從signed改爲unsigned）。

的MSN這裏的文章 - >

http://msdn.microsoft.com/en-us/library/6a71f45d%28VS.71%29.aspx

是非常有用的。

而且，雖然此鏈接：

http://weblogs.asp.net/alessandro/archive/2007/10/02/bitwise-operators-in-c-or-xor-and-amp-amp-not.aspx

是非常技術性的，它涵蓋了。

HTH

Answer 5

任何時候你有項目組合的1個選項或更多的則逐位通常是一個容易解決。

一些例子包括安全位（等待Justin的樣本。），調度日等

Answer 6

我不得不說，正在修改位域壓縮數據最常見的用途之一。你大多在試圖通過數據包經濟實惠的程序中看到這一點。

例

network compression using bitfields

Answer 7

其中最常見的事情，我用它們在C＃是生產哈希碼。有一些相當好的使用它們的散列方法。例如。用於與X的座標類，都是整數一個ý我可以使用：

public override int GetHashCode() 
{ 
    return x^((y << 16) | y >> 16); 
} 

這很快生成時以相等的對象產生的保證是相等的數（假設相等意味着兩個X和Y參數在兩個對象中相同），同時也不會產生低價值對象的碰撞模式（在大多數應用中可能最常見）。

另一個是組合標誌枚舉。例如。 RegexOptions.Compiled | RegexOptions.CultureInvariant | RegexOptions.IgnoreCase

當你對.NET這樣的框架進行編碼時，有些底層操作通常是不必要的（例如在C＃中，我不需要編寫代碼將UTF-8轉換爲UTF-16，它在框架中適用於我），但當然有人必須編寫該代碼。

有幾個位變換技術，如四捨五入到最接近的二進制數（圓高達1010至10000例）：

 unchecked 
     { 
      --x; 
      x |= (x >> 1); 
      x |= (x >> 2); 
      x |= (x >> 4); 
      x |= (x >> 8); 
      x |= (x >> 16); 
      return ++x; 
     } 

當你需要他們哪些是有用的，但往往不會非常普遍。

最後，你也可以使用它們來微觀優化數學，如<< 1而不是* 2，但我只是說它通常是一個壞主意，因爲它隱藏了真實代碼的意圖，在性能上幾乎沒有什麼節省，並可以隱藏一些微妙的錯誤。

Answer 8

二進制排序。有些問題的實現是使用分隔符運算符而不是位移運算符。這導致BS在集合達到10,000,000以上之後失敗

Answer 9

如果您需要與硬件進行通信，您需要在某個點上使用位。

提取像素值的RGB值。

所以，很多事情

Answer 10

我不知道該怎麼實用，解決您認爲是一個數獨，但是讓我們假設它是。

想象一下，你要編寫一個數獨解算器，甚至只是一個簡單的程序，向你展示棋盤並讓你自己解決這個難題，但確保棋步合法。

該板本身將最可能是由二維陣列狀來表示：

uint [, ] theBoard = new uint[9, 9]; 

價值0指細胞仍然是空的和值從區間[1U，9U]是在實際值董事會。

現在想象你想檢查一下是否合法。顯然你可以用幾個循環來完成，但是掩碼可以讓你的工作更快。在一個簡單的程序中，只需確保遵守規則，這並不重要，但可以通過求解器來解決。

您可以維護位掩碼數組，這些位掩碼存儲有關已插入每行，每列a和每個3x3框中的數字的信息。

uint [] maskForNumbersSetInRow = new uint[9]; 

uint [] maskForNumbersSetInCol = new uint[9]; 

uint [, ] maskForNumbersSetInBox = new uint[3, 3]; 

從數字到位模式的映射，與對應於該號碼組1個比特，很簡單

1 -> 00000000 00000000 00000000 00000001 
2 -> 00000000 00000000 00000000 00000010 
3 -> 00000000 00000000 00000000 00000100 
... 
9 -> 00000000 00000000 00000001 00000000 

在C＃中，可以計算位模式這樣（value是uint ）：

uint bitpattern = 1u << (int)(value - 1u); 

在上述1u對應於位模式00000000 00000000 00000000 00000001線路shifte d離開value - 1。如果，例如value == 5，你

00000000 00000000 00000000 00010000

在開始的時候，對於每一行，列和箱掩碼是0。每次在板上放置一些數字時，都會更新掩碼，以便設置與新值對應的位。

我們假設您在第3行插入值5（行和列從0開始編號）。第3行的掩碼存儲在maskForNumbersSetInRow[3]中。讓我們還假設插入之前已經有行3位圖形號碼{1, 2, 4, 7, 9}在面具maskForNumbersSetInRow[3]看起來是這樣的：

00000000 00000000 00000001 01001011 
bits above correspond to:9 7 4 21 

的目標是建立對應於這個面具值5位。您可以使用按位或運算符（|）來完成此操作。首先，創建對應於所述值5

uint bitpattern = 1u << 4; // 1u << (int)(value - 1u) 

，然後使用operator |設置位掩碼maskForNumbersSetInRow[3]

maskForNumbersSetInRow[3] = maskForNumbersSetInRow[3] | bitpattern; 

或使用較短的形式的比特模式

maskForNumbersSetInRow[3] |= bitpattern; 

00000000 00000000 00000001 01001011 
       | 
00000000 00000000 00000000 00010000 
       = 
00000000 00000000 00000001 01011011 

現在您的掩碼錶示此行中有值{1, 2, 4, 5, 7, 9}（第3行）。

如果你想檢查，如果有一些值在行中，你可以使用operator &來檢查掩碼中是否設置了相應的位。如果該運算符的結果應用於掩碼，並且與該值相對應的位模式不爲零，則該值已在該行中。如果結果爲0，則該值不在該行中。

例如，如果你想檢查是否值3行中，你可以做這樣：

uint bitpattern = 1u << 2; // 1u << (int)(value - 1u) 
bool value3IsInRow = ((maskForNumbersSetInRow[3] & bitpattern) != 0); 

00000000 00000000 00000001 01001011 // the mask 
       | 
00000000 00000000 00000000 00000100 // bitpattern for the value 3 
       = 
00000000 00000000 00000000 00000000 // the result is 0. value 3 is not in the row. 

下面是在板上設定新的價值，保持適當的位屏蔽起來的方法到目前爲止，並檢查移動是否合法。

public void insertNewValue(int row, int col, uint value) 
{ 

    if(!isMoveLegal(row, col, value)) 
     throw ... 

    theBoard[row, col] = value; 

    uint bitpattern = 1u << (int)(value - 1u); 

    maskForNumbersSetInRow[row] |= bitpattern; 

    maskForNumbersSetInCol[col] |= bitpattern; 

    int boxRowNumber = row/3; 
    int boxColNumber = col/3; 

    maskForNumbersSetInBox[boxRowNumber, boxColNumber] |= bitpattern; 

} 

具有口罩，你可以檢查，如果此舉是法律是這樣的：

public bool isMoveLegal(int row, int col, uint value) 
{ 

    uint bitpattern = 1u << (int)(value - 1u); 

    int boxRowNumber = row/3; 
    int boxColNumber = col/3; 

    uint combinedMask = maskForNumbersSetInRow[row] | maskForNumbersSetInCol[col] 
         | maskForNumbersSetInBox[boxRowNumber, boxColNumber]; 

    return ((theBoard[row, col] == 0) && ((combinedMask & bitpattern) == 0u); 
} 

Answer 11

您將使用他們因爲各種原因：（！和檢查）

• 存儲選項標誌以有效的內存方式運行
• 如果要進行計算編程，您可能需要考慮通過使用按位運算來代替m來優化某些操作數學運營商（小心副作用）
• Gray Code！
• 創建枚舉值

我相信你能想到別人。

這就是說，有時候你需要問自己：記憶和性能提升是否值得付出努力。寫完那種代碼之後，讓它休息一段時間然後回到它。如果您遇到困難，請使用更易維護的代碼進行重寫。

另一方面，有時使用按位操作確實很有意義（想想密碼學）。

更好的是，讓其他人閱讀並廣泛地記錄。

Answer 12

遊戲！

回到過去，我用它代表了黑白棋的棋子。這是8X8，所以它花了我long類型，並比例如，如果你想知道哪裏是所有板塊 - 你or兩個球員件。
如果你想要一個球員的所有可能的步驟，說到右邊 - 你>>球員的作品表示一個，並AND它與對手的片斷，以檢查是否有現在普通的1（這意味着有一個對手件你的權利）。然後你繼續這樣做。如果你回到你自己的東西 - 不動。如果你清楚了一點 - 你可以在那裏移動，並捕獲途中的所有碎片。
（這種技術被廣泛使用，在多種棋類遊戲，包括國際象棋）

Answer 13

Dozens of bit twiddling examples here

的代碼是C，但你可以很容易地適應C＃