Skip to main content
  1. Posts/

位运算用法整理

·

实训准备的第二弹。

简介 #

整理了一些和位运算相关的内容,主要分为以下几个部分:

  1. 集合的整数表示
  2. 位运算的常见技巧和常用公式
  3. gcc 中 __builtin 系列函数及 C++ 中 bitset 类的简介

集合的整数表示 #

以下内容摘自挑战程序设计竞赛

在程序中表示集合的方法有很多种,当元素数比较少时,像这样用二进制码来表示比较方便。集合 ${0,1,…,n-1}$ 的子集 S 可以用如下方式编码成整数。

$$ f(S)=\sum\limits_{i\in{S}}2^i $$

像这样表示之后,一些集合运算可以对应地写成如下方式。

  • 空集:0
  • 只含有第 i 个元素的集合:1<<i
  • 含有全部 n 个元素的集合:(1<<n)-1
  • 判断第 i 个元素是否属于集合 S:if (S>>i & 1)
  • 向集合中加入第 i 个元素:S | 1<<i
  • 从集合中去除第 i 个元素:S & ~(1<<i)
  • 求 S 和 T 的交集、并集:S|T, S&T

此外, 想要将集合 ${0,1,…,n-1}$ 的所有子集枚举出来的话,可以像下面这样书写:

for (int S = 0; S < (1<<n); ++S)
{
    // 对子集的处理
}

按这个顺序循环的话,S 便会从空集开始,然后按照 {0},{1},{0,1},…{0,1,…,n-1} 的升序顺序枚举出来。

更高级的内容参见挑战程序设计竞赛其实是懒

位运算的常见技巧和常用公式 #

如有遗漏请务必补充。

  • (来自: 树状数组 lowbit)取出 “从 x 的最低位的 1 直到最后” 的值:x &= -x
  • (来自: 线段树)快速求 $2x,2x+1$:x<<1, x<<1|1
  • (来自: 我也不知道来自哪里)把 x 最低位的 1 变成 0:x &= (x-1)
  • (来自: 我也不知道来自哪里)把 x 最低位的 0 变成 1:x |= x+1
  • (来自: 状压 dp)判断 x 的第 i 位是不是 1:if (x & (1<<i))
  • (来自: 博弈论)异或(XOR)运算的性质:同一个数异或两次即为其自身
  • (来自:CSAPP)C/C++ 中对于有符号数,>> 表示算术右移;对于无符号数,>> 表示逻辑右移。对于两者而言,<< 都表示逻辑左移。
  • (来自: 为了偷懒不写 EOF)表示 x 不等于 -1:~x。也就是说,while(scanf("%d", &n) != EOF) 等价于 while(~scanf("%d", &n))

由于其中原理都不难推导,这里不再赘述。

gcc 中 __builtin 系列函数及 C++ 中 bitset 类的简介 #

这里只记录一些实训可能会用到的……

__builtin #

以下函数都返回 int,x 都为 unsigned int(当然在函数名后加 lll 可以改为 long/long long 类型)。

  • __builtin_popcount(x):x 中 1 的个数
  • __builtin_ctz(x):x 末尾 0 的个数(x 非 0)
  • __builtin_clz(x):x 前导 0 的个数(x 非 0)
  • __builtin_ffs(x):x 中最后一个为 1 的位是从后向前的第几位
  • __builtin_parity(x):x 中 1 的个数模 2 的值

bitset #

本来想自己写一下,后来发现 这个博客这个博客 总结得很好,就偷了个懒。

一般来说实训当中不太会有需要用到 __builtin 和 bitset 的题目,所以了解一下就可以了。