一些奇妙的bit操作

请设置文章作者

发布于：Dec 29, 2022

次浏览

一些奇妙的bit操作

学习过程中看到 + 推理出的一些奇妙的位运算相关的操作。顺序尽量有一定推理逻辑, 尽量分组写在一起

听说”hacker’s delight”这本书专门讲这些, 但我还没时间看

• assert
  1. 默认从右往左是从低位到高位, aka 右边的末尾

1. +1的效果: 从右到左第一个0, 按位取反(不够加要一直进位)
2. -1的效果: 从右到左第一个1, 按位取反(不够减要一直借位)
3. 快速求补码: 右起第一个1往左, 按位取反
4. n & n-1的效果: 最右边的1变0, 因为-1的效果, 并且可以知道这个被消灭的1的右边都是0
5. N >> 1在二叉树中相当于N/2向下取整, 以用来找当前节点的父节点
6. 补码的负等于对该数取补, -x = (~x + 1)
7. x | (~x + 1)从低位1开始, 往高位全部置1

• xor的性质
  • x xor y = t 等价于 x xor t = y

CSAPP lab1: datalab tips

1. int负数 = 按位取反末位加一: -x = (~x + 1)
   • 减一个数等价于加上这个数的取负
2. 对于一些限制使用的操作, 可以通过变换得到
   • e.g. a | b = ~(~a & ~b), 或者对于bool, a | b = !(!a & !b)
3. 判断相等!(x^x) ,两个相等的数异或得0, 再用!运算符转换成bool