language-agnostic - 位运算符的真实世界用例

Question

以下位运算符的一些实际用例是什么？

和
异或
不是
或者
左/右移位

score 249 · Accepted Answer

位域（标志）
它们是表示状态由几个“是或否”属性定义的事物的最有效方式。ACL 就是一个很好的例子。如果您有 4 个离散权限（读取、写入、执行、更改策略），最好将其存储在 1 个字节中而不是浪费 4 个。这些可以映射到多种语言的枚举类型以增加便利性。
通过端口/套接字进行的通信
总是涉及校验和、奇偶校验、停止位、流控制算法等，这些通常取决于单个字节的逻辑值而不是数值，因为介质可能只能在一次。
压缩、加密
这两者都严重依赖于按位算法。以deflate算法为例——一切都以位为单位，而不是字节。
有限状态机
我说的主要是嵌入在某些硬件中的那种，尽管它们也可以在软件中找到。这些本质上是组合的——它们可能真的被“编译”成一堆逻辑门，所以它们必须表示为AND、OR、NOT等。
图形这里几乎没有足够的空间来介绍在图形编程中使用这些运算符的每个领域。 XOR（或^）在这里特别有趣，因为第二次应用相同的输入将撤消第一次。较旧的 GUI 过去依赖于此进行选择突出显示和其他覆盖，以消除代价高昂的重绘需求。它们在慢速图形协议（即远程桌面）中仍然有用。

这些只是我想出的前几个例子——这并不是一个详尽的清单。

score 56 · Accepted Answer

56

奇怪吗？

(value & 0x1) > 0

它可以被两个（偶数）整除吗？

(value & 0x1) == 0

于 2010-01-19T21:37:47.680 回答

score 32 · Accepted Answer

我在实现 CMS 的安全模型时使用了按位运算。如果用户在适当的组中，它具有可供用户访问的页面。一个用户可以在多个组中，所以我们需要检查用户组和页面组之间是否存在交叉。因此，我们为每个组分配了一个唯一的 2 次幂标识符，例如：

Group A = 1 --> 00000001
Group B = 2 --> 00000010
Group C = 3 --> 00000100

我们将这些值 OR 在一起，并将值（作为单个 int）存储在页面中。例如，如果一个页面可以被组 A 和 B 访问，我们存储值 3（二进制为 00000011）作为页面访问控制。以同样的方式，我们将 ORed 组标识符的值与用户一起存储，以表示他们所在的组。

因此，要检查给定用户是否可以访问给定页面，您只需要将这些值组合在一起并检查该值是否非零。这是非常快的，因为这个检查是在一条指令中实现的，没有循环，没有数据库往返。

score 28 · Accepted Answer

下面是一些处理作为单个位存储的标志的常见习语。

enum CDRIndicators {
  Local = 1 << 0,
  External = 1 << 1,
  CallerIDMissing = 1 << 2,
  Chargeable = 1 << 3
};

unsigned int flags = 0;

设置 Chargeable 标志：

flags |= Chargeable;

清除 CallerIDMissing 标志：

flags &= ~CallerIDMissing;

测试是否设置了 CallerIDMissing 和 Chargeable：

if((flags & (CallerIDMissing | Chargeable )) == (CallerIDMissing | Chargeable)) {

}

score 27 · Accepted Answer

低级编程就是一个很好的例子。例如，您可能需要将特定位写入内存映射寄存器，以使某些硬件执行您想要的操作：

volatile uint32_t *register = (volatile uint32_t *)0x87000000;
uint32_t          value;
uint32_t          set_bit   = 0x00010000;
uint32_t          clear_bit = 0x00001000;

value = *register;            // get current value from the register
value = value & ~clear_bit;   // clear a bit
value = value | set_bit;      // set a bit
*register = value;            // write it back to the register

此外，htonl()andhtons()使用&and|运算符实现（在字节序（字节顺序）与网络顺序不匹配的机器上）：

#define htons(a) ((((a) & 0xff00) >> 8) | \
                  (((a) & 0x00ff) << 8))

#define htonl(a) ((((a) & 0xff000000) >> 24) | \
                  (((a) & 0x00ff0000) >>  8) | \
                  (((a) & 0x0000ff00) <<  8) | \
                  (((a) & 0x000000ff) << 24))

score 22 · Accepted Answer

22

例如，我使用它们从打包的颜色值中获取 RGB(A) 值。

于 2010-01-19T20:51:07.863 回答

score 16 · Accepted Answer

当我有一堆布尔标志时，我喜欢将它们全部存储在一个 int 中。

