目錄
一渡处、引言
二座享、離散數(shù)學(xué)中的集合
三捕犬、位串和按位運算符
四亿昏、在編程中使用位串和按位運算符
五龟再、練習(xí)題
六、拓展閱讀
本文的示例代碼用編程語言 Swift 5.0 實現(xiàn)寨蹋，但只要你熟悉任何編程語言兴想，都可以順暢讀完本文斩例。
一吼具、引言
在實際編程中僚纷，我們經(jīng)常需要對某事物的某狀態(tài)進(jìn)行分類，比如把食品的口味分為酸馍悟，甜畔濒，苦和辣剩晴，把網(wǎng)絡(luò)請求的過程分為初始锣咒，請求中，成功和失敗赞弥，把用戶的狀態(tài)分為已登錄和未登錄毅整。很多編程語言都提供 枚舉(enums) 來讓我們表達(dá)和處理這類問題，比如在 Swift 中绽左，我們可以定義一個枚舉 Taste 悼嫉，來表達(dá)食品的 4 種不同口味：
enum Taste {
case sour, sweet, bitter, spicy
}
棒棒糖是甜的，咖啡是苦的拼窥，要將它們表達(dá)出來戏蔑，很簡單，只需要聲明兩個 Taste 類型的變量鲁纠，值分別是 sweet 和 bitter ：
let lollipop: Taste = .sweet
let coffee: Taste = . bitter
如果我們想判斷某食品是否好吃（假設(shè)帶甜味的好吃）总棵，只需要一個方法，將食品的口味作為唯一參數(shù)改含，判斷它是否等于 .sweet情龄，然后將判斷結(jié)果返回：
func isDelicious(taste: Taste) -> Bool {
return taste == .sweet
}
isDelicious(taste: lollipop) // true, ?? 棒棒糖好吃
isDelicious(taste: coffee) // false, ?? 咖啡不好喝
目前看起來不錯。
但很多食物捍壤，不是單一口味的骤视，而是混合了多種口味，比如又酸又甜的酸奶鹃觉。我們好像無法用一個 Taste 類型的變量來表示酸奶专酗，因為大多數(shù)編程語言中的枚舉只允許同時存在一個值。但我們可以用一個 Taste 類型的數(shù)組變量來表示：
let yoghourt: [Taste] = [.sweet, .sour]
這樣寫沒問題盗扇，但我們不得不修改已經(jīng)寫好的 isDelicious(taste:) 方法笼裳，因為現(xiàn)在有一些食物的類型不是 Taste唯卖，而是 [Taste]，我們需要處理混合口味：
func isDelicious(tastes: [Taste]) {
return tastes.contains(.sweet)
}
由于我們將方法參數(shù)改成了 [Taste]躬柬，我們也不得不修改已經(jīng)聲明的 lollipop 和 coffee拜轨，使其類型為 [Taste]，即使它們是單一口味的：
let lollipop: [Taste] = [.sweet]
let coffee: [Taste] = [.bitter]
let yoghourt: [Taste] = [.sweet, .sour]
isDelicious(tastes: lollipop) // true, ?? 棒棒糖好吃
isDelicious(tastes: coffee) // false, ?? 咖啡不好喝
isDelicious(tastes: yoghourt) // true, ?? 酸奶好喝
當(dāng)然允青，也可以不修改 lollipop 和 coffee 的類型橄碾，在使用 isDelicious(taste:) 的時候臨時用一個數(shù)組來包裹它們，像這樣：
let lollipop: Taste = .sweet
let coffee: Taste = .bitter
let yoghourt: [Taste] = [.sweet, .sour]
isDelicious(tastes: [lollipop]) // true, ?? 棒棒糖好吃
isDelicious(tastes: [coffee]) // false, ?? 咖啡不好喝
isDelicious(tastes: yoghourt) // true, ?? 酸奶好喝
兩種寫法都可以颠锉，我們的目的不是討論它們的優(yōu)劣》ㄉ現(xiàn)在我們的代碼終于能同時處理單一口味和混合口味了，但產(chǎn)生了一些問題：
- 注意
isDelicious(taste:)方法的內(nèi)部實現(xiàn)琼掠，從簡單的==判斷變成了判斷數(shù)組是否包含某個元素拒垃。雖然我們使用了 Swift 提供的contains(_:)方法來替代我們手動進(jìn)行遍歷判斷，但在大多數(shù)語言里瓷蛙，這都不是一個高效的方式悼瓮。事實上，Swift 官方文檔 已經(jīng)告訴我們contains(_:)的時間復(fù)雜度是 O(n)艰猬，其中 n 是數(shù)組元素的總個數(shù)横堡。當(dāng)數(shù)組包含大量元素時，contains(_:)方法會造成明顯的性能問題冠桃。 - 也許我們不僅僅需要判斷某食品是否包含某種口味命贴，還需要判斷某食品是否不包含某種口味，甚至需要得出某種食品不包含的口味有哪些食听。
Taste和[Taste]都無法讓我們高效簡單地實現(xiàn)這些需求胸蛛。
本文提供一種方法，允許我們更簡單地表達(dá)單一口味和多種口味樱报，同時葬项，不增加后續(xù)各種檢測的時間復(fù)雜度。在學(xué)習(xí)它之前肃弟，我們需要先了解一些數(shù)學(xué)知識玷室。
二、離散數(shù)學(xué)中的集合
集合（Sets）笤受，在離散數(shù)學(xué)中穷缤，指一堆無序的元素，元素可以是重復(fù)的箩兽，元素可以是任何對象（指任何事物津肛，并非面向?qū)ο笾械膶ο螅Ｎ覀兛梢杂眠@樣的方式來表示一個集合：
A = {a, b, c, d} A 是一個集合汗贫，A 包含 a身坐，b秸脱，c 和 d 四個元素。
B = {a, b, e} B 也是一個集合部蛇，B 包含 a摊唇，b 和 e 三個元素。
現(xiàn)在我們來定義一些常用的集合運算涯鲁。
集合 A 和 B 的并集（The Union of Sets）巷查，用符號 ∪ 表示。并集的結(jié)果是另一個集合抹腿，這個集合的元素或?qū)儆诩?A岛请，或?qū)儆诩?B：
A ∪ B = {a, b, c, d, e} A 和 B 的并集的元素或者屬于 A 或者屬于 B
集合 A 和 B 的交集（The Intersection of Sets），用符號 ∩ 表示警绩。交集的結(jié)果是另一個集合崇败，這個集合的元素既屬于集合 A，也屬于集合 B：
A ∩ B = {a, b} A 和 B 的交集的元素既屬于 A 也屬于 B
集合 A 和 B 的差集（The Difference of Sets）肩祥，用符號 - 表示后室。差集的結(jié)果是另一個集合，這個集合的元素只屬于集合 A搭幻，不屬于集合 B：
A - B = {c, d} A 和 B 的差集的元素只屬于 A 不屬于 B
集合 A 和 B 的差集咧擂，也可以說成是 在集合 A 下逞盆，集合 B 的補集檀蹋。
事實上，我們可以用集合及其運算來描述“食品問題”云芦。首先俯逾，我們用集合來重寫之前用枚舉定義的 Taste 類型
Sour = {sour} Sour 是代表酸的集合，只包含元素“酸”
Sweet = {sweet} Sweet 是代表甜的集合舅逸，只包含元素“甜”
Bitter = {bitter} Bitter 是代表苦的集合桌肴，只包含元素“苦”
Spicy = {spicy} Spicy 是代表辣的集合，只包含元素“辣”
Taste = Sour ∪ Sweet ∪ Bitter ∪ Spicy = {sour, sweet, bitter, spicy} Taste 是代表所有口味的集合
接著琉历，我們就可以表達(dá)不同食品的口味了：
Lollipop = Sweet = {sweet} 棒棒糖是甜的坠七，所以我們直接將代表甜的集合作為棒棒糖的口味
Coffee = Bitter = {bitter} 咖啡是苦的，所以我們直接將代表苦的集合作為咖啡的口味
Yoghourt = Sweet ∪ Sour = {sweet, sour} 我們用甜的集合與酸的集合的并集作為酸奶的口味
到現(xiàn)在旗笔，無論食品的口味是單一的彪置，還是混合的，我們都能用集合將其表達(dá)出來蝇恶，比如拳魁，某種黑暗料理可能是既苦又辣又甜的：
DarkFood = Sweet ∪ Bitter ∪ Spicy = {sweet, bitter, spicy}
注意，黑暗料理的口味包含除酸以外的所有口味撮弧，因此我們也可以這樣表達(dá)黑暗料理：
DarkFood = Taste - Sour = {sweet, bitter, spicy}
當(dāng)我們接受到一個任意的食品口味集合后潘懊，如何像 isDelicious(taste:) 一樣判斷它是否好吃呢：
假設(shè) SomeFood 是某食品口味的集合
如果 SomeFood ∩ Sweet 的結(jié)果包含 sweet 元素姚糊，則 SomeFood 好吃，否則不好吃
Lollipop ∩ Sweet = {sweet} ∩ {sweet} = {sweet} 因此棒棒糖好吃
Coffee ∩ Sweet = {bitter} ∩ {sweet} = {} 因此咖啡不好喝
Yoghourt ∩ Sweet = {sour, sweet} ∩ {sweet} = {sweet} 因此酸奶好吃
如果仔細(xì)觀察授舟，我們會發(fā)現(xiàn)上面的交集結(jié)果救恨，要么等于 Sweet 要么是一個空集（空集，指一個沒有任何元素的集合）释树。我們也可以得出棒棒糖不包含的口味了：
Taste - Lollipop
= {sour, sweet, bitter, spicy} - {sweet}
= {sour, bitter, spicy}
用集合來處理“食品問題”是不錯的選擇忿薇，但問題是，上面的運算并不是編程語言代碼躏哩，只是一堆數(shù)學(xué)符號而已署浩！我們必須用編程語言來描述集合及其運算，才能真正使用它扫尺。
三筋栋、位串和按位運算符
緊接著上面的問題，要用編程語言來描述集合正驻，我們有很多方式弊攘。比如，我們可以為集合定義一個類型然后實現(xiàn)并集交集等方法姑曙，事實上襟交，一些編程語言內(nèi)置提供了這樣的類型，比如 Swift 中的 Set 和 Java 中的 HashSet伤靠。Swift 中的 Set 非常尊重集合在數(shù)學(xué)中的定義和相關(guān)操作捣域，是用來處理集合相關(guān)問題的極佳方式。
但這里宴合，我們介紹另一種辦法來描述集合焕梅，它在“食品問題”中更加通用和高效， 也允許我們在 C/C++ 或 JavaScript 等等這些沒有直接提供集合類型的語言中方便地進(jìn)行集合的相關(guān)運算卦洽。
在離散數(shù)學(xué)中贞言，位（Bits）是值為 0 或 1 的數(shù)字。 位串（Bit strings）阀蒂，是任意長度的連續(xù)的位该窗。比如：
ABitString = 01011，ABitString 是長度為 5 的位串蚤霞，從右到左的 5 個位的值分別是 1, 1, 0, 1, 0
BBitString = 10000酗失，BBitString 是長度為 5 的位串，從右到左的 5 個位的值分別是 0, 0, 0, 0, 1
和集合一樣争便，我們也定義一些位串的常用運算级零，這些運算被稱為 按位運算符（Bitwise Operators）。
位串 ABitString 和 BBitString 的 按位并（Bitwise AND），用符號 & 表示奏纪，運算結(jié)果是另一個位串鉴嗤，從右到左，它的第 i 位的值是 1 如果 ABitString 的第 i 位是 1 且 BBitString 的第 i 位是 1序调，否則為 0：
ABitString & BBitString = 01011 & 10000 = 00000
位串 ABitString 和 BBitString 的 按位或（Bitwise OR）醉锅，用符號 | 表示，運算結(jié)果是另一個位串发绢，從右到左硬耍，它的第 i 位的值是 1 如果 ABitString 的第 i 位是 1 或 BBitString 的第 i 位是 1，否則為 0：
ABitString | BBitString = 01011 | 10000 = 11011
位串 ABitString 的 按位非（Bitwise NOT）边酒，用符號 ~ 表示经柴，運算結(jié)果是另一個位串，從右到左墩朦，它的第 i 位的值是 1 如果 A 的第 i 位是 0坯认，否則為 0：
~ABitString = ~01011 = 10100
注意，我們只能對長度相同的兩個位串進(jìn)行按位并和按位或氓涣，如果長度不同牛哺，我們通常會在長度小的位串前面補 0，直到它的長度等于另一個位串：
C = 01
D = 1110
C & D = 01 & 1110 = 0001 & 1110 = 0000
現(xiàn)在劳吠，我們用位串的方式來描述集合引润。先給出集合 Sour 的位串：
SourBitString = 1000
我們可以這么理解：SourBitString 的 4 個位，從左到右痒玩，分別代表元素 sour, sweet, bitter 和 spicy淳附。位的值如果是 1，代表此元素屬于當(dāng)前集合凰荚，0 代表此元素不屬于當(dāng)前集合燃观。同理褒脯，我們可以給出其他三個集合的位串：
SweetBitString = 0100
BitterBitString = 0010
SpicyBitString = 0001
我們已經(jīng)用位串分別表示了集合 Sour, Sweet, Bitter 和 Taste便瑟。如果我們將這 4 個位串進(jìn)行按位或運算：
SourBitString | SweetBitString | BitterBitString | SpicyBitString
= 1000 | 0100 | 0010 | 0001
= 1111
結(jié)果是另一個位串，它代表的集合正是集合 Taste番川。集合 Taste 是我們在第二節(jié)中通過集合 Sour, Sweet, Bitter 和 Taste 的并集運算得出的到涂。我們好像可以得出，位串的按位或等同于集合的并集颁督。
我們現(xiàn)在來表達(dá)不同食品的口味：
LollipopBitString = SweetBitString = 0100
CoffeeBitString = BitterBitString = 0010
YoghourtBitString = SweetBitString | SourBitString = 1100
DarkFoodBitString = SweetBitString | BitterBitString | SpicyBitString = 0111
或者我們也可以這樣定義 DarkFoodBitString
DarkFoodBitString = ~SourBitString = 0111
從上面的運算中践啄，我們可以得出，位串的按位非等同于集合與當(dāng)前集合的差集
繼續(xù)沉御，我們用位串來判斷某食品是否好吃：
LollipopBitString & SweetBitString = 0100 因此棒棒糖好吃
CoffeeBitString & SweetBitString = 0000 因此咖啡不好喝
YoghourtBitString & SweetBitString = 0100 因此酸奶好吃
從上面的運算中屿讽，我們可以得出，位串的按位并等同于集合的交集。
我們也可以用位串得出棒棒糖不包含的口味
~LollipopBitString = 1011
至此伐谈，我們成功地用位串和按位運算來替代了集合和集合運算烂完。
四、在編程中使用位串和按位運算符
幸運的是诵棵，大多數(shù)語言抠蚣，都直接提供了按位運算符。現(xiàn)在履澳，我們用 Swift 來實現(xiàn)第三節(jié)的位串和按位運算嘶窄。
首先，我們定義一個變量 sour 來表示 SourBitString：
// 我們用 Int 類型來表示位串距贷，因為 Int 類型本質(zhì)上是長度為 32 或 64 的二進(jìn)制數(shù)字
// 在性能敏感的場景下柄冲，我們也可以選擇 UInt8 等長度更小的類型
// 我們用 0b 前綴來告訴編譯器后面的數(shù)字是二進(jìn)制形式的
// 我們也可以直接使用十進(jìn)制數(shù)字 8，甚至是十六進(jìn)制形式 0x8忠蝗，它們完全等同羊初。
// 但在這里，二進(jìn)制形式的寫法更容易讓我們理解現(xiàn)在發(fā)生了什么
let sour: Int = 0b1000
然后什湘，同理长赞，定義三個變量來表示其他三個位串：
let sweet: Int = 0b0100
let bitter: Int = 0b0010
let spicy: Int = 0b0001
上面的寫法沒問題，但其實闽撤，我們更傾向于這樣寫：
let spicy: Int = 1 << 0 // 等同于二進(jìn)制形式 0b0001得哆，或位串 0001
let bitter: Int = 1 << 1 // 等同于二進(jìn)制形式 0b0010，或位串 0010
let sweet: Int = 1 << 2 // 等同于二進(jìn)制形式 0b0100哟旗，或位串 0100
let sour: Int = 1 << 3 // 等同于二進(jìn)制形式 0b1000贩据，或位串 1000
注意，我們剛剛使用的是二進(jìn)制形式的寫法闸餐。但現(xiàn)在我們使用的是十進(jìn)制數(shù)字 + 左移的寫法饱亮。左移是另一個按位運算符 <<，我們稱它為按位左移運算符（Bitwise Left Shift Operator）舍沙。它的作用是將位串的所有位向左移動 n 個位置近上。超出位串邊界的位將被移除，右邊留空的位用 0 補上拂铡。比如：
我們將位串 001101 向左移 2 位
001101 << 2 = 110100
在上面的定義中壹无，我們先讓 spicy 的值為十進(jìn)制數(shù)字 1（等同于二進(jìn)制 0b1，如果我們在前面不斷補 0感帅，0b1 也等同于 0b0001）斗锭，然后對 1 進(jìn)行按位左移 0 位，因此失球，spicy 的值依舊等同于 0b0001岖是。按同樣的邏輯，我們分別對十進(jìn)制數(shù)字 1 進(jìn)行左移 1，2 和 3 位來得到了 bitter豺撑，sweet 和 sour作箍。
相比給每個變量寫固定的二進(jìn)制形式的值，我們更喜歡對 1 進(jìn)行左移來給不同的變量賦值前硫。因為兩種寫法的實際效果雖然是等同的胞得，但第一種寫法更容易讓我們寫錯（肉眼區(qū)分大量的 0 和 1 并不容易）。如果你有 Cocoa 和 Objective-C 編程經(jīng)驗屹电，應(yīng)該見過類似的用法阶剑，比如 UIView 頭文件中的 UIViewAnimationOptions。如果你有 Android 和 Java 編程經(jīng)驗危号，也應(yīng)該見過類似的用法牧愁，比如 AlarmManager 中的 FLAG_WAKE_FROM_IDLE。
繼續(xù)外莲，我們現(xiàn)在可以表示出 TasteBitString：
let taste = spicy | bitter | sweet | sour // taste 的值是 15猪半，對應(yīng)二進(jìn)制 1111
接著是我們的食品：
let lollipop = sweet
let coffee = bitter
let yoghourt = sour | sweet
let darkFood = sweet | bitter | spicy
isDelicious(taste:) 也可以被重寫：
func isDelicious(taste: Int) -> Bool {
return taste & sweet == sweet
}
至此，我們用位串和按位操作代表了集合和集合運算偷线，最終替代了最開始的枚舉方式磨确。所有食品口味都是 Int 類型，避免了 Taste 和 [Taste]声邦，在檢測的時候乏奥，我們也保證了極小的時間復(fù)雜度。
如果你使用的是其他語言亥曹，到此就結(jié)束了邓了。但在 Swift 里，我們還可以進(jìn)一步優(yōu)化我們的代碼媳瞪。由于這樣的寫法是如此的頻繁骗炉，Swift 內(nèi)置提供了專門用來處理此類問題的類型 OptionSet，使用 OptionSet 可以避免我們手動進(jìn)行按位運算蛇受，以及與其他 Swift 代碼保持統(tǒng)一的規(guī)范句葵。
現(xiàn)在我們可以用 OptionSet 來完成我們的最終代碼：
struct TasteOptions: OptionSet {
let rawValue: Int
static let spicy = TasteOptions(rawValue: 1 << 0)
static let bitter = TasteOptions(rawValue: 1 << 1)
static let sweet = TasteOptions(rawValue: 1 << 2)
static let sour = TasteOptions(rawValue: 1 << 3)
static let all: TasteOptions = [.spicy, .bitter, .sweet, .sour]
}
let lollipop: TasteOptions = .sweet
let coffee: TasteOptions = .bitter
let yoghourt: TasteOptions = [.sour, .sweet]
let darkFood: TasteOptions = [.sweet, .bitter, .spicy]
func isDelicious(tasteOptions: TasteOptions) -> Bool {
return tasteOptions.contains(.sweet)
}
isDelicious(tasteOptions: lollipop)
isDelicious(tasteOptions: coffee)
isDelicious(tasteOptions: yoghourt)
isDelicious(tasteOptions: darkFood)
注意，雖然使用 OptionsSet 后龙巨，我們的檢測方法依舊叫 contains(_:)笼呆，但其內(nèi)部實現(xiàn)采用的是按位運算，而非遍歷比較旨别。如果你想確認(rèn)這一步，可以閱讀 OptionSet 的源代碼汗茄。
五秸弛、練習(xí)題
在第四節(jié)中，我們介紹了按位左移運算符。有左就有右递览，按位右移運算符（Bitwise Right Shift Operator） 的作用是將位串的所有位向右移動 n 個位置叼屠。超出位串邊界的位將被移除，左邊留空的位用 0 補上绞铃。比如：
我們將位串 001101 向右移 2 位
001101 >> 2 = 000011
- 你能否用按位右移運算符來改寫下面的代碼镜雨，同時保證每個變量的實際值不變？
let spicy: Int = 1 << 0 // 等同于二進(jìn)制形式 0b0001儿捧，或位串 0001
let bitter: Int = 1 << 1 // 等同于二進(jìn)制形式 0b0010荚坞，或位串 0010
let sweet: Int = 1 << 2 // 等同于二進(jìn)制形式 0b0100，或位串 0100
let sour: Int = 1 << 3 // 等同于二進(jìn)制形式 0b1000菲盾，或位串 1000
- 第四節(jié)中我們討論過更傾向于使用按位左移運算符颓影，而不是手動寫二進(jìn)制形式的數(shù)字。你能解釋為什么我們更傾向于使用按位左移運算符懒鉴，而不是按位右移運算符嗎诡挂？
