回归本源一一位运算及其应用(完整全文) – 2014国家集训队论文

镇海中学 沈洋

2014 年信息学奥林匹克中国国家队候选队员论文

2014 国家集训队论文

摘要

在电子计算机中, 位运算可以说是比四则运算史基本的运算, 但由于它们不是数学的基本运算且不常在生活中应用, 容易被部分选手, 特别是初学信息学的选手忽视. 本文希望通过对位运算及其应用的介绍, 来使这一情况得到一定的改善.

本文大致可分为三个部分. 第一部分 (第 1 节) 对位运算基本概念进行了介绍, 第二部分 (第 2 至 4 节) 对位运算的几个应用进行了介绍, 第三部分 (第 5 节) 展示了一些例题.

几点说明

• 约定二进制最高位为最左边, 最低位为最右边, 最低位记为第 0 位.
• 本文中的所有程序均以 C++语言描述, 所涉及的语言细节, 内建函数等均以 GNU C++(GCC 编译器) 为标准.
• 若无特别说明, 本文中的位运算使用 C++运算符表示.
• 本文中汇编指 x86 汇编.

基本运算

与, 或, 非和异或

对于逻辑运算的 与, 或, 非 和 异或, 想必大家都耳熟能详了.

其中 与 ($\land$),"或"($\lor$),"异或"($\oplus$) 的真值表如下:

非 ($\lnot$) 的真值表如下:

位运算的 与, 或,非 和 异或 可以看作逻辑运算在整数上的扩展. 它们的运算法则如下:

• 与 运算结果的每个二进制位的值等于两个运算数的对应二进制位进行逻辑"与"运算的结果.
• 或 运算结果的每个二进制位的值等于两个运算数的对应二进制位进行逻辑"或"运算的结果.
• 非 运算结果的每个二进制位的值等于运算数的对应二进制位进行逻辑"非"运算的结果.
• 异或 运算结果的每个二进制位的值等于两个运算数的对应二进制位进行逻辑"异或"运算的结果.

这四种位运算对应的汇编指令如下:

由此可以看出, 对于这四种运算, 带符号整数和无符号整数并没有对应不同的汇编指令, 它们的行为是相同的. 也就是说, 对于带符号整数, 符号位也会与其它位按照同样的方式处理.

移位运算

移位运算分为逻辑移位, 算数移位, 循环移位, 带进位循环移位四种. 其中带进位循环移位涉及到 CF 标志位, 因此不在我们的讨论范围内. 为了准确区分各种移位运算, 在这一部分中我们使用汇编指令来表示它们.

当我们说将 x 左移或右移 y 位时, 默认 y 非负且小于 x 的位宽 1. 例如对于 32 位整数, y 只能在 0 到 31 之间取值.

逻辑移位

逻辑左移对应的汇编指令为 shl x y, 它的功能是把 x 的每个二进制位向左移动 y 位, 移动造成的最右边的空位由 0 补足, 最左边的数溢出 2.

逻辑右移与逻辑左移完全相反, 它对应的汇编指令为 shr x y, 它的功能是把 x 的每个二进制位向右移动 y 位, 移动造成的最左边的空位由 0 补足, 最右边的数溢出.

算术移位

算术左移的汇编指令为 sal x y, 它与逻辑左移完全相同.

算术右移的汇编指令为 sar x y, 它与逻辑右移大体相同, 唯一的区别在于移动造成的最左边的空位由符号位 (最高位) 补足而不是由 0 补足.

循环移位

循环左移对应的汇编指令为 rol x y, 它的功能是把 x 的每个二进制位向左移动 y 位, 移动造成的最右边的空位由最左边溢出的位补足.

循环右移与循环左移完全相反, 它对应的汇编指令为 ror x y, 它的功能是 把 x 的每个二进制位向右移动 y 位, 移动造成的最左边的空位由最右边溢出的位 补足.

移位运算的数学意义

在逻辑移位, 算术移位这两个看似复杂的定义背后实际上是有其数学含义的. 逻辑移位被设计用于处理无符号整数, 它的左移和右移分别与无符号整数的 x × 2^y 和 x ÷ 2^y 具有相同的效果: 算术移位被设计用于处理带符号整数, 它的左移和右移分别与带符号整数的 x × 2^y 和 x ÷ 2^y 具有相同的效果 (舍入方式为向下舍入). 这一点根据补码的定义比较容易证明, 在此就不赘述了.

• 若超出这个范围, 汇编指令只考虑 y 的后几位, C 语言将产生未定义行为.
• 实际上, 最后一个溢出的位会被放入标志位 CF 中, 其他标志位也会相应发生变化, 但这不在我们的讨论范围内, 故在本文中略去对这些部分的描述.

C++中的移位运算

在 C++中, 无符号整数的移位使用逻辑移位, 有符号整数的移位使用算术 移位. 这样一来, 无论是无符号整数还是带符号整数, 我们都可以放心的使用 左移和右移来代替乘以二的幕或除以二的幕的操作.

C++中没有专门的对带符号整数进行逻辑右移的运算符, 不过我们可以通过强制类型转换将它转换成无符号整数后再进行运算.

