学习笔记

位运算

• 异或：不进位加法
  • x ^ 0 = x
  • x^ 1s(全1，0取反 ~0)
  • x & ~x = 1s
  • x^x=0
  • swap：c = a ^ b => a ^ c = b, b ^ c = a
  • a ^ b ^ c = (a ^ b) ^ c = a ^ (b ^ c)
• 实际应用
  • 判断奇偶
    • 奇数: x % 2 = 1 -> x & 1 = 1
    • 偶数：x % 2 = 0 -> x & 1 = 0
  • 判断二的n次幂
    • x & ( x - 1) == 0
  • 中位数
    • mid = (left + right) / 2 -> mid = (left + right) >> 1
  • 去最低位1
    • x = x & (x - 1)
  • 得到最低位的1
    • x & -x
  • x & ~x = 0

布隆过滤器

• 位数组 + n个 hash函数
• 不精确：不在一定不在，在不一定在

应用

• 缓存击穿
• 垃圾邮件
• 集合判重

LRU

• 双向链表 + hash表
• Java可用LinkedHashMap实现

排序算法

比较类排序

• 交换
  • 冒泡
  • 快排
• 插入
  • 简单插入
  • 希尔
• 选择
  • 简单选择
  • 堆
• 归并
  • 二路归并
  • 多路归并

非比较类排序

• 计数
• 桶
• 基数