网站 ftp,qq中心官方网站,南庄营销网站建设,歌曲网站模板位运算
Part 1#xff1a;基础 左移#xff1a;左移一位#xff0c;相当于某数乘以 2 2 2。左移 x x x位,相当于该数乘以 2 x 2^x 2x。 右移#xff1a;右移一位#xff0c;相当于某数除以 2 2 2。右移 x x x位#xff0c;相当于该数除以 2 x 2^x 2x。 与运算基础 左移左移一位相当于某数乘以 2 2 2。左移 x x x位,相当于该数乘以 2 x 2^x 2x。 右移右移一位相当于某数除以 2 2 2。右移 x x x位相当于该数除以 2 x 2^x 2x。 与运算按位进行“与”运算两数同一位都为 1 1 1 时结果为 1 1 1否则为 0 0 0。 0 0 0 与任何数都为 0 0 0。 或运算按位进行“或”运算两数同一位都为 0 0 0 时结果为 0 0 0否则为 1 1 1。 非运算按位取反。
Part 2异或
简介
异或操作是指两个数或者多个数之间进行的一种相同为 0 0 0、不同为 1 1 1的位运算。
异或操作通常用 ⊕ \oplus ⊕或^表示。
运算律 0 ⊕ n n 0\oplus nn 0⊕nn n ⊕ n 0 n\oplus n0 n⊕n0 结合律 交换律一堆数在一起进行异或操作时可以按任意顺序进行。
应用 交换两个数aa^b,ba^b,aa^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 n1 n1。 对于 Tarjan 求边双连通分量有一段标记是 isb[i]isb[i^1]1标记该边和它的反向边是桥 bridge插入的时候是成对插入的 ( 0 , 1 ) 、 ( 1 , 2 ) 、 ⋯ 、 ( 2 k , 2 k 1 ) (0,1)、(1,2)、\cdots、(2k,2k1) (0,1)、(1,2)、⋯、(2k,2k1)。
Part 3lowbit
定义 lowbit ( n ) \text{lowbit}(n) lowbit(n) 定义为非负整数 n n n在二进制表示下“最低位的 1 1 1及其后面的所有 0 0 0”构成的数值。
举个栗子 n 10 n10 n10 的二进制表示为 ( 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 n1)n\(-n) lowbit(n)n(∼n1)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 n0 n0。
举个栗子 n 9 ( 1001 ) 2 n9(1001)_2 n9(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 log21 和 log 2 8 \log_28 log28就可以知道 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 maxn120;
int h[maxn5];
for(int i1;i20;i) h[1i]i;
while(cinn)
{while(n0) couth[n-n] ,n-n-n;coutendl;
}还有一种方法建立一个长度为 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 i0;i36;i) h[(1lli)%37]i;
while(cinn)
{while(n0) couth[(n-n)%37] ,n-n-n;coutendl;
}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 xi1如果第 i i i 位是 1 1 1 这个值是 1 1 1否则是 0 0 0。 常见用途 01 01 01 字典树、线性基 枚举子集 常用于状压。 for(int S1S;S1;S1(S1-1)S) S2S^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 cnt0;while(n) n(n-1),cnt;return cnt;
}
