位运算的实际应用

Question

1. 你曾经用过位运算做什么？
2. 它们为什么如此方便？
3. 有人可以推荐一个非常简单的教程吗？

- Alex Gordon

---

位运算符的真实世界应用案例 - phuclv

Answer 1

虽然似乎每个人都沉迷于标志用例，但这并不是位运算符的唯一应用（尽管可能是最常见的）。此外，C# 是一种高级语言，其他技术可能很少使用，但了解它们仍然是值得的。以下是我能想到的：

---

<< 和 >> 运算符可以快速将数字乘以 2 的幂次方。当然，.NET JIT 优化器可能会为您完成（任何一个像样的编译器也会），但如果您真的担心每微秒的时间，您可以编写代码来确保。

这些运算符的另一个常见用途是将两个 16 位整数塞进一个 32 位整数中，如下所示：

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

这种技巧在直接与Win32函数交互时很常见，因为有时出于遗留原因会使用这种技巧。

当然，如果你想要在回答作业问题时让未经验的人感到困惑，这些运算符也是很有用的。 :)

不过在任何真正的代码中，你最好使用乘法代替，因为它更易读，而且JIT会将其优化为shl和shr指令，所以没有性能损失。

---

^（异或）操作符有很多巧妙的技巧。由于以下特性，它实际上是一个非常强大的操作符：

• 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();
    }
}

- Vilx-

---

+1，美妙的异或交换。谢谢。 - Grozz

感谢您对异或链表方法的支持，我之前还没有见过这种方法。 - snemarch

有趣的是这被标记为“不具建设性” :) - Alex Gordon

当你想要困惑没有经验的人时，这是许多高级开发人员/架构师的常见做法。我曾真诚地认为随着经验的增长会带来谦虚务实的态度，但不幸的是并非如此。Brogrammers已经接管了世界，这使得世界变得更糟。 - Davos

在任何真实的代码中，你最好使用乘法而不是加法，因为它具有更好的可读性，并且JIT会将其优化为shl和shr指令，因此没有性能惩罚。为什么代码高尔夫在现实代码中如此普遍？ - Davos

Answer 2

我在我的应用程序中使用位运算符来进行安全操作。我将把不同的级别存储到一个Enum中：

[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
}

- Justin Niessner

---

@Justin，非常感谢你。你能否解释一下这个User.Permissions = SecurityLevel.SuperUser | SecurityLevel.AnswerAdmin的意思？ - Alex Gordon

@Dave - 没错。但是当您使用标记枚举时，您将使用位运算符来检查值。方便而相当简单。在我看来，这正是OP所要求的。 - Justin Niessner

@Justin: 虽然现在已经过时，但仍有 Enum.HasFlag 方法可用：http://msdn.microsoft.com/en-us/library/system.enum.hasflag.aspx - Reed Copsey

@Reed - 确实。它仍然作为一个例子很有用（因为我猜测Enum.HasFlags的实现在内部也是这样做的）。 - Justin Niessner

@Chris：是的，如果你没有注意到的话 :-P - Dave

Answer 3

我不知道解数独对你来说有多实用，但我们假设它是实用的。

想象一下，你想编写一个解数独的程序或者仅仅是一个简单的程序，能够显示出数独棋盘并让你自己解决难题，同时确保每步都符合规则。

这个棋盘本身很可能会用二维数组表示：

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

数值0表示单元格仍为空，范围为[1u，9u]的值是棋盘上的实际值。

现在想象一下，您想要检查某个移动是否合法。显然，您可以使用几个循环来完成，但是位掩码可以让事情更快。在一个简单的程序中，只需要确保遵守规则即可，但在求解器中，速度就很重要了。

您可以维护位掩码数组，其中存储有关已插入每行、每列和每个3x3框中数字的信息。

uint [] maskForNumbersSetInRow = new uint[9];

uint [] maskForNumbersSetInCol = new uint[9];

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

将数字映射为位模式，其中与该数字对应的一个位被设置，非常简单。

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，它将被左移value - 1个位置。例如，如果value == 5，则会得到：

00000000 00000000 00000000 00010000

一开始，每行、每列和每个宫格的掩码都是0。每次在数独盘上放置数字时，都会更新掩码，因此与新值相对应的位被设置为1。

假设您在第3行（行和列编号从0开始）插入了值为5的数字。第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)

然后使用运算符|将位设置在掩码maskForNumbersSetInRow [3]中。

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

或者使用更短的形式

maskForNumbersSetInRow[3] |= bitpattern;

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

现在，您的掩码表示此行（第3行）中存在值{1, 2, 4, 5, 7, 9}。

如果要检查某个值是否在该行中，您可以使用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);
}

- Maciej Hehl

---

非常有趣的内容，但有些难以理解。似乎需要进一步解释（例如带有一些示例的注释）。构建掩码时的位移操作让我有些困惑。只是想问一下，因为您显然花了一些时间回答。 - Mark

Answer 4

这里有几十个位操作示例

代码是用C编写的，但您可以轻松地将其适应于C#。

- Thomas Levesque

Answer 5

1. 它们可以通过一个有限大小的变量向函数传递多个参数。
2. 优点是低内存开销或低内存成本：因此提高了性能。
3. 我无法即时编写教程，但我相信它们已经存在。

- C.J.

---

糟糕，我刚才看到你标记了C#，我以为它是C++。我必须读得更慢... :) - C.J.

Answer 6

如果你需要与硬件进行通信，你在某个时候需要使用位操作。

提取像素值的RGB值。

有很多事情。

- James

Answer 7

在C#中，我最常使用哈希码。有一些相当不错的哈希方法可以使用。例如，对于一个包含两个整数X和Y的坐标类，我可能会使用以下代码：

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，但我仅提供这个例子来说明这通常是一个坏主意，因为它隐藏了真实代码的意图，几乎没有提高性能，并可能隐藏一些微妙的错误。

- Jon Hanna

---

从技术上讲，位移运算符不能被视为按位运算符。请查看维基百科文章的位移部分以了解原因：http://en.wikipedia.org/wiki/Bitwise_operation - Justin Niessner

Answer 8

它们可以用于许多不同的应用程序，这里是我之前发布过的一个问题，其中使用了位运算符：

Bitwise AND、Bitwise Inclusive OR question, in Java

对于其他示例，请查看（例如）标记的枚举。

在我的示例中，我使用位运算来将二进制数字的范围从-128...127更改为0..255（将其表示从有符号更改为无符号）。

此处有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

非常技术性，它涵盖了所有内容。

希望对你有所帮助。

- Dave

Answer 9

每当您有一个选项可以选择1个或多个项目的组合时，位运算通常是一种简单的解决方法。

一些例子包括安全位（等待Justin的示例..），调度天数等。

- NotMe

Answer 10

我认为最常见的用途之一是修改位域以压缩数据。这在试图节省数据包的程序中经常出现。 使用位域进行网络压缩的示例。

- Greg Buehler