使用位运算符

4
我一直在学习C#,发现一些与我的旧工作C++相似的地方。我从未理解过位运算符在实际应用中的原因。我从未使用过它们,也没有必要使用它们。我一直在学习它们的工作方式;下面的示例显示了移位位运算符。什么是位运算符的意义、用途和工作原理?
也许我在位逻辑方面有所遗漏。
byte bitComp = 15;              // bitComp = 15 = 00001111b
byte bresult = (byte) ~bitComp; // bresult = 240 = 11110000b

下面是一个补码位运算符的例子:

byte bitComp = 15;              // bitComp = 15 = 00001111b
byte bresult = (byte) ~bitComp; // bresult = 240 = 11110000b
12个回答

17

一个典型的用途是操纵表示互斥“标志”的位。

来自 MSDN 的示例:枚举类型

[Flags]
enum Days2
{
    None = 0x0,
    Sunday = 0x1,
    Monday = 0x2,
    Tuesday = 0x4,
    Wednesday = 0x8,
    Thursday = 0x10,
    Friday = 0x20,
    Saturday = 0x40
}

class MyClass
{
    Days2 meetingDays = Days2.Tuesday | Days2.Thursday;

    Days2 notWednesday = ~(Days2.Wednesday);
}

另请参阅Stack Overflow问题最常见的C#按位操作


8

以下是很少有人发现的每天位运算技巧:

当您拥有一个表示位字段的枚举类型时,您需要将每个枚举条目定义为不同的位值,例如:

enum
{
    Option1 = 1,
    Option2 = 2,
    Option3 = 4,
    Option4 = 8,
    Option5 = 16
};

但很容易忘记数列中下一个项需要是上一个数字的两倍。使用位移操作可以使数列更容易正确得到:

enum
{
    Option1 = 1<<0,
    Option2 = 1<<1,
    Option3 = 1<<2,
    Option4 = 1<<3,
    Option5 = 1<<4
};

3
使用 [Flags] 特性时更是如此。 http://msdn.microsoft.com/zh-cn/library/system.flagsattribute.aspx - kenny

5

另一种典型(但我认为较少见)的用途是将几个数字组合成一个大数字。一个例子是Windows RGB宏:

#define RGB(r, g ,b)  ((DWORD) (((BYTE) (r) | ((WORD) (g) << 8)) | (((DWORD) (BYTE) (b)) << 16)))

当你取3个字节并将它们组合成一个整数来代表RGB值时。


4

除了组合标志外,位逻辑在UI代码中并不一定是必需的,但它仍然非常重要。例如,我维护一个二进制序列化库,需要处理各种复杂的位打包策略(例如变长基于128位的整数编码)。以下是其中一个实现(实际上,这是一个较慢/更安全的版本-有其他用于处理缓冲数据的变体,但它们更难以理解):

    public static bool TryDecodeUInt32(Stream source, out uint value)
    {
        if (source == null) throw new ArgumentNullException("source");

        int b = source.ReadByte();
        if (b < 0)
        {
            value = 0;
            return false;
        }

        if ((b & 0x80) == 0)
        {
            // single-byte
            value = (uint) b;
            return true;
        }

        int shift = 7;

        value = (uint)(b & 0x7F);
        bool keepGoing;
        int i = 0;
        do
        {
            b = source.ReadByte();
            if (b < 0) throw new EndOfStreamException();
            i++;
            keepGoing = (b & 0x80) != 0;
            value |= ((uint)(b & 0x7F)) << shift;
            shift += 7;
        } while (keepGoing && i < 4);
        if (keepGoing && i == 4)
        {
            throw new OverflowException();
        }
        return true;
    }

我们有:
  • 测试最高有效位是否设置(这会改变数据的含义)
  • 大量使用移位操作
  • 删除最高有效位
  • 按位组合值
这是真实的代码,用于一个真实且广泛使用的协议中。通常,在任何编码层中都会大量使用位操作。
例如,在图形编程中,它也非常重要。还有许多其他领域也需要用到。
此外,还可以通过位操作进行一些微小的优化(如数学密集型工作等)。

3

COM编程中的一个例子:

