為什麼需要位運算

機器裏的數字表示方式和存儲格式就是二進制

位運算符

指定位置的位運算

1. 將x最右邊的n位清零：x&(~0<<n)
2. 獲取x的第n位值(0或者1)：(x>>n)&1
3. 獲取x的第n位的冪值：x&(1<<n)
4. 僅將第n位置為1：x|(1<<n)
5. 僅將第n位置為0：x&(~(1<<n))
6. 將x最高位至第n位(含)清零：x&((1<<n)-1)
7. 將第n位至第0位(含)清零：x&(~((1<<(n+1))-1))

實戰位運算要點

判斷奇偶：
x % 2 == 1 —> (x & 1) == 1
x % 2 == 0 —> (x & 1) == 0

除 2 ：
x >> 1 —> x / 2

x = x & (x - 1) 清零最低位的1

x & -x 得到最低位的 1

x & ~x 0

Bloom Filter vs Hash Table

一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用於檢索一個元素是否在一個集合中。

優點是空間效率和查詢時間都遠遠超過一般的算法， 缺點是有一定的誤識別率和刪除困難。

排序算法

1. 比較類排序：通過比較來決定元素間的相對次序，由於其時間複雜度不能突破
   O(nlogn)，因此也稱為非線性時間比較類排序。
2. 非比較類排序:
   不通過比較來決定元素間的相對次序，它可以突破基於比較排序的時間下界，以線性時間運行，因此也稱為線性時間非比較類排序。

初級排序 - O(n^2)

1. 選擇排序(Selection Sort) 每次找最小值，然後放到待排序數組的起始位置。
2. 插入排序(Insertion Sort) 從前到後逐步構建有序序列;對於未排序數據，在已排序序列中從後 向前掃描，找到相應位置並插入。
3. 冒泡排序(Bubble Sort) 嵌套循環，每次查看相鄰的元素如果逆序，則交換。

高級排序 - O(N*LogN)

4. 快速排序(Quick Sort)
   數組取標杆 pivot，將小元素放 pivot左邊，大元素放右側，然後依次 對右邊和右邊的子數組繼續快排;以達到整個序列有序。

5. 歸併排序(Merge Sort)— 分治

   1. 把長度為n的輸入序列分成兩個長度為n/2的子序列;
   2. 對這兩個子序列分別採用歸併排序;
   3. 將兩個排序好的子序列合併成一個最終的排序序列。

歸併和快排具有相似性，但步驟順序相反
歸併：先排序左右子數組，然後合併兩個有序子數組
快排：先調配出左右子數組，然後對於左右子數組進行排序

6. 堆排序(Heap Sort) — 堆插入 O(logN)，取最大/小值 O(1)

   1. 數組元素依次建立小頂堆
   2. 依次取堆頂元素，並刪除

特殊排序 - O(n)

7. 計數排序(Counting Sort)
   計數排序要求輸入的數據必須是有確定範圍的整數。將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中;然後依次把計數大於 1 的填充回原數組
8. 桶排序(Bucket Sort)
   桶排序 (Bucket sort)的工作的原理：假設輸入數據服從均勻分佈，將數據分到有限數量的桶裏，每個桶再分別排序(有可能再使用別的排序算法或是以遞歸方式 繼續使用桶排序進行排)。
9. 基數排序(Radix Sort)
   基數排序是按照低位先排序，然後收集;再按照高位排序，然後再收集;依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按 高優先級排序。