位运算相关笔记

笔记"/>

位运算相关笔记

位运算

Part 1：基础

1. 左移：左移一位，相当于某数乘以 2 2 2。左移 x x x位,相当于该数乘以 2 x 2^x 2x。

2. 右移：右移一位，相当于某数除以 2 2 2。右移 x x x位，相当于该数除以 2 x 2^x 2x。

3. 与运算：按位进行“与”运算，两数同一位都为 1 1 1 时结果为 1 1 1，否则为 0 0 0。 0 0 0 与任何数都为 0 0 0。

4. 或运算：按位进行“或”运算，两数同一位都为 0 0 0 时结果为 0 0 0，否则为 1 1 1。

5. 非运算：按位取反。

Part 2：异或

简介

异或操作，是指两个数或者多个数之间进行的一种相同为 0 0 0、不同为 1 1 1的位运算。

异或操作通常用 ⊕ \oplus ⊕或^表示。

运算律

• 0 ⊕ n = n 0\oplus n=n 0⊕n=n， n ⊕ n = 0 n\oplus n=0 n⊕n=0

• 结合律

• 交换律：一堆数在一起进行异或操作时，可以按任意顺序进行。

应用

• 交换两个数：a=a^b,b=a^b,a=a^b;

• 找到某个数

  一个数组中只有一个数出现了奇数次，其余数都出现了偶数次，如何找到这个出现奇数次的数？

  根据异或运算的性质，一个数与自己异或等于零，一个数与 0 0 0异或等于本身可知，只需将数组中的所有数进行异或操作即可将出现偶数次的数消掉，得到出现奇数次的。

• i ⊕ 1 i\oplus 1 i⊕1 表示 i i i 的反向边。

  证明：对于一个数 n n n，如果它是奇数，那么它异或 1 1 1 等于 n − 1 n-1 n−1；如果它是偶数，那么它异或 1 1 1 等于 n + 1 n+1 n+1。

  对于 Tarjan 求边双连通分量，有一段标记是 isb[i]=isb[i^1]=1（标记该边和它的反向边是桥 bridge），插入的时候是成对插入的（ ( 0 , 1 ) 、 ( 1 , 2 ) 、 ⋯ 、 ( 2 k , 2 k + 1 ) (0,1)、(1,2)、\cdots、(2k,2k+1) (0,1)、(1,2)、⋯、(2k,2k+1)）。

Part 3：lowbit

定义

lowbit ( n ) \text{lowbit}(n) lowbit(n) 定义为非负整数 n n n在二进制表示下“最低位的 1 1 1及其后面的所有 0 0 0”构成的数值。

举个栗子， n = 10 n=10 n=10 的二进制表示为 ( 1010 ) 2 (1010)_2 (1010)2​，则 lowbit ( n ) = 2 = ( 10 ) 2 \text{lowbit}(n)=2=(10)_2 lowbit(n)=2=(10)2​。

公式

lowbit ( n ) = n & ( ∼ n + 1 ) = n & ( − n ) \text{lowbit}(n)=n\&(\sim n+1)=n\&(-n) lowbit(n)=n&(∼n+1)=n&(−n)

应用

lowbit \text{lowbit} lowbit运算配合Hash，可以找出整数二进制表示下所有是 1 1 1的位，时间复杂度与 1 1 1的个数同级。

实现：不断把 n n n 赋值为 n − lowbit ( n ) n-\text{lowbit}(n) n−lowbit(n)，直至 n = 0 n=0 n=0。

举个栗子： n = 9 = ( 1001 ) 2 n=9=(1001)_2 n=9=(1001)2​， lowbit ( 9 ) = 1 \text{lowbit}(9)=1 lowbit(9)=1。把 n n n 赋值为 9 − lowbit ( n ) = 8 = ( 1000 ) 2 9-\text{lowbit}(n)=8=(1000)_2 9−lowbit(n)=8=(1000)2​。 8 − lowbit ( 8 ) = 0 8-\text{lowbit}(8)=0 8−lowbit(8)=0，停止循环。在这个过程中减掉了 1 1 1 和 8 8 8，即 n n n 每一位上的 1 1 1 后补 0 0 0 后的数值。取 log ⁡ 2 1 \log_21 log2​1 和 log ⁡ 2 8 \log_28 log2​8，就可以知道 n n n 的第 1 1 1 位和第 3 3 3 位是 1 1 1。

C++中的 log2 函数效率不够高，所以我们要预处理一个数组，用 Hash 代替 log ⁡ \log log 运算。

当 n n n较小时，可以建立一个数组 h，令 h [ 2 k ] = k h[2^k]=k h[2k]=k。

const int maxn=1<<20;
int h[maxn+5];
for(int i=1;i<=20;i++) h[1<<i]=i;
while(cin>>n)
{while(n>0) cout<<h[n&-n]<<' ',n-=n&-n;cout<<endl;
}

还有一种方法，建立一个长度为 37 37 37 的数组 h，令 h [ 2 k m o d 37 ] = k h[2^k\bmod 37]=k h[2kmod37]=k（ ∀ k ∈ [ 0 , 35 ] \forall k\in[0,35] ∀k∈[0,35]， 2 k m o d 37 2^k\bmod 37 2kmod37 互不相等，可以取遍 1 ∼ 36 1\sim36 1∼36）。

int h[37];
for(int i=0;i<36;i++) h[(1ll<<i)%37]=i;
while(cin>>n)
{while(n>0) cout<<h[(n&-n)%37]<<' ',n-=n&-n;cout<<endl;
}

lowbit 运算还可用于树状数组。

更多函数

• int __builtin_ctz(unsigned int x)

  int __builtin_ctzll(unsigned long long x)

  返回 x x x 的二进制表示下最低位的 1 1 1 后边有多少个 0 0 0。

• int __builtin_popcount(unsigned int x)

  int __builtin_popcountll(unsigned long long x)

  返回 x x x 的二进制表示下有多少位为 1 1 1。

常见操作

• 查询一个数二进制下的第 i i i 为是不是 1 1 1：

  x>>i&1，如果第 i i i 位是 1 1 1 这个值是 1 1 1，否则是 0 0 0。

  常见用途： 01 01 01 字典树、线性基

• 枚举子集

  常用于状压。

  for(int S1=S;S1;S1=(S1-1)&S) S2=S^S1;
  

  其中 S S S 是全集， S 1 S_1 S1​ 是子集， S 2 S_2 S2​ 是 S 1 S_1 S1​ 的补集。

• 改变 x x x 的第 i i i 位

  x|=1<<(i-1);//将x第i位变成1
  x&=~(1<<(i-1));//将x第i位变成0
  

• 查询 1 1 1 的个数

  int popcount(int n)
  {int cnt=0;while(n) n&=(n-1),cnt++;return cnt;
  }