位运算笔记 | Catalyst

📔

基础

名字	用法	说明	Rust 用法
位与	`A&B`	每一位进行比较，都为 1 的情况下该位为 1
位或	`A \\| B`	每一位进行比较，只要一个为 1 则该位为 1
异或	`A^B`	每一位进行比较，不同则该位为 1，否则为 0
取反	`~A`	0 和 1 全部取反	`!A`
左移	`A<<B`	二进制后左移 B 位，即在后面添加 B 个 0，相当于 `A*(2^B)`
右移	`A>>B`	二进制后右移 B 位，即去掉最后 B 位，相当于 `A/(2^B)`

补码是常用的表示负数的方法，数字上来讲是模减去绝对值。

正数的补码=原码，负数的补码=绝对值取反后加 1。

a & 0xf

0x是十六进制数的开头， 0xf 表示十六进制数字 f（15），二进制的 1111。 a & 0xf 则是只保留 a的后四位。

2 的 n 次幂在二进制下，为100..00模式。例： 2=10, 4=100, 8=1000……

而其补码（取反加一）则刚好只有最高位相同。例： -2=11111110 和 2=10 。

如果利用二进制来表达集合，（1 表示有，0 表示没有），求子集：

for(let j=k; j=(j-1)&k; j!=k)

其中j是假设的子集（每次循环出一个），k是集合的二进制表示。

设节点标号为i，则其左孩子节点为2*i，右孩子节点为2*i+1，父节点为i/2（floor）。

第 n 行最左边是2^n，右边是2^(n+1)-1。（从第 0 行开始）

参考资料