在C语言中，位运算符的应用及其效率？

Question

在C语言中，位运算符的应用及其效率？

cbitwise-operatorsmasking

11

我对位运算符还不熟悉。

我了解逻辑函数是如何工作的以获取最终结果。例如，当您对两个数字进行按位 AND 运算时，最终结果将是这两个数字的AND运算结果（1&0=0; 1&1=1; 0&0=0）。OR、XOR和NOT也是一样。

我不明白它们的应用。我尝试在各处寻找答案，但大多数只是解释了位运算的工作原理。在所有位运算符中，我只理解移位运算符（乘法和除法）的应用。我也遇到了掩码。我知道掩码是使用位 AND 进行操作的，但它的目的是什么，我在哪里以及如何使用它？

你能详细说明一下如何使用掩码吗？OR和XOR有类似的用途吗？

- Sai Maddali

6个回答

3

位运算中的一种应用是检查一个字节中是否设置了单个位。在网络通信中这非常有用，因为协议头试图尽可能地将信息打包到最小的区域内以减少开销。

例如，IPv4头部利用第6个字节的前3位来告诉接收方该IP数据包是否能够被分段，如果可以，则期望更多的分段数据包随后到达。如果这些字段的大小为int（1字节），则每个IP数据包会比必要的大21位。这意味着每天会有大量不必要的数据通过互联网传输。

使用位掩码和位与运算符可以检索这3位。

char mymask = 0x80;
if(mymask & (ipheader + 48) == mymask)
  //the second bit of the 6th byte of the ip header is set

- ryanbwork

3

如前所述，小集合可以快速执行大量操作，交并补（对称差）显然显而易见，但例如以下操作也能有效地完成：

使用 x & -x 获得集合中最低的项
使用 x & (x - 1) 从集合中移除最低的项
添加所有小于最小现有项的项
添加所有高于最小现有项的项
计算它们的基数（虽然算法不是显而易见的）
以某种方式置换集合，即更改项目的索引（并非所有置换都同样有效）
计算包含相同数量项的按字典顺序排序的下一个集合（Gosper's Hack）

1和2及其变体可用于在小型图上构建高效的图算法，例如请参见《计算机程序设计艺术4A》中的算法R。

按位运算的其他应用包括但不限于：

位棋盘，在许多棋类游戏中很重要。没有位棋盘的国际象棋就像没有圣诞老人的圣诞节。它不仅是一种占用空间极少的表示方式，还可以直接对位棋盘进行非平凡计算（请参见Hyperbola Quintessence）
侧面堆及其在查找最近公共祖先和计算范围最小查询方面的应用。
高效的循环检测（Gosper's Loop Detection，在HAKMEM中发现）
在不拆解和重构地址的情况下向Z曲线地址添加偏移量（请参见Tesseral Arithmetic）

这些用途更加强大，但也更为高级、罕见和非常特定。它们表明按位运算不仅仅是留存于旧低级别时代的可爱玩具。

- harold

1

在微控制器应用中，您可以利用位运算在端口之间切换。在下图中，如果我们想要打开单个端口并关闭其他端口，则可以使用以下代码。

void main() 
{
     unsigned char ON = 1;
     TRISB=0;
     PORTB=0;
     while(1){
        PORTB = ON;
        delay_ms(200);
        ON = ON << 1;
        if(ON == 0) ON=1;
     }
}

- CroCo

1

例子 1

如果您有10个布尔值“一起工作”，您可以大大简化代码。

int B1 = 0x01;
int B2 = 0x02;
int B10 = 0x0A;

int someValue = get_a_value_from_somewhere();

if (someValue & (B1 + B10)) {
    // B1 and B10 are set
}

示例2

与硬件交互。硬件上的地址可能需要位级访问以控制接口，例如缓冲区上的溢出位或可以告诉您8个不同事物状态的状态字节。使用位屏蔽，您可以获取到实际需要的信息位。

if (register & 0x80) {
    // top bit in the byte is set which may have special meaning.
}

这实际上只是示例1的一个特殊情况。

- John3136

1

位运算符在资源有限的系统中特别有用，因为每个位可以编码一个布尔值。对于标志，使用许多字符是浪费的，因为每个字符占用一个字节的空间（当它们本来可以存储8个标志）。

通常微控制器具有C接口，用于它们的IO端口，其中每个位控制8个端口之一。如果没有位运算符，这些端口将非常难以控制。

关于掩码，常见使用 & 和 | 两个运算符：

x & 0x0F //ensures the 4 high bits are 0
x | 0x0F //ensures the 4 low bits are 1

- Cameron S

所以，假设我想要提取一个12位数字中的最高有效6位，我应该将该数字与“0x0F”进行或运算，并使用AND运算来提取反之亦然（即最低有效6位）吗？ - Sai Maddali

这取决于您希望其他位是什么。如果希望最低有效的4位为0，则可以将它们与0xF0进行AND运算。 0000xxxx | 11110000 = 1111xxxx（x未改变，只更改特定位时非常有效）。 - Cameron S

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jxh · Accepted Answer

按位运算符的低级应用是进行二进制数学运算。有一个众所周知的技巧，可以测试一个数字是否为2的幂：

if ((x & (x - 1)) == 0) {
    printf("%d is a power of 2\n", x);
}

然而，它也可以用于更高级的功能：集合操作。您可以将一组位视为一个集合。举个例子，让每个字节中的位表示8个不同的项，比如我们太阳系中的行星（冥王星不再被认为是行星，所以8位就足够了！）：

#define Mercury (1 << 0)
#define Venus   (1 << 1)
#define Earth   (1 << 2)
#define Mars    (1 << 3)
#define Jupiter (1 << 4)
#define Saturn  (1 << 5)
#define Uranus  (1 << 6)
#define Neptune (1 << 7)

然后，我们可以像使用|一样形成行星的集合（子集）：

unsigned char Giants = (Jupiter|Saturn|Uranus|Neptune);
unsigned char Visited = (Venus|Earth|Mars);
unsigned char BeyondTheBelt = (Jupiter|Saturn|Uranus|Neptune);
unsigned char All = (Mercury|Venus|Earth|Mars|Jupiter|Saturn|Uranus|Neptune);

现在，您可以使用&来测试两个集合是否有交集：

if (Visited & Giants) {
    puts("we might be giants");
}

通常使用 ^ 运算符来查看两个集合之间的差异（集合的并集减去交集）：

if (Giants ^ BeyondTheBelt) {
    puts("there are non-giants out there");
}

因此，将|视为并集，&视为交集，将^视为除去交集的并集。

一旦您接受了位表示集合的想法，那么按位操作自然就可以帮助您操作这些集合。