C++中没有提供循环移位操作符, 但我们可以通过其他运算的组合来实现它. 例如对于 32 位无符号整数 x, 表达式 (x << y) | (x >> (32 - y)) 可以实现循环左移的功能, 而 (x >> y) | (x << (32 - y)) 则可以实现循环 右移的功能.

二进制位的修改和查询

借由汇编指令, 内建函数以及基本位运算的组合, 我们可以在二进制位的 层面上对整数进行一些修改和查询. 本节将介绍一些常用操作并给出一些易于 理解和扩展的实现 3. 由于带符号整数的性质较为复杂, 在这里我们只讨论无符号整数的相关操作, 并以常用的 32 位无符号整数为例.

读某些位

读取 x 的第 pos 个二进制位是一个很常用的操作, 它的实现方式是先将 x 右移 pos 位, 使要读取的位移到最低位, 再通过 & 1 将其取出. 代码如下 4:

bool readBit(u32 x, int pos) {
    return (x >> pos) & 1;
}

• 一些"黑技术"如利用 64 位指令处理 32 位操作数, 利用浮点数进行计算等并未涉及. 对此感兴趣的读者可以参考 http://graphics.stanford.edu/~seander/bithacks.html
• 为简化代码, 我们使用 u32 来表示 32 位无符号整数 (unsigned int).

有时候我们会将多个整数"打包"在一个整数中, 一个典型的应用是将四 个字节打包为一个 32 位整型, 那么读取的时候就需要形如"读 x 的第 pos 位开始 的 cnt 位"这样的操作. 它的实现方式与上面别无二致: 首先将 x 右移 pos 位, 再 通过& mask 来取出最后 cnt 位, 其中 mask 的后 cnt 个位为 1, 其余位为 0, 可以 由 $(1 << cnt) - 1$ 得到. 代码如下:

u32 readBits(u32 x, int pos, int cnt) {
    return (x >> pos) & ((1u << cnt) - 1);
}

通过上面两个例子, 不难发现读取某个或某些二进制位的关键实际上是与 运算. 通过将原数和一个遮罩 mask 进行与运算, 可以达到保留指定一些位 (将遮罩 mask 的对应位设为 1), 清零其它位 (遮罩 mask 的对应位设为 0) 的目的.

改某些位

对二进制位的修改实际上是"与","或"和"异或"运算的实际应用.

将某些位置为 1

要实现这个功能, 我们的办法是将原数与一个遮罩进行或运算. 对于要改为 1 的位, 我们将遮罩的对应位设为 1, 否则将对应位设为 0, 这样, 原数与遮罩 进行或运算的结果就是答案. 举例来说, 将 x 的第 pos 位置为 1 的代码如下:

u32 setBit(u32 x, int pos) {
    return x | (1u << pos);
}

将某些位置为 0

这个操作与上一个操作正好相反, 这一次我们要利用的是与运算. 我们构 造一个遮罩, 对于要修改的位, 我们将遮罩的对应位设为 0, 否则将其设为 1 (注意, 这与上一个操作中的遮罩完全相反), 随后将原数与这个遮罩进行与运 算即可得到答案. 将 x 的第 pos 位置为 0 的代码如下:

u32 clearBit(u32 x, int pos) {
    return x & ˜(1u << pos);
}

取反某些位

这一次是异或运算的应用. 同样构造一个遮罩, 如果我们要取反某位, 则 将遮罩的对应位设为 1, 否则将其设为 0, 随后将原数与这个遮罩进行异或运算 即可得到答案. 将 x 的第 pos 位取反的代码如下:

u32 flipBit(u32 x, int pos) {
    return x ^ (1u << pos);
}

求 1 的个数

分治法
求二进制位中 1 的个数与求各个二进制位的和是等价的, 因此我们转而思考 如何求各个二进制位的和. 我们可以使用分治来解决这个问题: 每次将整个数 分成两个部分, 分别求出每个部分的和, 再将它们相加. 利用位运算, 我们可 以并行地完成每一层的工作, 像下面这样:

int bitCount_1(u32 x) {
    x = ((x & 0xAAAAAAAAu) >> 1) + (x & 0x55555555u);
    x = ((x & 0xCCCCCCCCu) >> 2) + (x & 0x33333333u);
    x = ((x & 0xF0F0F0F0u) >> 4) + (x & 0x0F0F0F0Fu);
    x = ((x & 0xFF00FF00u) >> 8) + (x & 0x00FF00FFu);
    x = ((x & 0xFFFF0000u) >> 16) + (x & 0x0000FFFFu);
    return x;
}

它是这样工作的:

• 第一步, 有 32 个项需要相加, 每一项占 1 bit. 我们将其中的奇数项和偶数 项分别取出来 (利用 2.1 小节中提到的方法), 并将奇数项右移 1 位和偶数 项"对齐", 然后将他们相加. 这一步过后我们实际上将 16 对 1 bit 的项分 别相加, 并将结果存放在了原来这两项所在的 2 bit 空间上.
• 第二步, 有 16 个项需要相加, 每一项占 2 bit. 我们将奇偶项分别相加, 形成 8 个 4 bit 的项.
• ......
• 第五步, 有两项需要相加, 每一项占 16 bit. 将这两项相加我们便得到了答案.
  那么, 还能再优化么? 答案是肯定的. 看下面这段代码:

