• 在计算机中数字的表示形式不是人类使用的十进制，而是二进制
• 十进制、二进制相互转换
  • 十进制数不断除以二，每次除法所得的余数是从低位到高位排列的

• 左移 <<

  • 左侧移除则没有了
  • 右侧空位补 0

• 右移 >>

  • 右侧移除则没有了
  • 左侧空位补 0

• 按位或 |

• 按位与 &

• 按位取反 ~

• 按位异或 ^

  • x ^ 0 = x
  • x ^ 1s = ~x
  • x ^ (~x) = 1s
  • x ^ x = 0
  • c = a ^ b => a ^ c = b; b ^ c = a
  • a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c

• x & (~0 << n) => 将 x 最右边的 n 位清零
• (x >> n) & 1 => 获取 x 的第 n 位值（0 或 1）
• x & (1 << n) => 获取 x 的第 n 为的幂值
• x | (1 << n) => 仅将第 n 位置为 1
• x & (~ (1 << n)) => 仅将第 n 位置为 0
• x & ((1 << n) - 1) => 将 x 最高位至第 n 位（含）清零

• 判断奇偶

  • x % 2 == 1 或 (x & 1) == 1
  • x % 2 == 0 或 (x & 1) == 0

• 除以二

  • x >> 1
    • mid = (left + right) / 2 => mid = (left + right) >> 1

• 清零最低位的 1

  • x = x & (x - 1)

• 得到最低位的 1

  • x & -x

• x & ~x => 0

• 两个高级的数据结构，在面试及工业中应用广泛

• 经常与 HashTable 对比
• HashTable
  • Hash Function 得到 key
  • 如果 key 重复，使用链表将对应同一个 key 的所有 value 连接起来
  • 所有存在的值都保存在 HashTable 中
  • 没有误差
• 在工业应用中，有时不需要保存所有 value 的信息，只需要知道 value 是否存在
  • 这时，由于 HashTable 会存储冗余的数据，我们需要一种更高效的数据结构来为我们提供某个 value 是否存在这种信息
    • 这里的“高效”主要指存储同样数量的数据，不会存储冗余数据，使用较小存储空间
• Bloom Filter
  • 由一个很长的二进制向量和一系列随机映射函数构成
  • 可以用于检索一个元素是否存在于一个集合中
  • 有点：
    • 空间效率和查询时间都远远超过一般算法
  • 缺点：
    • 有误差
    • 删除困难
  • 原理：
    • 对于任何一个元素，会被分配到一系列的二进制位中
      • 即，如果一个元素存在，则会使用某几个函数将这个元素映射到一个二进制向量的某几个二进制位中，并将那几个二进制位置为 1
    • 在查询时，对于一个给定元素，同样会被映射到几个二进制位中，如果其中有一位为 0，则该元素一定不存在；否则，该元素很可能存在
      • 一般 Bloom Filter 都是在外层作为缓存使用，如果某个元素在 Bloom Filter 中查询结果为存在，则请求会继续向 DB 进行元素 value 的请求（这时，DB 会返回该元素是否存在的确定结果）
• 工业应用
  • 比特币网络
    • 查询某个地址是否存在于某个节点
  • 分布式系统
    • MapReduce
    • Hadoop
    • Search engine
  • Redis 缓存
  • 垃圾邮件、评论等过滤

• 缓存
  • CPU
  • 两个要素
    • 大小：如果缓存喊打的话，就可以随意存了
    • 替换策略：缓存大小往往是有限的，当缓存已经存满数据时，需要将缓存中已有的数据移除一部分才可以继续存储新的数据，这时就需要一个规则来确定哪些数据要被移除
      • LRU Cache 的替换策略：当缓存满了时，把最不常用的数据移除
• LRU Cache 实现
  • HashTable + Double LinkedList
  • 查询：O(1)
  • 更新：O(1)

排序算法有两类：

1. 比较类排序
   • 通过比较来决定元素间的相对次序
   • 由于其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序
   • 算法
     • 交换
       • 冒泡排序
       • 快速排序
     • 插入
       • 简单插入排序
       • 希尔排序
     • 选择
       • 简单选择排序
       • 堆排序
     • 归并
       • 二路归并排序
       • 多路归并排序
2. 非比较类排序
   • 不通过比较来决定元素间相对次序
   • 可以突破基于比较排序的时间下界，以线性时间运行，也称为线性时间非比较类排序

• 算法
  • 计数排序
  • 桶排序
  • 基数排序

1. 选择排序 Selection Sort
   • 每次找最小值，然后放到待排序数组的起始位置

2. 插入排序 Insertion Sort
   • 从前到后逐步构建有序序列；对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
   • 前面的数组已经是有序数组，对于后面未排序的数组，注意找到各个元素应该所在的位置
     • 默认顺序为从小到大
     • 每次要插入的元素都与有序数组的最后一个元素相邻
     • 默认查找元素位置的方式，为从有序数组的最右端开始扫描，如果当前元素比要插入的元素大，则交换两个元素的位置

3. 冒泡排序 Bubble Sort
   • 嵌套循环，每次查看的相邻元素如果逆序，则交换
     • 默认顺序为从小到大
     • 大元素会先被放在最终位置

1. 快速排序 Quick Sort

   • 数组取标杆 pivot，将小元素放在 pivot 左边，大元素放在 pivot 右边，然后依次对左边和右边的子数组继续应用快速排序，直到整个数组成为有序序列
   • 应用最多
   • 分治

2. 归并排序 Merge Sort

• 把长度为 n 的输入序列分成两个长度为 n/2 的子序列，并对这两个子序列分别采用归并排序，最后将两个完成排序的子序列合并成一个最终的排序序列

归并排序和快速排序具有相似性，但步骤顺序相反

• 快速排序：先调配出左右子数组，然后对于左右子数组进行排序
  • 先使用 pivot 将数组分成两部分：左子数组的每个元素都小于 pivot；右子数组的每个元素都大于 pivot；两个子数组中元素此时无序
• 归并排序：先排序左右子数组，然后合并两个有序子数组

3. 堆排序 Heap Sort

• 堆插入、删除 O(logN)
• 取最大值/最小值 O(1)
• 分类
  • 大顶堆
    • 最大的元素放在最前面
  • 小顶堆
    • 最小的元素放在最前面
• 数组元素依次建立小顶堆，依次取堆顶元素，并删除

1. 计数排序 Counting sort

• 要求输入的数据必须是有确定范围的整数。
• 将输入数据的值转化为键存储于额外开辟的数组空间中；然后依次把计数大于 1 的数据填充回原素组
  • 新开辟的数组的 index 值表示的是元素的整数值，数组中的元素表示值为对应 index 的元素在数据中的个数

2. 桶排序 Bucket Sort

• 假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序
  • 有可能使用其他排序算法或是以递归的方式对桶进行排序

3. 基数排序 Radix Sort

• 按照低位先排序，然后收集；再按高位排序，再收集；以此类推，直到最高位。
• 有时元素的某些属性具有优先级，此时，先按低优先级进行排序，再按高优先级进行排序