我使用按位与将它们取出。例如：

int flags;
if (flags & 0x10) {
  // Turn this feature on.
}

if (flags & 0x08) {
  // Turn a second feature on.
}

等等

score 15 · Accepted Answer

& = AND：
屏蔽特定位。
您正在定义应该显示或不显示的特定位。0x0 & x 将清除一个字节中的所有位，而 0xFF 不会更改 x。0x0F 将显示低半字节中的位。

转换：
要将较短的变量转换为具有位标识的较长变量，需要调整位，因为 int 中的 -1 是 0xFFFFFFFF，而 long 中的 -1 是 0xFFFFFFFFFFFFFFFF。为了保留身份，您在转换后应用掩码。

|=OR
设置位。如果它们已经设置，这些位将被单独设置。许多数据结构（位域）具有 IS_HSET = 0、IS_VSET = 1 等标志，可以独立设置。要设置标志，请应用 IS_HSET | IS_VSET（在 C 和汇编中，这非常便于阅读）

^=XOR
查找相同或不同的位。

~= 不
翻转位。

可以看出，所有可能的局部位操作都可以通过这些操作来实现。因此，如果您愿意，可以仅通过位操作来实现 ADD 指令。

一些很棒的技巧：

http://www.ugcs.caltech.edu/~wnoise/base2.html
http://www.jjj.de/bitwizardry/bitwizardrypage.html

score 11 · Accepted Answer

11

加密都是按位运算。

于 2010-01-19T20:51:27.190 回答

score 10 · Accepted Answer

您可以将它们用作散列数据的快速而肮脏的方法。

int a = 1230123;
int b = 1234555;
int c = 5865683;
int hash = a ^ b ^ c;

score 9 · Accepted Answer

大约三分钟前，我刚刚使用按位异或 ( ^) 来计算与 PLC 进行串行通信的校验和......

score 8 · Accepted Answer

这是一个以字节格式从位图图像中读取颜色的示例

byte imagePixel = 0xCCDDEE; /* Image in RRGGBB format R=Red, G=Green, B=Blue */

//To only have red
byte redColour = imagePixel & 0xFF0000; /*Bitmasking with AND operator */

