位域算术基础教程

本文描述使用布尔操作操作位域的基本操作。虽然本文以 Java 为重点，但大多数编程语言使用相同的语法。

什么是位域？

所有现代计算机使用二进制算术 - 这意味着，最基本的信息单位是位 - 其值可以是 0 或 1。在几乎所有二进制算术的硬件实现中，你不能直接寻址和修改位，但必须使用字节（= 8 位）。位域是位的向量，其中每个位表示一条特定的信息，可以为真或假。根据应用，位域可以占用更多或更少的空间。

位域的可能应用包括但不限于布隆过滤器和游戏人工智能。在后者中，如果它们表示游戏棋盘上的特定状态，则称为位棋盘。

你也可以使用字（2 字节 = 大多数配置中的 short）、双字（4 字节 = 大多数配置中的 int）或四字（8 字节 = 大多数配置中的 long）而不是单字节进行寻址。在 64 位平台上，双字或四字通常最有效，但超过四字（即 64 位）的任何东西在 CPU 中需要多条指令，这通常使计算效率低下（有一些涉及 SIMD 的技巧，但这超出了本文的范围）。

在位域中设置一个或多个位

在位域中设置单个位非常简单，因为它只涉及布尔 OR 操作。要设置的位需要首先表示为掩码 - 如果 $n$ 是要设置的位的编号，适当的掩码是 $2^n$。然后，你可以使用以下涉及按位（！）OR 的表达式来设置位

bitfield |= mask;

如果你想设置多个位，只需像这样 OR 所有掩码：

bitfield |= mask1 | mask2 | mask3;

注意此代码设置位，无论它们之前是否已设置。

使用任何编程语言时，始终验证你使用的是按位布尔运算符。C/C++ 通常不会在使用 || 或 && 等运算符时打印警告消息，但这些不是按位工作，而是将左侧和右侧参数仅当为零（即没有设置位）时视为假。

在位域中取消设置位

取消设置位几乎和检查它们一样简单：你将位域与取反（NOT）的掩码进行 AND。由于 AND 和 NOT 操作的工作方式，原始掩码中未设置的位在取反掩码中已设置，因此保持与之前相同。取反掩码对于要取消设置的位为零，因此 AND 操作的结果对于这些位始终为零。

代码示例：

bitfield &= ~mask;

就像上面一样，你可以按位 OR 掩码一次执行多个取消设置 - 但记住在它们周围加括号。

bitfield &= ~(mask1 | mask2 | mask3);

在位域中检查位

检查位域中的位就像将位域与相应掩码进行 AND 一样简单。如果结果数字为零，则检查的位未设置，如果不为零则检查的位已设置。

byte result = bitfield & mask;

如果你想一次使用多个掩码，记住当且仅当没有与掩码对应的位被设置时结果为零。如果至少设置了一个位，你无法（没有进一步操作）看到设置了多少和哪些位。

byte result = bitfield & (mask1 | mask2 | mask3);

位域的效率和可能的替代方案

显然，位域使用大约每个属性一个字节的 1/8 空间（大多数编程语言在使用 布尔 数组或类似时每个属性使用一个字节）。如果你的应用需要确定性存储，位域是占用空间最少的未压缩存储类型。因为它是未压缩的，不需要进行耗时的压缩和解压缩操作。

虽然位域每次读/写访问至少需要一个布尔操作，但这些操作在所有类型的处理器上都非常快（约 1 个时钟周期）。此外，使用位域产生更好的内存局部性（因为大小减小），比每个属性 1 字节的存储产生更少的页面错误。总体而言，这些效果在真实硬件上几乎任何情况下都产生更好的时间性能，尽管理论上它们比每个属性 1 位的存储稍慢。

如果你可以接受给定的假阳性概率，你应该考虑布隆过滤器作为替代方案。写入它们需要更多时间，但它们需要显著更少的空间同时保持零假阴性概率。