簡介
Redis 使用字串物件來表示位陣列，因為字串物件使用的 SDS 資料結構是二進制安全的，所以程式可以直接使用 SDS 結構來保存位陣列，并使用 SDS 結構的操作函式來處理位陣列，
在 SDS 結構當中，buf 位元組陣列除了字串結尾的 \0 空字符，其余的位置都存盤著一個位元組長的位陣列，一個位元組可以存盤 8 位的二進制，
這里需要注意的是，在 buf 陣列中存盤的二進制位陣列的順序與實際書寫的順序相反，比如 01010101 存盤在 buf 陣列中的結構是 10101010 這樣的倒序，使用逆序來保存位陣列可以簡化 SETBIT 的實作，
命令使用
Redis 提供了 GETBIT、SETBIT、BITCOUNT、BITOP、BITPOS、BITFIELD、BITFIELD_RO 等命令用于處理二進制位陣列，
GETBIT
GETBIT <bitarray> <offset> 命令用于回傳位陣列 bitarray 在 offset 偏移量上的二進制位的值，其詳細執行程序如下：
- 計算
byte = offset / 8得到offset偏移量指定的二進制位保存在位陣列的哪個位元組； - 計算
bit = (offset mod 8) + 1得到offset偏移量指定的二進制位是byte位元組的第幾個二進制位； - 根據
byte值和bit值，在位陣列bitarray中定位offset偏移量指定的二進制位，并回傳這個位的值，
SETBIT
SETBIT <bitarray> <offset> <value> 可以看作是 GETBIT 的反向操作，只是需要注意設定二進制位時有可能需要擴展 buf 陣列的長度，
具體的執行程序如下：
- 計算
len = (offset / 8) + 1得到保存offset偏移量指定的二進制位需要多少位元組； - 檢查
bitarray位陣列的長度是否滿足要求，否則需要對 SDS 的進行擴展，并且將新增的二進制位全部置為 0； - 計算
byte = offset / 8得到offset偏移量指定的二進制位保存在位陣列的哪個位元組； - 計算
bit = (offset mod 8) + 1得到offset偏移量指定的二進制位是byte位元組的第幾個二進制位； - 根據
byte值和bit值，在位陣列bitarray中定位offset偏移量指定的二進制位，首先將這個位現在的值保存在oldvalue變數中，然后將新值value設定為這個二進制位的值； - 向客戶端回傳
oldvalue的值，
由于 buf 陣列使用逆序保存位陣列，當 Redis 對 buf 陣列進行擴展之后，寫入操作都可以直接在新擴展的二進制位中完成，而不必改動位陣列原來已有的二進制位，
BITCOUNT
BITCOUNT key [start] [end] 命令用于統計給定位陣列中，值為 1 的二進制位的數量，
BITOP
BITOP operation destkey key [key ...] 支持對一個或多個保存二進制位的字串 key 進行位元操作，并將結果保存到 destkey 上，operation 可以是 AND 、 OR 、 NOT 、 XOR 這四種操作中的任意一種：
AND: 邏輯與OR: 邏輯或NOT: 邏輯非XOR: 邏輯異或
因為 BITOP AND、BITOP OR、BITOP XOR 三個命令可以接受多個位陣列作為輸入，程式需要遍歷輸入的每個位陣列的每個位元組來進行計算，所以這些命令的復雜度為 \(O(n^2)\)；與此相反，因為 BITOP NOT 命令只接受一個位陣列輸入，所以它的復雜度為 \(O(n)\)，
BITPOS
BITPOS key bit [start [end [BYTE | BIT]]] 回傳字串中設定為 1 或 0 的第一個位的位置，
默認情況下，整個字串都會被檢索一遍，命令的
使用 start 和 end 引數默認可以指定一個位元組的范圍，在 7.0.0 版本之后，提供了 BYTE 和 BIT 指定以位元組為范圍還是位為范圍，
二進制位統計演算法
BITCOUNT 命令要做的作業初看上去并不復雜，但實際上要高效地實作這個命令并不容易，需要用到一些精巧的演算法，
遍歷演算法
實作 BITCOUNT 命令最簡單直接的方法，就是遍歷位陣列中的每個二進制位，并在遇到值為 1 的二進制位時，將計數器的值增一，
遍歷演算法雖然實作起來簡單，但效率非常低，因為這個演算法在每次回圈中只能檢查一個二進制位的值是否為 1，所以檢查操作執行的次數將與位陣列包含的二進制位的數量成正比，
查表演算法
查表演算法就是創建一個表，表的鍵為某種排列的位陣列，而表的值則是相應位陣列中值為 1 的二進制位的數量，
創建了這種表之后，就可以根據輸入的位陣列進行查表，在無須對位陣列的每個位進行檢查的情況下，直接知道這個位陣列包含了多少個值為 1 的二進制位，
初看起來，只要創建一個足夠大的表，那么統計作業就可以輕易地完成，但這個問題實際上并沒有那么簡單，因為查表法的實際效果會受到記憶體和快取兩方面因素的限制：
- 查表法是典型的空間換時間策略，演算法在計算方面節約的時間是通過花費額外的記憶體換取而來的，節約的時間越多，花費的記憶體就越大，
- 查表法的效果還會受到 CPU 快取的限制，對于固定大小的 CPU 快取來說，創建的表格越大，CPU 快取所能保存的內容相比整個表格的比例就越少，查表時出現快取不命中的情況就會越高，快取的換入和換出操作就會越頻繁，最終影響查表法的實際效率，
variable-precision SWAR 演算法
BITCOUNT 命令要解決統計一個位陣列中非 0 二進制位的數量的問題，在數學上被稱為“計算漢明重量（Hamming Weight）”，目前已知效率最好的通用演算法為 variable-precision SWAR 演算法，該演算法通過一系列位移和位運算操作，可以在常數時間內計算多個位元組的漢明重量，并且不需要使用任何額外的記憶體，
以下是一個處理 32 位長度位陣列的 variable-precision SWAR 演算法的實作：
uint32_t swar(uint32_t i){
i = (i & 0x55555555) + ((i>>1) & 0x55555555); // 步驟 1
i = (i & 0x33333333) + ((i>>2) & 0x33333333); // 步驟 2
i = (i & 0x0F0F0F0F) + ((i>>4) & 0x0F0F0F0F); // 步驟 3
i = (i - 0x01010101) >> 24; // 步驟 4
return i;
}
variable-precision SWAR 演算法實質上是通過分而治之的思想，將計算拆解成多個小問題去解決：
- 步驟 1 是將 32 位陣列與
01010101010101010101010101010101做邏輯與操作，并且右移 1 位之后繼續做邏輯與操作，最終取它們的和，這一步的想法是將 32 位拆成每 2 位作為一個組合，統計出每一組中 1 的個數； - 步驟 2 是將上述得到的結果與
00110011001100110011001100110011做邏輯與操作，這一步的想法就是拆成每 4 位作為一個組合，統計出每一組中 1 的個數； - 步驟 3 是將上述得到的結果與
00001111000011110000111100001111做邏輯與操作，這一步的想法就是拆成每 8 位作為一個組合，統計出每一組中 1 的個數； - 上述的結果仍然不是最終想要的結果，步驟 4 就是將上述得到的數字計算出 1 真正的數量，
i - (0x01010101)計算出漢明重量并記錄在二進制的高八位，>> 24陳述句則通過右移運算，將漢明重量移到最低八位，最后二進制對應的十進制就是漢明重量，
因為 variable-precision SWAR 演算法是一個常數復雜度的操作，所以可以按照自己的需要，在一次回圈中多次執行 variable-precision SWAR 演算法，從而按倍數提升計算漢明重量的效率，
當然，在一個回圈里執行多個 variable-precision SWAR 演算法呼叫這種優化方式是有極限的：一旦回圈中處理的位陣列的大小超過了快取的大小，這種優化的效果就會降低并最終消失，
Redis 的實作
BITCOUNT 命令的實作用到了查表和 variable-precision SWAR 兩種演算法：
- 如果未處理處理的二進制位的數量小于 128 位，那么程式使用查表演算法來計算二進制位的漢明重量，表中記錄了 0x00 ~ 0xFF 在內的所有二進制位的漢明重量
- 如果未處理的二進制位的數量大于等于 128 位，那么程式使用 variable-precision SWAR 演算法來計算二進制位的漢明重量，每次處理 128 個二進制位，呼叫 4 次 32 位 variable-precision SWAR 演算法來計算其漢明重量
實際上 BITCOUNT 命令實作的演算法復雜度為 \(O(n)\)，其中 n 為輸入二進制位的數量，
首發于「程式員翔仔」，點擊查看更多，
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/553136.html
標籤：NoSQL
上一篇：Redis單機部署
下一篇：返回列表