位运算技巧
不定期更新
基本运算符 \(:\) 与( & ) , 或( | ) , 异或( ^ ) , 取反( ~ ) , 左移( << ) , 右移( >> )
\(① :\) 优先级
~ > 加减 > 左移右移 > & > ^ > |
\(② :\) 基本规则
& \(:\) 同为 \(1\) , 才为 \(1\) , 其他为 \(0\) .
| \(:\) 同为 \(0\) , 才为 \(0\) , 其他为 \(1\) .
^ \(:\) 二者相同为 \(0\) , 不同为 \(1\) .
~ \(:\) 取反码 .
若为负数 , 先取反码再进行操作.
x<x>>n , \(x\) 在非负数范围内相当于 \(x\times 2^n\) 和 \(x\div 2^n\).
而对于 \(x\) 为负数而言 , x<
而x>>n 则不是向 \(0\) 取整 , 而是向下取整 . 举例 : \(-3\div 2^1 = -2\) , \(-1\div 2^1 = -1\).
\(③ :\) 技巧
判断一个数是不是 \(2\) 的 正整数次幂.
return ( x>0 && x&(x-1) );
获取 \(a\) 的第 \(b\) 位 , 最低的编号为 \(0\).
return (a>>b)&1 ;
若二进制中 \(1\) 表示在集合里面 , \(0\) 表示不在集合里面.
\(a\) , \(b\) 的交集 \(:\) a&b.
\(a\) , \(b\) 的并集 \(:\) a|b.
\(a\) 的补集 : ~a.
\(a\) , \(b\) 的差集 \(:\) a&(~b).
\(n\) 的第 \(k\) 位取反 \(:\) n xor (1<
\(n\) 的第 \(k\) 位赋 \(1 :\) n|(1<
\(n\) 的第 \(k\) 位赋 \(0 :\) n & (~(1<
遍历 \(x\) 的非空子集
for(int s = x; s ; s = (s-1)&u)
// s是非空子集.