木易

# Road Map

打怪路线：

  • 模板题：191
  • 位运算实现四则运算：371 -> 29 ->
  • 计数：136 -> 137 -> 260
  • 状态压缩表示：78 -> 847
  • 编码：89 -> 393
  • 补码和进制转换：476 -> 405 ->

# 位运算常用技巧

# 六种基本运算

  1. 与 a & b
  2. 或 a | b
  3. 取反 ~a
  4. 异或 a ^ b
  5. 左移 <<
  6. 右移 >>

# 技巧型运算

# x & -x

lowbit运算: lowbit(x) = x & -x

应用: 得到 x 的二进制表示中最右边的一个 1

负数在计算机中以补码形式来表示。

补码： 正数的补码就是其本身；负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1。 (即在反码的基础上+1)

000... 1010 => 10
-10 => 0101 + 1 => 111... 0110
1
2

# 模拟加法

a ^ b相当于 a 与 b 的二进制的不进位相加

配合移位操作可以实现加法操作

# 模拟乘以 2 的幂

x << k 相当于 x * 2 的 k 次幂

# 模拟除以 2 的幂

x >> k 相当于 x / 2 的 k 次幂

比如：我们在使用二分算法时，获取 mid，可以 使用 mid = l + (r - l) >> 1

# 模拟整除判断

(x & m) == 0 相当于 x % (m + 1) == 0

我们常用 x & 1 == 0 来判断 x是否是偶数就是利用此条性质

举例：(x & 3) == 0 相当于 x % 4 == 0

# 异或运算交换两个元素

a = a ^ b
b = a ^ b
a = a ^ b
1
2
3

# 将第 k 位置为 1(k 从 0 开始)

x |= (1 << k)

# 将第 k 位置为 0

x &= ~(1 << k)

# 判断第 k 位是不是 1

(x >> i) & 1 或者 x & (1 << i)

# 删除最后一位的 1

  • x & (x - 1)
  • x ^ (x & -x)

# 判断 全是 1

(n & (n + 1)) == 0
1

← 0x02_递归 →