Binary Operation

算得上一些基本的编程技巧了, 但过去我这块本身就学得不牢靠, 这里总结一下重新学习

基础

• 与(AND) a & b: 对应位都为 1 时, 结果为 1
• 或(OR) a | b: 对应位存在 1 时, 结果为 1
• 异或(XOR) a ^ b: 对应位不同时, 结果为 1
• 取反 ~a: 二进制数补码对应位取反

额外的, 似乎肌肉里存在着一句俗语”取反加一”, 这实际说的是一个负数的二进制补码的计算方式. 对于非负数而言, 其补码等于自身, 对于负数而言, 其补码为对应正数取反后加一.

• 左移 a << i: 二进制数向右移动 i 位, 表现为末尾增添 i 个 0
• 右移 a >> i: 二进制数向左移动 i 位, 表现为首部增添 i 个 0, 截断原始的后 i 位

对于左移这种可能使得一个有符号数溢出的操作符而言, 溢出后的情况可以视作未定义. 虽然事实上根据不同的编译器/编译选项/平台, 有着不同的规则. 而对于无符号数而言, 溢出后的表现十分稳定, 就是对 $2^n$ 取模.

应用

OIWIKI 上有详细且完整的应用内容, 但我们这里只针对其中部分进行阐述, 有些部分太偏向奇技淫巧(茴香豆的茴字有四种写法)其实可以不学(请相信现代编译器), 但可以学一下装个逼, 搞个什么防御式编程

位操作

等价于将一个整数视为 32/64 位长的布尔数组(准确来说 bitset), 索引从 0 开始(最低位索引为 0)

• 获取第 n 位: (a >> n) & 1
• 第 n 位置零: (a & ~(1 << n))
• 第 n 位置一: (a | ~(1 << n))
• 第 n 位取反: (a ^ (1 << n))

内建位运算

gcc doc 此处有 gcc 的全部内建函数, 通常不会直接使用到下面的函数, 一般而言做为一些状态转移的一些判断条件.

• 二进制末尾 1 的位置: __builtin_ffs(a), 若 a 为 0 返回 0, 索引从 1 开始(i.e. 最低位索引为 1)
• 二进制前置连续 0 的个数: __builtin_clz(a), 若 a 为 0, 结果未定义
• 二进制末尾连续 0 的个数: __builtin_ctz(a), 若 a 为 0, 结果未定义
• 二进制符号位之外的, 与符号位相同的前置连续位数量: __builtin_clrsb(a), 为 0 返回前置连续 0 个数减一, 为 1 返回前置连续 1 个数减一
• 二进制 1 的个数: __builtin_popcount(a)

集合操作

前置知识

x 对 $2^n$ 取模等价于 x & (pow(2, n) - 1). 实际上就是只保留 x 的末尾几位, 取模计算将前置位都置零了.

子集遍历

将一个数视为一个集合, 二进制位上的 0/1 表示该位置代表的元素是否在该集合内. 因此集合的操作就被转换为了对二进制位的操作. 这通常要求集合中的元素在比较小的范围, 至少要小于等于二进制位数.

遍历一个集合的全部子集可以通过下面的代码完成, 其中 sub - 1 可以视为集合遍历的最小递进, 对 mask 做二进制与则是快速递进至子集(可以理解为将 mask 中多余的 1 去除). 遍历的次数等于子集的数量, 即 pow(2, __builtin_popcount(mask))

for (int sub = mask; sub; sub = (sub - 1) & mask) {
  // iterating every subset of mask by descending order
  // 当 sub = 0 时, (sub - 1) & mask == mask, 因此我们需要 sub > 0 做为循环终止条件
}
// 遍历所有集合的子集合, n 代表集合长度
for (int mask = 0; mask < (1 << n); ++mask) {
  for (int sub = mask; sub; sub = (sub - 1) & mask) {
    // 对于一个长度为 n 的二进制数, 任意一位的状态只有三种情况
    // 1. 在 mask 不在 sub; 2. 在 mask 在 sub; 3. 不在 mask 不在 sub
    // 考虑到任何一个状态只会遍历一次, 因此总的遍历次数为 3^n
  }
}