HRESULT是由32位整数组成的错误代码。高位是一个标志,表示该代码代表成功(0)还是失败(1)。接下来的15位是一个整数,表示它是ole自动化错误还是win32错误或其他类型的错误。低16位是实际的错误代码。

当你想把信息输入或输出到HRESULT时,能够移位非常有用。

现在,你几乎总是希望抽象出位操作。最好有一个方法(或在C中是一个宏),告诉你HRESULT是否失败,而不是在源代码中直接用(hr & 0x80000000) != 0进行位操作。让编译器内联它。

有很多低级数据结构的例子,其中信息被压缩到单词中,并需要使用位运算进行提取。


1

最小化内存使用

自然而然的,一个非常普遍的原因是将大量数据压缩到少量的内存中。如果你考虑这样一个布尔数组:

bool data[64] = {...};

那需要占用64字节(512位)的内存。而同一概念可以使用8字节(64位)的内存表示:

uint64_t data = ...;

当然,现在我们有大量的DRAM,所以似乎将所有这些数据压缩到最小尺寸可能并没有什么区别,但我们仍然处理64位通用寄存器。 我们仍在处理64字节的高速缓存行,例如每个物理映射页面的千字节,并且将数据向下移动内存层次结构是昂贵的。 因此,如果您正在顺序处理大量数据,并且可以将其减少到1/8的大小,那么通常您将能够在更短的时间内处理更多的数据。

因此,上面的类比的常见用途是在涉及位标志的情况下将一堆布尔值存储在较小的空间中,例如:

enum Flags
{
     flag_selected =  1 << 0,
     flag_hidden =    1 << 1,
     flag_removed =   1 << 2,
     flag_hovering =  1 << 3,
     flag_minimized = 1 << 4,
     ...
};
uint8_t flags = flag_selected | flag_hovering;

同时操作多个位

除了将所有数据压缩到更小的空间中,您还可以同时测试多个位:

// Check if the element is hidden or removed.
if (flags & (flag_hidden | flag_removed))
{
    ...
}

一个聪明的优化器通常会将其缩减为单个按位与,如果flag_hiddenflag_removed是在编译时已知的字面常量。

作为另一个例子,让我们回到上面的例子:

bool data[64];

假设你想要测试是否所有的64个布尔值都被设置了,如果是的话,你需要执行不同的操作。根据这种表示方式,我们可能需要这样做:
bool all_set = true;
for (int j=0; j < 64; ++j)
{
     if (!data[j])
     {
          all_set = false;
          break;
     }
}
if (all_set)
{
     // Do something different when all booleans are set.
     ...
}

当位运算表示法允许我们这样做时,那就相当昂贵了:

uint64_t data = ...;
if (data == 0xffffffffffffffff)
{
     // Do something different when all bits are set.
     ...
}

在64位机器上,此版本可以使用单个指令执行对所有64位设置的检查。使用SIMD寄存器,您甚至可以使用单个SIMD指令一次测试超过64位。

另一个例子是,假设您想计算设置了多少个布尔值。在这种情况下,您可能需要使用布尔表示进行操作:

int count = 0;
for (int j=0; j < 64; ++j)
     count += data[j];
// do something with count

如果您使用位运算,可以这样做:

uint64_t data = ...;
const int count =  __popcnt64(data);
// do something with count

有些硬件可以作为本地指令非常高效地执行这个任务,而另一些则仍然可以比循环遍历 64 个布尔值并计算被设置为 true 的布尔值的数量更快。

高效的算术运算

另一个常见的问题是高效的算术运算。如果你面对以下类似的情况:

x = pow(2, n);

如果 n 是一个运行时变量,那么你通常可以通过以下方式获得更高效的结果:

x = 1 << n;

当然,使用内置函数的优化编译器可能能够将前者转换为后者,但至少我最近检查过的C和C++编译器在编译时无法执行此优化,至少当n不是在编译时已知的情况下。
每当你处理2的幂时,通常可以使用位移和其他位运算来高效地完成许多操作。例如,考虑以下内容:
x = n % power_of_two;

...其中power_of_two是一个始终为2的幂次方的运行时变量。在这种情况下,您可以执行以下操作:

x = n & (power_of_two - 1);