//Now, we only want red colour
redColour = (redColour >> 24) & 0xFF;  /* This now returns a red colour between 0x00 and 0xFF.

我希望这个小例子有帮助....

score 7 · Accepted Answer

按位 & 用于屏蔽/提取字节的特定部分。

1 字节变量

 01110010
&00001111 Bitmask of 0x0F to find out the lower nibble
 --------
 00000010

特别是移位运算符 (<< >>) 经常用于计算。

score 7 · Accepted Answer

在当今现代语言的抽象世界中，并没有太多。文件 IO 是一个很容易想到的问题，尽管它是对已经实现的东西执行按位操作，而不是实现使用按位操作的东西。尽管如此，作为一个简单的示例，此代码演示了在 c# 中删除文件的只读属性（以便它可以与指定 FileMode.Create 的新 FileStream 一起使用）：

//Hidden files posses some extra attibutes that make the FileStream throw an exception
//even with FileMode.Create (if exists -> overwrite) so delete it and don't worry about it!
if(File.Exists(targetName))
{
    FileAttributes attributes = File.GetAttributes(targetName);

    if ((attributes & FileAttributes.ReadOnly) == FileAttributes.ReadOnly)
        File.SetAttributes(targetName, attributes & (~FileAttributes.ReadOnly));

    File.Delete(targetName);
}

至于自定义实现，这里有一个最近的例子：我创建了一个“消息中心”，用于将安全消息从我们的分布式应用程序的一个安装发送到另一个安装。基本上，它类似于电子邮件，包括收件箱、发件箱、已发送等，但它也有已读回执的保证交付，因此除了“收件箱”和“已发送”之外还有其他子文件夹。这相当于要求我笼统地定义“收件箱中”或“已发送文件夹中”的内容。在已发送的文件夹中，我需要知道哪些已读，哪些未读。对于未读的内容，我需要知道已收到的内容和未收到的内容。我使用这些信息来构建一个动态 where 子句，该子句过滤本地数据源并显示适当的信息。

以下是枚举的组合方式：

    public enum MemoView :int
    {
        InboundMemos = 1,                   //     0000 0001
        InboundMemosForMyOrders = 3,        //     0000 0011
        SentMemosAll = 16,                  //     0001 0000
        SentMemosNotReceived = 48,          //     0011
        SentMemosReceivedNotRead = 80,      //     0101
        SentMemosRead = 144,                //     1001
        Outbox = 272,                       //0001 0001 0000
        OutBoxErrors = 784                  //0011 0001 0000
    }

你明白这是做什么的吗？通过与“收件箱”枚举值 InboundMemos 进行与运算 (&)，我知道 InboundMemosForMyOrders 在收件箱中。

这是该方法的简化版本，该方法构建并返回为当前选定文件夹定义视图的过滤器：

    private string GetFilterForView(MemoView view, DefaultableBoolean readOnly)
    {
        string filter = string.Empty;
        if((view & MemoView.InboundMemos) == MemoView.InboundMemos)
        {
            filter = "<inbox filter conditions>";

            if((view & MemoView.InboundMemosForMyOrders) == MemoView.InboundMemosForMyOrders)
            {
                filter += "<my memo filter conditions>";
            }
        }
        else if((view & MemoView.SentMemosAll) == MemoView.SentMemosAll)
        {
            //all sent items have originating system = to local
            filter = "<memos leaving current system>";

            if((view & MemoView.Outbox) == MemoView.Outbox)
            {
                ...
            }
            else
            {
                //sent sub folders
                filter += "<all sent items>";

                if((view & MemoView.SentMemosNotReceived) == MemoView.SentMemosNotReceived)
                {
                    if((view & MemoView.SentMemosReceivedNotRead) == MemoView.SentMemosReceivedNotRead)
                    {
                        filter += "<not received and not read conditions>";
                    }
                    else
                        filter += "<received and not read conditions>";
                }
            }
        }

        return filter;
    }

非常简单，但在抽象级别上的简洁实现通常不需要按位操作。

score 5 · Accepted Answer

通常按位运算比乘法/除法更快。因此，如果您需要将变量 x 乘以 9，您x<<3 + x将比 . 快几个周期x*9。如果此代码在 ISR 中，您将节省响应时间。

同样，如果您想将数组用作循环队列，使用按位操作处理环绕检查会更快（也更优雅）。（您的数组大小应该是 2 的幂）。例如：，如果您想插入/删除，您可以使用tail = ((tail & MASK) + 1)代替。tail = ((tail +1) < size) ? tail+1 : 0

此外，如果您希望错误标志将多个错误代码保存在一起，则每个位都可以保存一个单独的值。您可以将其与每个单独的错误代码一起作为检查。这用于 Unix 错误代码。

此外，n 位位图可以是一个非常酷且紧凑的数据结构。如果要分配一个大小为 n 的资源池，我们可以用一个 n 位来表示当前状态。

score 4 · Accepted Answer

Base64 编码就是一个例子。Base64 编码用于将二进制数据表示为可打印字符，以便通过电子邮件系统（和其他目的）发送。Base64 编码将一系列 8 位字节转换为 6 位字符查找索引。位操作、移位和'ing，or'ing，not'ing对于实现Base64编码和解码所需的位操作非常有用。

这当然只是无数例子中的一个。

score 4 · Accepted Answer

我很惊讶没有人为互联网时代挑选出明显的答案。计算子网的有效网络地址。

http://www.topwebhosts.org/tools/netmask.php

score 4 · Accepted Answer

4

似乎没有人提到定点数学。

（是的，我老了，好吗？）

于 2010-01-19T23:32:49.770 回答

score 4 · Accepted Answer

位运算符对于循环长度为 2 的幂的数组很有用。正如许多人提到的，位运算符非常有用，用于标志、图形、网络、加密。不仅如此，它们的速度也非常快。我个人最喜欢的用途是循环一个不带条件的数组。假设您有一个基于零索引的数组（例如，第一个元素的索引为 0）并且您需要无限循环它。无限期地，我的意思是从第一个元素到最后一个元素并返回到第一个元素。实现这一点的一种方法是：

int[] arr = new int[8];
int i = 0;
while (true) {
    print(arr[i]);
    i = i + 1;
    if (i >= arr.length) 
        i = 0;
}

这是最简单的方法，如果您想避免使用if语句，可以使用模数方法，如下所示：

int[] arr = new int[8];
int i = 0;
while (true) {
    print(arr[i]);
    i = i + 1;
    i = i % arr.length;
}

这两种方法的缺点是模运算符很昂贵，因为它在整数除法之后寻找余数。第一种方法在每次迭代时运行一个if语句。但是，如果使用按位运算符，如果数组的长度是 2 的幂，则可以0 .. length - 1通过使用&(bitwise and) 运算符轻松生成类似的序列i & length。所以知道了这一点，上面的代码就变成了

int[] arr = new int[8];
int i = 0;
while (true){
    print(arr[i]);
    i = i + 1;
    i = i & (arr.length - 1);
}

下面是它的工作原理。在二进制格式中，每个 2 的幂减去 1 的数字仅用 1 表示。例如二进制中的 3 is 11， 7 is 111， 15 is1111等等，你明白了。现在，如果你&对一个只包含二进制数字的数字有任何数字会发生什么？假设我们这样做：

num & 7;

如果num小于或等于 7，那么结果将是num因为每个&带有 1 的位都是它自己。如果num大于7，则在&运算过程中计算机会考虑7的前导零，当然&运算后会保持为零，只保留尾部。就像在9 & 7二进制的情况下它看起来像

1001 & 0111

结果将是 0001，它是十进制的 1，并寻址数组中的第二个元素。

score 3 · Accepted Answer

数字x是2的幂吗？（例如在计数器递增的算法中很有用，并且一个动作只执行对数次）

(x & (x - 1)) == 0

哪个是整数的最高位x？（例如，这可用于找到大于 2 的最小幂x）

x |= (x >>  1);
x |= (x >>  2);
x |= (x >>  4);
x |= (x >>  8);
x |= (x >> 16);
return x - (x >>> 1); // ">>>" is unsigned right shift

哪个是1整数的最低位x？（帮助找到可被 2 整除的次数。）

x & -x

score 3 · Accepted Answer

如果您想计算您的数字 mod(%) 的某个幂 2，您可以使用yourNumber & 2^N-1，在这种情况下与相同yourNumber % 2^N。

number % 16 = number & 15;
number % 128 = number & 127;

这可能仅作为模运算的替代方法有用，它的除数很大，即 2^N ......但即便如此，在我对 .NET 2.0 的测试中，它对模运算的速度提升也可以忽略不计。我怀疑现代编译器已经执行了这样的优化。有人知道更多吗？

score 2 · Accepted Answer

2

我将它们用于多选选项，这样我只存储一个值而不是 10 个或更多

于 2010-01-19T20:48:11.537 回答

score 2 · Accepted Answer

当您只想更改微控制器输出的某些位，但要写入的寄存器是一个字节时，您可以执行以下操作（伪代码）：

char newOut = OutRegister & 0b00011111 //clear 3 msb's
newOut = newOut | 0b10100000 //write '101' to the 3 msb's
OutRegister = newOut //Update Outputs

当然，许多微控制器允许您单独更改每个位......

score 2 · Accepted Answer

它在 sql 关系模型中也很方便，假设您有以下表格：BlogEntry、BlogCategory

传统上，您可以使用 BlogEntryCategory 表在它们之间创建 nn 关系，或者当没有那么多 BlogCategory 记录时，您可以使用 BlogEntry 中的一个值来链接到多个 BlogCategory 记录，就像使用标记的枚举一样，在大多数 RDBMS 中也有在“标记”列上选择一个非常快速的运算符...

score 1 · Accepted Answer

1

我已经看到它们用于基于角色的访问控制系统。

于 2010-01-19T20:56:33.390 回答

score 1 · Accepted Answer

每当我第一次开始 C 编程时，我都了解真值表和所有这些，但是直到我阅读了这篇文章http://www.gamedev.net/reference/articles/article1563.asp之前，我并没有完全了解如何实际使用它（给出了现实生活中的例子）

score 1 · Accepted Answer

我经常使用按位运算将选项组合存储在单个整数中。

int options = 0;

其中OPTION1可以定义OPTION2为OPTION31、2、4、8、16 OPTION4、OPTION5...

void addOption(int option)将使用|运算符向选项添加选项。

boolean hasOption(int option)将使用&运算符来测试选项中的选项。

score 1 · Accepted Answer

我的问题在这里有一个真实的世界用途 -
只响应第一个 WM_KEYDOWN 通知？

当在 windows C api 中使用 WM_KEYDOWN 消息时，第 30 位指定先前的键状态。如果在发送消息之前 key 处于 down 状态，则值为 1，如果 key 处于 up 状态，则值为 0

score 1 · Accepted Answer

它们主要用于按位运算（惊喜）。以下是 PHP 代码库中的一些真实示例。

字符编码：

if (s <= 0 && (c & ~MBFL_WCSPLANE_MASK) == MBFL_WCSPLANE_KOI8R) {

数据结构：

ar_flags = other->ar_flags & ~SPL_ARRAY_INT_MASK;

数据库驱动程序：

dbh->transaction_flags &= ~(PDO_TRANS_ACCESS_MODE^PDO_TRANS_READONLY);

编译器实现：

opline->extended_value = (opline->extended_value & ~ZEND_FETCH_CLASS_MASK) | ZEND_FETCH_CLASS_INTERFACE;

score 1 · Accepted Answer

我在一些游戏开发书籍中看到它是一种更有效的乘法和除法方法。

2 << 3 == 2 * 8 
32 >> 4 == 32 / 16

score 1 · Accepted Answer

我不认为这算作按位计算，但 ruby 的 Array 通过普通整数按位运算符定义集合操作。所以[1,2,4] & [1,2,3] # => [1,2]。同样对于a ^ b #=> set difference和a | b #=> union。

score 1 · Accepted Answer

汉诺塔线性解决方案使用按位运算来解决问题。

public static void linear(char start, char temp, char end, int discs)
{
    int from,to;
    for (int i = 1; i < (1 << discs); i++) {
        from = (i & i-1) % 3;
        to = ((i | i-1) + 1) % 3;
        System.out.println(from+" => "+to);
    }
}

可以在此处找到此解决方案的说明

score 0 · Accepted Answer

我将它们用作选项处理程序，例如在访问控制列表中描述特定资源。

看看这篇文章http://planetozh.com/blog/2006/05/php-bitwise-operators-example-of-use/

编辑：

另一个链接： http: //blog.code-head.com/how-to-write-a-permission-system-using-bits-and-bitwise-operations-in-php

score 0 · Accepted Answer

不久前我写了一篇小的 wiki 文章，展示了一个二进制 writer/reader。它适用于位级别，并展示了如何使用位运算符来打包数据。这可能是一个“现实世界”的例子，因为它在游戏中有应用。

score 0 · Accepted Answer

我一直假设按位运算是要执行的相当简单的运算，因此当运行时间至关重要时，通过位集实现的解决方案可以将运行时间提高一个常数，具体取决于算法。

score 0 · Accepted Answer

数据库世界中的另一个真实世界应用程序是 MySQL，它具有称为SET的数据类型。

位运算符由 DBMS 来存储 SET 数据类型。设置可以节省空间。

Element    SET Value    Decimal Value
Travel      00000001    1
Sports      00000010    2
Dancing    00000100    4
Fine Dining   00001000  8

score 0 · Accepted Answer

0

我使用它们来实现快速 BCD 计算（会计师和审计师对 fp 舍入感到不安）。

于 2010-01-19T22:41:35.367 回答

score 0 · Accepted Answer

0

我们使用 Bitwise Flags 使会话更小，以便在我们的内部网站上登录权限。

于 2010-01-19T22:45:59.223 回答

score 0 · Accepted Answer

一个非常具体的例子，但我用它们让我的数独求解器运行得更快（我正在和一个朋友比赛）

每列、每行和 3x3 都表示为一个无符号整数，当我设置数字时，我会为相关列、行和 3x3 正方形中设置的数字标记适当的位。

这使得很容易看到我可以在给定的正方形中放置哪些可能的数字，因为我会将右列、行和 3x3 正方形或在一起，而不是给我留下一个表示给定可能合法值的掩码位置。

希望这是有道理的。

score 0 · Accepted Answer

还没有人提到收藏。有时你有一个很小的可能值集合，比如只有 10 或 20 个可能的值，并且你希望将其中的一些保留在一个集合中。Set当然，您可以使用很可能使用支持哈希表的常规实现。但由于可能值的集合是如此之小，这实际上只是浪费时间和空间。相反，您可以将集合存储在单个int或值中，如果我没记错的话long，这正是 java 所做的。EnumSet

score 0 · Accepted Answer

一个常见的用途是对齐，例如我需要我的数据在 4 字节或 16 字节边界上对齐。这在 RISC 处理器中很常见，其中未对齐的加载/存储要么很昂贵（因为它触发了一个异常处理程序，然后需要修复增加未对齐的负载）或根本不允许。

对于任何 2 的幂的对齐，下一个对齐的 pos 可以计算如下：

aligned_offset = alignment + ((current_offset - 1) & ~(alignment - 1))

因此，在 4 字节对齐和当前偏移量为 9 的情况下：

aligned_offset = 4 + ((9-1) & ~(4-1)) = 4 + (8 & 0xFFFFFFFC) = 4+ 8  = 12

所以下一个 4 字节对齐的偏移量将是 12

language-agnostic - 位运算符的真实世界用例

41 回答 41

Related

Reference