按位运算的实际应用

Question

1. 你有什么用bitwise操作？
2. 他们为什么这么方便？
3. 有人可以推荐一个非常简单的教程吗？

Answer 1

虽然每个人似乎都迷上了标志用例,但这并不是按位运算符的唯一应用(虽然可能是最常见的).此外,C#是一种足够高级别的语言,其他技术可能很少使用,但仍然值得了解它们.这是我能想到的:

在<<与>>运营商可以迅速地乘的2场的力量,.NET JIT优化器将可能是你(和另一种语言的任何像样的编译器以及)做到这一点,但如果你每微秒真的心乱了,你只是可能会写这个以确定.

这些运算符的另一个常见用途是将两个16位整数填充为一个32位整数.喜欢:

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

这对于与Win32函数的直接接口很常见,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

我在应用程序中使用按位运算符来保证安全性.我将在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
}

Answer 3

我不知道解决你认为的数独是多么实用,但让我们假设它是.

想象一下,你想要写一个数独解算器,甚至只是一个简单的程序,那说明你的主板,让你自己解决了这个难题,但保证了动作是合法的.

电路板本身很可能由二维数组表示,如:

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

值0表示单元格仍为空,范围[1u,9u]中的值是板中的实际值.

现在想象一下你想检查一些举动是否合法.显然你可以通过几个循环来完成它,但是bitmasks可以让你更快地完成任务.在一个只是确保遵守规则的简单程序中,它并不重要,但在解决方案中它可以.

您可以维护位掩码数组,这些数组存储有关已插入每行,每列a和每个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对应于bitpattern 的行中00000000 00000000 00000000 00000001左移value - 1.例如value == 5,如果你得到了

00000000 00000000 00000000 00010000

在开始时,每个行,列和框的掩码是0.每次在板上放置一些数字时,都会更新掩码,因此设置了与新值对应的位.

假设您在第3行中插入值5(行和列从0开始编号).存储第3行的掩码maskForNumbersSetInRow[3].我们还假设在插入之前{1, 2, 4, 7, 9},第3行中已有数字.掩码中的位模式maskForNumbersSetInRow[3]如下所示:

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

目标是在此掩码中设置与值5对应的位.您可以使用bitwise或operator(|)来完成.首先,创建对应于值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 4

这里有几十个简单的例子

代码是 C 语言，但您可以轻松地将其改编为 C#