这与模数运算具有相同的效果(仅适用于2的幂次方)。这是因为2的幂次方值始终是一个设置位后跟着零。例如,16将是0b10000。如果从中减去1,则变为:0b1111,并使用按位与操作将有效地清除所有上位位,以一种类比于n%16的方式。

类似的事情可以用左移来乘以2的幂次方,用右移来除以2的幂次方等等。许多硬件喜欢使用2的幂次方图像大小,如16x16、32x32、64x64、256x256等,其中一个主要原因是它使用位操作指令实现了高效的算术运算。

结论

总之,这是对位运算和指令可以做什么的简要介绍,包括快速算术、减少内存使用以及能够在不循环遍历它们并逐位操作它们的情况下同时对可能的许多位执行操作。

它们在性能关键领域仍然非常相关。例如,如果你看一下Atomontage体素渲染引擎,它声称可以仅用一个比特表示一个体素,这不仅重要是为了将巨大的体素数据适应DRAM,而且还要从较小、快速的存储器(如寄存器)中快速地呈现它。如果它要使用8位来存储需要单独检查的类似true/false值,那么自然无法做到这一点。


1

左移和右移运算符(<< 和 >>)经常在性能关键的应用程序中使用,这些应用程序执行算术运算,更具体地说是乘法和除法,通过二的幂次方。

例如,假设您必须计算数学表达式5*2^7。一个天真的实现方法是:

int result = 5 * (int)Math.Pow(2, 7);

通过使用左移操作符,您可以编写如下代码:

int result = 5 << 7;

第二个表达式将比第一个表达式快几个数量级,但仍会产生相同的结果。

1

从我个人的理解,大概有以下三个主要用途:

1) 在嵌入式应用中,通常需要访问内存映射寄存器,其中每个位都代表着某些特定含义(例如ADC或串行寄存器中的更新位)。这与C#相比更加适用于C++。

2) 计算校验和,如CRC。这需要广泛使用移位和掩码。在任何人提到“使用标准库”之前,我必须指出我已经遇到了太多非标准校验和,不得不从头开始实现。

3) 处理来自另一个平台的数据时,由于位或字节顺序(或两者)与你执行代码的平台不同,需要进行一定的操作。当测试嵌入式系统时,通过网络接收未转换为网络顺序的数据,或者处理来自数据捕获系统的大量数据时,情况尤为突出。可以查看维基百科关于字节序的文章。如果您真的感兴趣,请阅读Danny Cohen的经典文章“关于圣战和呼吁和平”的文章


在“使用标准库”的反对意见上 - 也有人必须编写标准库版本! - Jack Lloyd

1

举几个例子:

  • 通讯协议栈:在通讯协议栈的层级中,附加到数据上的头部可能包含字节,其中字节内的各个位表示某些信息,因此必须进行掩码处理才能被处理。类似地,当组装响应中的头部时,需要设置或清除单独的位。

  • 嵌入式软件:嵌入式微控制器可以有数十或数百个硬件寄存器,在其中每个位(或其集合)控制芯片内不同的功能,或指示硬件的某些部分的状态。

顺便说一下,在 C 和 C++ 中,如果可移植性很重要,则不建议使用位域,因为位域中位的顺序取决于编译器。使用掩码代替可以保证将设置或清除哪个位。


1
关于“它们如何工作”:按位操作是CPU支持的最低级别操作之一,实际上,一些按位操作,比如NAND和NOR,是通用的 - 你可以在足够大的一组NAND门中构建任何操作。这似乎是学术性的,但如果你看看硬件中如何实现加法器,那通常基本上就是它们归结为的东西。
至于“重点”: 在很多高级应用中,当然没有多少用处,但在系统的最底层,它们非常重要。随口说来,如果没有位运算,很难编写设备驱动程序、密码软件、RAID5或纠错码等错误校正系统、CRC之类的校验和、视频解码软件、内存分配器或压缩软件等内容。
它们还有助于有效地维护大量整数集合,例如由常见的“select"系统调用使用的fd_set,或在解决某些搜索/优化问题时使用。
查看MPEG4解码器、密码库或操作系统内核的源代码,你会看到很多很多的位操作示例。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接