int bitCount_2(u32 x) {
    x-= ((x & 0xAAAAAAAAu) >> 1);
    x = ((x & 0xCCCCCCCCu) >> 2) + (x & 0x33333333u);
    x = ((x >> 4) + x) & 0x0F0F0F0Fu;
    x = ((x >> 8) + x) & 0x00FF00FFu;
    x = ((x >> 16) + x) & 0x0000FFFFu;
    return x;
}

这段代码较上一段的第一个差别是第一步的实现. 我们知道第一步的作用

是将奇数位和偶数位相加, 根据第一个程序它的结果应为:

((x & 0xAAAAAAAAu) >> 1) + (x & 0x55555555u)

而 x 的值等于:

((x & 0xAAAAAAAAu) + (x & 0x55555555u)

将两式作差得到:

(x & 0xAAAAAAAAu) >> 1

因而将 x 减去 (x & 0xAAAAAAAAu) >> 1 便可以得到我们所求的结果.

另一个差别是第二步之后的实现, 我们以第二步为例来说明. 第二步的作 用是将 4 对 4 bit 整数相加, 但实际上此时每个整数最大只可能是 4, 这就表示, 即使是两个数相加的结果也能在 4 bit 的空间存下. 因此 (x >> 4) + x 可以正确地依次求出第 0 个数加第 1 个数, 第 1 个数加第 2 个数, 第 2 个数加第 3 个数……

我们从中取出我们需要的结果即可.

还能继续优化么? 答案依然是肯定的:

int bitCount_3(u32 x) {
    x-= ((x & 0xAAAAAAAAu) >> 1);
    x = ((x & 0xCCCCCCCCu) >> 2) + (x & 0x33333333u);
    x = ((x >> 4) + x) & 0x0F0F0F0Fu;
    x = (x * 0x01010101u) >> 24;
    return x;
}

这段代码与上一段的不同点在于, 上一段代码的最后两步操作被语句:

x = (x * 0x01010101u) >> 24

代替了. 我们知道上一段代码中第四, 第五步的作用是将 x 中的 4 个 8 bit 数相加,

那么, 如果我们令:

x = (a<<24)+(b<<16)+(c<<8)+(d<<0)

则我们所求的答案便是:

a + b + c + d

我们来看看计算 x * 0x01010101u 时发生了什么:

x*0x01010101
=(x<<24)+(x<<16)+(x<<8)+(x<<0)
=(a<<48)+(b<<40)+(c<<32)+(d<<24)+
         (a<<40)+(b<<32)+(c<<24)+(d<<16)+
                 (a<<32)+(b<<24)+(c<<16)+(d<< 8)+
                         (a<<24)+(b<<16)+(c<< 8)+(d<< 0)
=((a)   <<   48) +
((a+b)  <<   40) +
((a+b+c) <<  32) +
((a+b+c+d)<< 24) +
((b+c+d) <<  16) +
((c+d)   <<  8 ) +
((d)      << 0 )

由于 x 是 32 位整数, 因此上式的前二项应当溢出, 于是 x 0x01010101 的结果为 ((a+b+c+d)<<24) + ((b+c+d)<<16) + ((c+d)<<8) + (d) 考虑 到 a, b, c 的实际意义, 它们的值都不会超过 8, 因此上式的后二项的值必定 小 于 1 << 24, 也就是说它们不会对结果的最高 8 位造成任何影响. 因此, x 0x01010101 的结果的高 8 位便是我们所求的 a+b+c+d, 我们将它右移 24 位即可得到答案.

查表法

如果我们要求 0 到 n 中每一个数的答案的话, 那么可以使用如下递推:

f(0) = 0,
f(i) = f(i >> 1) + (i & 1)

显然对于所有 32 位整数保存答案 (至少在目前看来) 是一件不太现实的事 情, 不过好在这个问题是可以分割的, 我们可以预处理所有 16 位整数的答案, 在询问时将被询问的整数拆成高 16 位和低 16 位分别计算答案. 于是预处理的代 码如下:

int cnt_tbl[65537];
void bitCountPre() {
    cnt_tbl[0] = 0;
    for (int i=1; i<65536; ++i)
        cnt_tbl[i] = cnt_tbl[i >> 1] + (i & 1);
}

回答询问的代码如下:

int bitCount_4(u32 x) {
    return cnt_tbl[x >> 16] + cnt_tbl[x & 65535u];
}

内建函数
GCC 中提供了如下内建函数 5 来实现这个功能:

int __builtin_popcount (unsigned int x);

对于支持 SSE4.2 的机器, 如果在编译时开启相应开关, 则该函数会被翻译成汇编指令 popcnt, 否则该函数使用类似上面"查表法"的方法进行计算.

翻转位序

对于一个 32 位整数来说, 翻转位序是指将它的第 0 位与第 31 位交换, 第 1 位 与第 30 位交换,…… , 第 i 位与第 31 − i 位交换,…… , 第 15 位与第 16 位交换. 例如对于 32 位整数 5, 对它进行翻转位序将得到 2684354560.

分治法

我们可以采用分治法来解决这个问题: 首先将整个数分割成两个部分, 分别翻转这两个部分, 再将这两个部分对调. 同样地, 借由位运算, 我们可以把 每一层的工作并行完成, 实现如下:

u32 bitRev_1(u32 x) {
    x = ((x & 0xAAAAAAAAu) >> 1) | ((x & 0x55555555u) << 1);
    x = ((x & 0xCCCCCCCCu) >> 2) | ((x & 0x33333333u) << 2);
    x = ((x & 0xF0F0F0F0u) >> 4) | ((x & 0x0F0F0F0Fu) << 4);
    x = ((x & 0xFF00FF00u) >> 8) | ((x & 0x00FF00FFu) << 8);
    x = ((x & 0xFFFF0000u) >> 16) | ((x & 0x0000FFFFu) << 16);
    return x;
}

这段代码是这样工作的:

第一步, 交换相邻两位. 这样就形成了 16 个长度为 2 的己经翻转的组.

第二步, 每两位为一组, 交换相邻两组. 这就将 16 个长度为 2 的组变成了 8 个长度为 4 的己翻转的组.

……

第五步, 每 16 位为一组, 交换相邻两组. 整个数翻转完成.
5 关 于 本 文 中 提 到 的 GCC 内 建 函 数 的 具 体 说 明 及 其 他 相 关 内 建 函 数, 请 参 阅 GCC 于 册:

http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

查表法

我们首先预处理出所有 16 位整数翻转后的结果, 这可以由如下递推得到:

f(0) = 0,
f(i) = (f(i >> 1) >> 1) | ((i & 1) << 15)
Text
接下来, 我们将待翻转的 32 位整数拆成两个 16 位整数, 通过查表来得到这 两个 16 位整数的答案, 再将它们对调便可以完成整个 32 位整数的翻转. 预处理 的代码如下:

u32 rev_tbl[65537];
void bitRevPre() {
rev_tbl[0] = 0;
for (int i=1; i<65536; ++i)
rev_tbl[i] = (rev_tbl[i>>1]>>1) | ((i&1)<<15);
}
C++
查询的代码如下:

u32 bitRev_2(u32 x) {
return (rev_tbl[x & 65535] << 16) | rev_tbl[x >> 16];
}
C++

2.5 求前缀/后缀 0 的个数

二分法

求前缀 0 与求后缀 0 是类似的, 我们不妨以求前缀 0 为例. 首先给出代码:

int countLeadingZeros_1(u32 x) {
int ans = 0;
if (x >> 16) x >>= 16; else ans |= 16;
if (x >> 8) x >>= 8; else ans |= 8;
if (x >> 4) x >>= 4; else ans |= 4;
if (x >> 2) x >>= 2; else ans |= 2;
if (x >> 1) x >>= 1; else ans |= 1;
return ans + ! x;;
}
C++
这段代码的实质是二分查找. 它是这样工作的:

第一步, 判断高 16 位是否为空. 若是, 则高 16 位必然均为前缀 0, 我们给 答案加上 16, 并在第 0 至 15 位上继续二分: 若不是, 则前缀 0 只出现在则 高 16 位上, 我们将它们右移到低 16 位上以便对它继续二分.

第二步, 判断此时的高 8 位是否均为前缀 0, 并选择一边继续二分下去.

……

第六步, 判断仅剩的那一位是否为 0, 若是, 则给答案加 1.

求后缀 0 个数的方式与此别无二致, 因此根据上一段代码炮制一段求后缀 0 个数的代码并不是件难事:

int countTrailingZeros_1(u32 x) {
int ans = 0;
if (! (x & 65535u)) x >>= 16, ans |= 16;
if (! (x & 255u )) x >>= 8, ans |= 8;
if (! (x & 15u )) x >>= 4, ans |= 4;
if (! (x & 3u )) x >>= 2, ans |= 2;
if (! (x & 1u )) x >>= 1, ans |= 1;
return ans + ! x;
}
C++
这段代码的工作原理与上一段基本相同, 就不再赘述了.

查表法

我们依然以前缀 0 个数为例. 这个问题与同样是可以分割的. 我们可以先确 定第一个 1 出现在高 16 位中还是低 16 位中, 再通过查表来得到这个 16 位整数的 答案. 这张表可以通过如下递推得到:

f(0) = 16,
f(i) = f(i >> 1) - 1
Text
于是我们就不难写出预处理的代码:

int clz_tbl[65537];
void countLeadingZerosPre() {
clz_tbl[0] = 16;
for (int i=1; i<65536; ++i)
clz_tbl[i] = clz_tbl[i >> 1] - 1;
}
C++
以及查询的代码:

int countLeadingZeros_2(u32 x) {
if (x >> 16)
return clz_tbl[x >> 16]; else
return clz_tbl[x & 65535u] + 16;
}
C++
求后缀 0 个数也可以通过几乎相同的方法实现.

内建函数

对于这两个问题, GCC 也提供相应的内建函数.

求前缀 0 的内建函数为:

int __builtin_clz (unsigned int x);
C++
它对应的汇编指令为 bsr (Bit Scan Reverse) 外加一个异或.

求后缀 0 的内建函数为:

int builtin_ctz (unsigned int x);
C++
它对应的汇编指令为 bsf (Bit Scan Forward).

需要注意的是, 当参数 x 为 0 时, 这两个函数的行为是未定义的.

2.6 求第 k 个 1 的位置

这个问题可以转化为求最大的 w, 使得第 0 位到第 w − 1 中 1 的个数小于 k. 这 显然是可以二分的. 于是, 借助 2.3 小节中的 cnt_tbl, 我们便能实现一个简单的二分:

int kthBit_1(u32 x, int k) {
int ans = 0;
if (cnt_tbl[x & 65535u] < k)
k -= cnt_tbl[x & 65535u], ans |=16, x >>=16;
if (cnt_tbl[x & 255u ] < k)
k -= cnt_tbl[x & 255u ], ans |= 8, x >>= 8;
if (cnt_tbl[x & 15u ] < k)
k -= cnt_tbl[x & 15u ], ans |= 4, x >>= 4;
if (cnt_tbl[x & 3u ] < k)
k -= cnt_tbl[x & 3u ], ans |= 2, x >>= 2;
if (cnt_tbl[x & 1u ] < k)
k -= cnt_tbl[x & 1u ], ans |= 1, x >>= 1;
return ans;
}
C++
不借助 cnt_tbl 自然也是可以的. 我们可以发现, 我们在二分的过程中所需要的区间和都是 2.3 小节中分治法计算过的区间, 因此我们可以将分治的中间 值存下来供二分时使用, 像下面这样:

int kthBit_2(u32 x, int k) {
int s[5], ans = 0, t;
s[0] = x;
s[1] = x - ((x & 0xAAAAAAAAu) >> 1);
s[2] = ((s[1] & 0xCCCCCCCCu) >> 2) + (s[1] & 0x33333333u);
s[3] = ((s[2] >> 4) + s[2]) & 0x0F0F0F0Fu;
s[4] = ((s[3] >> 8) + s[3]) & 0x00FF00FFu;
t = s[4] & 65535u;
if (t < k) k -= t, ans |=16, x >>=16;
t = (s[3] >> ans) & 255u;
if (t < k) k -= t, ans |= 8, x >>= 8;
t = (s[2] >> ans) & 15u;
if (t < k) k -= t, ans |= 4, x >>= 4;
t = (s[1] >> ans) & 3u;
if (t < k) k -= t, ans |= 2, x >>= 2;
t = (s[0] >> ans) & 1u;
if (t < k) k -= t, ans |= 1, x >>= 1;
return ans;
}
C++

2.7 提取末尾连续的 1

我们知道对 x 加 1 之后, 最右边连续的 1 会变为 0, 最右边的 0 则变为 1, 而其

它位不变. 利用这一点我们可以通过下面这个公式来提取 x 末尾连续的 1:

x & (x ^ (x + 1))
C++

2.8 提取 lowbit

正整数 x 的 lowbit 是指 x 在二进制下最右边一个 1 开始至最低位的那部分, 记 为 lowbit(x). 例如 28 (11100B)6 的 lowbit 为 4 (100B), 16 (10000B) 的 lowbit 则为 16 (10000B). lowbit 的典型应用是树状数组和遍历集合.

有如下 3 个公式能帮我们求解 lowbit:

lowbit(x) = x & (x ^ (x - 1))
lowbit(x) = x ^ (x & (x - 1))
lowbit(x) = x & -x
C++
前两个公式利用了"将 x 减去 1 后, x 中最右侧的 1 变为 0, 其之后的 0 变为 1" 这一点, 第 3 个公式则主要利用了补码的特性. 读者可以自行完成这 3 个公式的证明.

2.9 遍历所有 1

一般情况下, 我们可以通过不断求 lowbit 并将它从原数中删去 (通过异或) 来遍历每一个 1. 当需要用到这个 1 所在的位置时, 我们可以通过 2.5 小节中介绍 的求后缀 0 个数的方法来获知.

3 将整数用作集合

集合的种类有很多, 但将它们的元素标号之后, 都能映射到整数集合上.

因此在这里我们只讨论全集为[0, n) 的整数集合.

二进制的每个位有 0 和 1 两种状态, 这正好可以对应集合中某个元素是否存 在, 因此我们可以用二进制数来表示集合一一如果某位为 1 就表示对应元素存在 于这个集合中, 否则不存在. 然而计算机中单个二进制数的位数是有限的, 不 妨设其能处理的单个二进制数的最大位宽为 w, 那么, 表示上述全集为[0, n) 的 整数集合就需要至少 in/wl 个二进制数. 我们把每个二进制数叫做一"块", 并 规定第 i 块记录第 wi 至 w(i + 1) − 1 这个 w 个数是否存在 (0 ≤ i < in/wl, 最后一块 略有不同). 这样, 我们便得到了一个维护集合的数据结构一一 bitset. 我们将某 个 bitset 能表示的全集的大小称为该 bitset 的大小.

6 我们用后缀 B 来表示一个二进制数.

从本质上来说, bitset 实际上是压 w 位的二进制高精度整数, 因此也可以进行与, 或, 非, 异或, 左移, 右移这些位运算, 甚至可以进行加减乘除.

3.1 加入某个元素

首先计算出被加入元素所属的块, 再使用 2.2 小节所述的方法将对应位置为 1.

时间复杂度: O(1)

3.2 删除某个元素

首先计算出被删除元素所属的块, 再使用 2.2 小节所述的方法将对应位置为 0.

时间复杂度: O(1)

3.3 查询某个元素是否存在

首先计算出待查询元素所属的块, 再利用 2.1 小节所述的方法检查对应位是否为 1.

时间复杂度: O(1)

3.4 交集

集合的交和 bitset 的与运算相对应. x 与 y 的交为 x & y.

时间复杂度:O(n/w)

3.5 并集

集合的交和 bitset 的或运算相对应. x 与 y 的并为 x | y.

时间复杂度:O(n/w)

3.6 差集

记 A, B 是两个集合, 则所有属于 A 且不属于 B 的元素构成的集合叫做 A 与 B 的差. 集合的差可以通过 bitset 的与运算和异或运算实现.x 与 y 的差为 x ^ (x & y).

时间复杂度:O(n/w)

3.7 补集

集合的补与 bitset 的非运算相对应. x 的补为∼x.

时间复杂度: O(n/w)

3.8 统计元素个数

对于每个块分别使用 2.3 小节中介绍的方法计算 1 的个数, 再将所有块的答案相加.

时间复杂度:O(n/w)

3.9 遍历集合元素

遍历所有块, 对每个块使用 2.9 小节中介绍的方法遍历元素.

时间复杂度:O(n/w + cnt), 其中 cnt 表示集合的元素个数.

3.10 求集合中第 k 小元素

朴素做法

首先从小到大依次遍历每个块, 找出第 k 小元素所在的块, 再利用 2.6 小节中介绍的方法确定具体是哪个元素.

时间复杂度:O(n/w + log w)

更加高效的做法

在某些应用中, 求第 k 小元素可能比其它集合操作的使用频率更大, 此时我 们就会需要一个复杂度更优的查询第 k 小元素操作, 同时要尽可能小地影响其它 集合操作的复杂度.

一种改进方式是利用线段树. 我们使用一颗辅助线段树来维护 bitset 中每个 块的元素个数. 这样一来, 我们就可以通过在线段树上二分的方式快速确定 第 k 小元素所属的块. 这是一个经典的线段树操作, 在这里就不再赘述. 找出第 k 小元素所在的块之后, 我们就可以利用 2.6 小节中介绍的方法确定具体是哪个元素了. 这样改进之后, 求第 k 小元素的时间复杂度降为了 O(log n).

添加了辅助线段树之后, 其他的集合操作也要做出相应修改. 在加入, 删 除集合元素时, 该元素所属的块的元素个数会发生改变, 我们需要同时维护辅 助线段树的信息, 因此这两个操作的时间复杂度变为了 O(log n). 在集合求交, 并, 差, 补的时候, 我们可以直接暴力重建辅助线段树, 时间复杂度维持不变 为 O(n/w).

3.11 求集合中大于 x 的最小元素

朴素做法
首先判断 x 所在块中是否存在大于 x 的元素, 若是则直接返回这个元素, 否 则从 x 所在的块开始向后遍历, 找到 x 之后第一个包含元素的块, 然后返回该块 的第一个元素. 其中, 某块的第一个元素以及某块中比 x 大的第一个元素均可以 利用 2.5 小节中介绍的统计后缀 0 个数的方法求出.

时间复杂度:O(n/w)

更加高效的做法
类似于求第 k 小元素, 我们也可以利用辅助数据结构来加速大于 x 的最小元素的查询.

这次我们利用的是 bitset 本身. 我们使用一个大小为 n/w 的辅助 bitset7 来保存每个块是否有元素, 这样一来, 我们可以通过如下流程来完成该查询:

若 x 所在块中存在大于 x 的元素, 则直接返回这个元素, 否则转 2.

利用辅助线段树查询 x 所在块之后第一个含有元素的块, 转 3.

在该块中找第一个元素并返回结果.

改进之后, 该查询的时间复杂度降为了 O(logw n).

同样地, 其他的集合操作也要做出相应修改. 在加入, 删除集合元素时, 我们需要同时维护辅助 bitset 中该元素所在块的信息, 因此这两个操作的时间复杂度变为了 O(logw n). 在集合求交, 并, 差, 补的时候, 我们可以直接暴力重建辅助 bitset, 时间复杂度维持不变为 O(n/w).

7 这里的 bitset 是递归定义的, 因此这个辅助 bitset 也支持快速求集合中大于 x 的最小元素.

3.12 将集合的全部或部分元素加上/减去 x

将集合的全部元素加上/减去 x
对集合 a 的每个元素都加上 x 只需要将 a 左移 x 位即可. 同样的, 对集合 a 的每个元素都减去 x 只需要将 a 右移 x 位即可.

时间复杂度:O(n/w)

将集合的部分元素加上/减去 x
设原集合为 a, 要求改动的那部分元素组成的集合为 b. 在这次修改中, a 与 b 的差这部分元素是不会改变的, 记为集合 p:a 与 b 的交这部分元素是需要 加上/减去 x 的, 记为集合 q. 之后我们利用移位操作对集合 q 作相应修改, 再与 集合 p 求并即可.

时间复杂度:O(n/w)

3.13 枚举子集

枚举子集的关键在于, 对于某个集合的某个子集, 我们需要求出字典序排 在它前一位的集合或后一位的集合. 对于集合 x 和它的一个子集 y, 我们可以通 过 (y - 1) & x 来求出字典序排在它前一位的子集. 因此, 若要枚举 x 的子集, 我们只需从 x 本身开始, 不断求前一个子集, 直到枚举到空集为止即可.

3.14 枚举含有 k 个元素的集合

与枚举子集类似, 枚举含有 k 个元素的集合的关键同样是对于某个含有 k 个 元素的集合求出字典序排在它前一位或后一位的集合. 这一次我们选择的是构 造字典序后一位的集合.

朴素的做法如下: 设当前集合中的数从小到大依次为 a0, a2, . . . , ak−1, 其中 最小的可以增大的数为 a j, 那么我们把 a j 加上 1, 并将 a0 到 a j−1 重置为 0 到 j − 1 即 可得到下一个包含 k 个元素的集合.

这个做法反映到 bitset 上是这样的: 设最右边连续的 1 是第 i 位到第 j 位, 那么 我们要做的就是将第 j 位上的 1 向左移一位, 同时将第 i 位到第 j − 1 位上的 1 向右移 到最右边. 这可以由下面这段代码完成:

u32 nextComb(u32 x) {
u32 l = x & -x, y = x + l;
return y | (((x ^ y) / l) >> 2);
}
C++
它是这样工作的:

第一步, 使用 l = x & -x 求出 x 的 lowbit.

第二步, y = x + l 将第 j 位上的 1 向左移动一位, 同时将第 i 位到第 j−1 位置为 0(i 和 j 的含义见上文).

第三步,((x ^ y) / l) >> 2 将第 i 位到第 j − 1 位上的 1 提取出来并移到最右边.

第四步, 将这些 1 与 y 合并得到答案.

4 其他应用

除上两节所介绍的应用外, 我们还可以利用位运算做一些其他事情.

4.1 判断奇偶性

根据奇偶性的定义, 二进制最低位为 0 的数为偶数, 最低位为 1 的数为奇数, 因此我们可以直接使用 x & 1 来判断 x 的奇偶性. 若 x & 1 等于 1 则表明 x 为奇 数, 否则 x 为偶数.

4.2 乘以或除以二的幕

根据移位运算的实际意义, 我们可以直接利用左移和右移实现, 参见 1.2 小节中的相关介绍.

4.3 对二的幕取模

x mod 2^y 相当于取出 x 的后 y 位, 因此可以用 x & ((1 << y) - 1) 来实现相同的效果.

4.4 求 log2 x 的整数部分

设 x 的位宽为 w, 使 用 2.5 小节中介绍的方法计算出的前缀 0 个数为 l, 那么 ⌊log2 x⌋ = w − 1 − l.

4.5 交换两个数

这是异或的经典应用. 我们可以通过如下代码来交换 a, b:

a ^= b, b ^= a, a ^= b
C++
4.6 比较两个数是否相等
我们可以计算两个数的异或值, 若等于零则说明这两个数相等, 否则说明这两个数不相等.

4.7 取绝对值

对于一个 w 位带符号整数 x, 它的符号位 sign = x >> (w - 1), 我们可 以通过表达式 (x ^ -sign) + sign 来得到 x 的绝对值. 这一点根据补码的定 义比较容易证明, 在此就不赘述了.

4.8 选择

我们可以利用表达式 y ^ ((x ^ y) & -cond) 来实现选择的功能:

若 cond = 1, 其结果为 x

若 cond = 0, 其结果为 y

5 例题

5.1 筷子

试题来源
经典问题

试题大意
有 2n + 1 个整数, 其中某个数出现了奇数次, 其他数出现了偶数次. 求出现了奇数次的那个数.

算法介绍
由于异或运算满足交换律, 并且满足 x ⊕ x = 0, 因此将所有数异或起来即为答案.

5.2 Robot in Basement

试题来源
Codeforces 97D8

Yandex.Algorithm 2011 Finals

试题大意
在一个 n × m (n, m ≤ 150) 的网格上, 有一些格子是障碍, 并且网格边界上的格子均是障碍, 另有一个非障碍的格子是出口. 有一个机器人可以根据程序在 该网格上行走. 一段程序是一个由 UDLR 四种指令组成的字符串, 机器人会依 次执行每个指令, 一个指令会使机器人向指定的方向移动一格, 如果对应格子 为障碍则不动.

现在给定一个长度为 l (l ≤ 10^5) 的程序, 求它的一个最短前缀 p, 使得对于一开始在网格图上任意非障碍位置的机器人, 在执行完程序 p 之后都停在出口上.

8http://codeforces.com/problemset/problem/97/D

算法介绍
首先不难想到一个 O(nml) 的朴素算法. 我们直接顺序执行给定的程序, 并 按照题目指定的移动方式暴力维护网格上哪些格子有机器人, 直到执行完某一 步后发现网格上只有出口位置有机器人时结束.

实际上我们可以利用 bitset 来维护网格上哪些格子有机器人. 一种表示方式 是利用 bitset 的第 i · m + j 个位置表示格子 (i, j) (0 ≤ i < n, 0 ≤ j < m) 上是否有机器 人. 这样一来一个向左或向右移动的指令就对应了该 bitset 的左移或右移 1 位, 一 个向上或向下的指令就对应了该 bitset 的左移或右移 m 位. 障碍的问题可以这样 解决: 预处理 cL, cR, cU, cD 四个 bitset, 分别表示向左, 向右, 向上及向下走一 步会碰到障碍的位置. 以向左走为例, 设原 bitset 为 x, 那么执行一个指令 L 之后 会撞到障碍的位置为 x & cL, 能正常向左走的位置为 x ^ (x & cL), 我们 知道能正常向左走的那些机器人应该被左移一位, 而那些会撞到障碍的机器人 则应留在原地, 因此最终的 bitset 应变为 (x & cL) | (x ^ (x & cL)). 改进后的算法的时间复杂度为 O( nml / w), 可以通过本题.

5.3 Quick Tortoise

试题来源
Codeforces 232E9

试题大意
在一个 n × m (n, m ≤ 500) 的网格上, 有一些格子是障碍. 共有 q (q ≤ 6·10^5) 个询问, 每次询问是否能只通过向下走和向右走从格子 (x1, y1) 走到格子 (x2, y2).

算法介绍
首先考虑所有询问满足 x1≤p≤x2 的情况. 对于所有在第 p 行上方的格子 (x, y), 求它能走到第 p 行的哪些格子, 己这个点集为fx, y, 它可以通过递推式 fx, y=fx+1, y∪fx, y+1 求出. 类似地, 对于所有在第 p 行下方的格子 (x, y), 求第 p 行的哪些格子能走到它, 己这个点集为 gx, y, 它可以通过 gx, y=gx−1, y∪gx, y−1 求出. 求出 fx, y 和 gx, y 之后, 我们就可以来处理询问了. 对于询问 (x1, y1),(x2, y2),

若 fx1, y1∩gx2, y2≠∅, 则表示可以从 (x1, y1) 走到 (x2, y2), 反之则不能.

9http://codeforces.com/problemset/problem/232/E

对于一般情况, 我们可以使用分治转化成上面的情况进行求解. 例如我们正在处理所有满足 l ≤ x1 ≤ x2 ≤ r 的询问, 令 mid = ⌊(l+r)/2⌋, 我们可以先按照上一段所述的方法处理所有满足 l ≤ x{1} ≤ mid ≤ x{2} ≤ r 的询问, 再递归地处理剩下的满足 l ≤ x1 ≤ x2 < mid 的询问和满足 mid < x1 ≤ x2 ≤ r 的询问. 如果我们只对 x 轴进 行分治, 那么这个算法时间复杂度为 O( n·m^2 log n + q log n). 如果我们交替对 x 轴 和 y 轴进行分治, 它的时间复杂度可以进一步降为 O((nm*)^1.5 + q log nm).

5.4 Bags and Coins

试题来源
Codeforces 356D10

试题大意
有 n (n ≤ 70000) 个包, 每个包可以直接放在地上, 也可以放在其他包里面, 并且允许多层嵌套. 有 s (s ≤ 70000) 个硬币分布在这 n 个包里. 如果拿出某个硬 币必须要打开第 i 个包, 我们就称该硬币在第 i 个包里. 现在己知每个包里的硬币 数, 第 i 个包里有ai (ai ≤ 70000) 个硬币. 求一种满足条件的包的嵌套方式以及硬 币分布方式, 或确定问题无解.

算法介绍
不妨设 a1 ≥ a2 ≥ . . . ≥ an.

我们首先考虑 s = a1 的情况. 在这种情况下, 我们只需要将第 1 个包放在地上, 并在第 i (1 ≤ i < n) 个包中放入 ai − ai+1 个硬币以及第 i + 1 个包, 最后在第 n 个包中放入an 个硬币即可.

于是对于一般情况, 即 s ≥ a1 的情况, 问题就转化成了边一些包放在地 上 (第 1 个包是必边的), 让它们的硬币个数之和等于 s. 这是一个经典的背包问 题. 我们可以用一个 bitset 来表示当前背包 (通过当前添加的物品能够达到哪些总体积), 设当前 bitset 为 S, 那么添加一个体积为 x 的物品后的 bitset 就会变 为 S | (S << x). 当添加完所有物品之后, 我们检查最终的 bitset 中是否包 含 s 这个元素就能确定是否有解.

10http://codeforces.com/problemset/problem/356/D

如何记录方案呢? 我们引入一个 from 数组, 其中 from[i]表示在某种体积 达 到 i 的 方 案 中 最 后 加 入 的 物 品. 这 样 一 来, 如 果 问 题 有 解, 我 们 就 可 以 通 过 from 数组不断追溯到上一个加进来的物品, 也就可以恢复方案了. from 数组 的维护也很容易, 在添加第 i 个物品的时候, 设添加之前的 bitset 为 S, 之后为 Sn, 己 Sn 与 S 的差为 D, 我们枚举 D 的每个元素 j, 并将 from[ j] 设为 i 即可. 由于 D 的 实际意义是加入第 i 个物品时新产生的可行体积的集合, 因此 from 数组的每个元素至多被设置一次, 也就保证了复杂度.

该算法的时间复杂度为 O(n*s/w).

参考文献

• [1] Sean Eron Anderson, "Bit Twiddling Hacks".
• [2] Christer Ericson, "Advanced bit manipulation-fu".
• [3] 刘汝佳, 黄亮, <算法艺术与信息学竞赛), 清华大学出版社.