1. 位运算

  1. << 左移   0011 << 1 = 0110
  2. >> 右移   0110 >> 1 = 0011
  3. |  按位或 0011 | 1011 = 1011
  4. &  按位与 0011 & 1011 = 0011
  5. ~  取反  ~0011 = 1100
  6. ^  异或  0011 ^ 1011 = 1000

1.1 异或常见特殊操作

  • x ^ 0 = x
  • x ^ ~0 = ~x
  • x ^ x = 0
  • c = a ^ b 可得
    • a ^ c = b
    • b ^ c = a

      1.2 二进制常用操作

  1. 将x右边的n位清零：x & (~0 << n)
  2. 获取x的第n位： (x >> n) & 1
  3. 获取x的第n位的幂值：x & (1 << (n-1))
  4. 仅将第n位设置成1: x | (1 << n)
  5. 仅将第n位设置成1: x & (~ (1 << n))
  6. 将x最高位至第n位设置成0：x & ((1 << n) - 1)

  7. 将第n位到第0位设置成0：x & (~((1 << (n + 1)) - 1))

  8. 判断奇偶：

x % 2 == 1 等同于 (x & 1) ==1
x % 2 == 0 等同于 (x & 1) ==0

  1. 取半数

x = x / 2 等同于 x = x >> 1
mid = (left + right) / 2 等同于 mid = (left + right) >> 1

  1. 去掉最低位的1

x = x & (x - 1)

  1. 得到最低位到1

x & -x

1.3 题

  1. number-of-1-bits

// for loop
// x & (x - 1) 去除最后一个1 可以写成 x &= x - 1

  1. power-of-two

x != 0 && (x & (x - 1) ) == 0 即可

  1. reverse-bits

// int —> “010101” ——> reverse string ——> int
// 位移相加

  1. n-queens

// 位运算替代判重数组

  1. n-queens-ii

  2. counting-bits

//

2. 布隆过滤器 BloomFilter

2.1 基础概念

  • 使用一个很长的二进制和一系列随机映射函数（哈希函数）。布隆过滤器可以用于检测一个元素是否在一个集合中。

image.png

  • 优缺点：
    • 优点：空间效率和时间效率都远远超过一般都算法。
    • 缺点：有一定的误识别率和删除困难。
  • 特点：
    • 一个元素会有多个位来标识。
    • 检测存在是时候只有有一个二进制位为0就是不存在。
    • 如果检测存在的时候所有的二进制位都为1，只能代表可能存在，并不代表一定存在！

2.2 代码实现

3. LRU （Least Recently Used）

  • 其他：LFU （Least Freqently Used）最少频次使用

    3.1 基本

  • 两个要素：大小、替换策略

  • HashTable 和 Double LinkedList
  • O(1) 查询 、修改

3.2 代码 lru-cacahe