一. 尋找父親節(jié)點和孩子節(jié)點

首先需要回顧一下希爾伯特曲線的生成方式婚脱，具體代碼見筆者上篇文章的分析涨冀，在這個分析中船惨，有4個方向比較重要，接下來的分析需要擂错，所以把這4個方向的圖搬過來味滞。

在舉例之前還需要說明一點，有些網(wǎng)站提供的二進制轉換钮呀，并沒有標明有符號還是無符號的轉換剑鞍，這樣就會導致使用者的一些誤解。筆者開始并沒有發(fā)現(xiàn)這個問題爽醋，導致掉入了這個坑蚁署，好一會才轉過彎來。筆者在網(wǎng)上查詢了很多在線轉換計算器的工具蚂四，都發(fā)現(xiàn)了這個問題光戈。比如常見的在線進制轉換http://tool.oschina.net/hexconvert，隨便找兩個64位的二進制數(shù)遂赠，有符號的和無符號的分別轉換成十進制久妆，或者反過來轉換，你會驚喜的發(fā)現(xiàn)跷睦，兩次結果居然相同筷弦！例如你輸入 3932700003016900608 和 3932700003016900600，你會發(fā)現(xiàn)轉換成二進制以后結果都是 11011010010011110000011101000100000000000000000000000000000000送讲。但是很明顯這兩個數(shù)不同奸笤。

假如 3932700003016900608 是無符號的，3932700003016900600 是有符號的哼鬓，正確的結果應該如下：

// 3932700003016900608
11011010010011110000011101000100000000000000000000000000000000

// 3932700003016900600
11011010010011110000011101000011111111111111111111111111111000

差距明顯很大监右。這種例子其實還有很多，隨便再舉出幾組：無符號的 3932700011606835200 和有符號的 3932700011606835000异希；無符號的 3932700020196769792 和有符號的 3932700020196770000健盒；無符號的 3932700028786704384 和有符號的 3932700028786704400……可以舉的例子很多，這里就不再舉了称簿。

利用網(wǎng)上的這個工具扣癣，十進制轉二進制是無符號的轉換，二進制轉十進制就會變成有符號的轉換了憨降。而 Google S2 默認是無符號的 CellID父虑，所以用有符號的 CellID 會出現(xiàn)錯誤。所以轉換中需要注意一下授药。筆者之前沒有發(fā)現(xiàn)這一點的時候出現(xiàn)了一些問題士嚎，后來突然發(fā)現(xiàn)了這一點，茅塞頓開悔叽。

好了莱衩，進入正題。接下來直接看一個例子娇澎，筆者用例子來說明每個 Cell 之間的關系笨蚁，以及如何查找父親節(jié)點的。

假設有上圖這4個連在一起的 Cell趟庄。先根據(jù)經緯度把 CellID 計算出來括细。

對應的4個 CellID 分別是：

由于前兩位都是0，所以其實可以省略戚啥，但是為了讀者看的更清晰勒极，筆者還是補全了64位，前面2個0還是補上

// 3932700003016900608 右上
0011011010010011110000011101000100000000000000000000000000000000      

// 3932700011606835200 左上
0011011010010011110000011101001100000000000000000000000000000000 

// 3932700020196769792 左下
0011011010010011110000011101010100000000000000000000000000000000

// 3932700028786704384 右下
0011011010010011110000011101011100000000000000000000000000000000

在前篇文章里面我們也分析了 Cell 64位的結構虑鼎，這里是4個 Level 14的 Cell辱匿，所以末尾有 64 - 3 - 1 - 14 * 2 = 32 個 0 。從末尾往前的第33位是一個1炫彩，第34位匾七，第35位是我們重點需要關注的〗ぃ可以看到分別是00昨忆，01，10杉允，11 邑贴。正好是連續(xù)的4個二進制席里。

根據(jù)這個順序，我們可以匹配到當前這4個 Level 14 的 Cell 對應的順序是上圖圖中的圖0 拢驾。只不過當前方向旋轉了45°左右奖磁。

右上的 CellID 是 3932700003016900608 ，從右往左的第34位和第35位是00繁疤，從右上這個 Cell 想找到希爾伯特曲線的下一個 Cell咖为，由于它目前方向是圖0的方向，所以右上的 Cell 的下一個 Cell 是左上那個 Cell稠腊，那么第34位和第35位就應該是01躁染，變換成01以后，就3932700011606835200架忌，這也就是對應的 CellID吞彤。右數(shù)第34位增加了一個1，對應十進制就增加了 2³³ = 8589934592叹放，算一下兩個 CellID 對應十進制的差值备畦，也正好是這個數(shù)。目前一切都是正確的许昨。

同理可得懂盐，左上的 Cell 的下一個 Cell 就是左下的 Cell，也是相同的第34位和第35位上變成10糕档，對應十進制增加 2³³ = 8589934592莉恼，得到左下的 CellID 為 3932700020196769792。繼續(xù)同理可以得到最后一個 CellID速那，右下的 CellID俐银，為 3932700028786704384。

看到這里端仰，讀者應該對查找同 Level 的兄弟節(jié)點的方法清清楚楚了捶惜。可能有人有疑問了荔烧，要查找父親節(jié)點和孩子節(jié)點和兄弟有啥關系吱七？他們之間的聯(lián)系就在這一章節(jié)開頭說的4個方向圖上面。

回顧一下希爾伯特曲線的生成方式鹤竭，在遞歸生成希爾伯特曲線的時候踊餐，保存了一個 posToIJ 數(shù)組，這個數(shù)組里面記錄著4個方向臀稚。希爾伯特曲線生成的形式和這4個方向是密切相關的吝岭。如果忘記了這部分，還請回看之前筆者的文章分析。

所以同一級的 Level 想查找孩子節(jié)點窜管，首先要找到在這一級中散劫，當前 Cell 所處的位置以及當前 Cell 所在的4個方向中的哪一個方向。這個方向決定了要查找孩子位于下一級或者下幾級的哪個位置幕帆。因為希爾伯特曲線相當于是一個顆四叉樹获搏，每個根節(jié)點有4個孩子，雖然按層可以很輕松的遍歷到孩子所在的層級蜓肆，但是同一個根節(jié)點的孩子有4個，究竟要選哪一個就需要父親節(jié)點的方向一級級的來判斷了谋币。

舉個例子來說明這個問題：

func testS2() {

    latlng := s2.LatLngFromDegrees(29.323773, 107.727194)
    cellID := s2.CellIDFromLatLng(latlng)
    cell := s2.CellFromCellID(cellID) //9279882742634381312

    // cell.Level()
    fmt.Println("latlng = ", latlng)
    fmt.Println("cell level = ", cellID.Level())
    fmt.Printf("cell = %d %b\n", cellID, cellID)
    smallCell := s2.CellFromCellID(cellID.Parent(13))
    fmt.Printf("smallCell level = %d\n", smallCell.Level())
    fmt.Printf("smallCell id = %d / cellID = %d /smallCell(14).Parent = %d (level = %d)/smallCell(15).Parent = %d (level = %d)/cellID(13).Parent = %d (level = %d)/cellID(14).Parent = %d (level = %d)/cellID(15).Parent = %d (level = %d)/ %b \n", smallCell.ID(), cellID, smallCell.ID().Parent(14), (smallCell.ID().Parent(14).Level()), smallCell.ID().Parent(15), (smallCell.ID().Parent(15).Level()), cellID.Parent(13), (cellID.Parent(13)).Level(), cellID.Parent(14), (cellID.Parent(14)).Level(), cellID.Parent(15), (cellID.Parent(15)).Level(), smallCell.ID())

}

讀者考慮一下上述的程序會輸出什么呢仗扬？或者這樣問，同一個節(jié)點蕾额，先找它的 Level 13 的父親節(jié)點早芭，再通過 Level 13 的這個節(jié)點再找它的 Level 15 的父親節(jié)點得到的 Level 15 的節(jié)點，和诅蝶，直接找它的 Level 15 的父親節(jié)點退个，最終結果一樣么？

當然调炬，這里先找 Level 13语盈，再找 Level 15，得到的結果不是 Level 28缰泡，這里不是相加的關系刀荒，結果還是 Level 15 的父親節(jié)點。所以上面兩種方式得到的結果都是 Level 15的棘钞。那么兩種做法得到的結果是一樣的么缠借？讀者可以先猜一猜。

實際得到的結果如下：

latlng =  [29.3237730, 107.7271940]
cell level =  30
cell = 3932700032807325499 11011010010011110000011101011111101111101001011100111100111011
smallCell level = 13
smallCell id = 3932700015901802496 / cellID = 3932700032807325499 /smallCell(14).Parent = 3932700020196769792 (level = 14)/smallCell(15).Parent = 3932700016975544320 (level = 15)/cellID(13).Parent = 3932700015901802496 (level = 13)/cellID(14).Parent = 3932700028786704384 (level = 14)/cellID(15).Parent = 3932700032007929856 (level = 15)/ 11011010010011110000011101010000000000000000000000000000000000

可以看到宜猜，兩種做法得到的結果是不同的泼返。但是究竟哪里不同呢？直接看 CellID 不夠直觀姨拥，那把它們倆畫出來看看绅喉。

可以看到兩者雖然 Level 是相同的，但是位置是不同的叫乌，為何會這樣呢霹疫？原因就是之前說的，四叉樹4個孩子综芥，究竟選擇哪一個丽蝎，是由于父親節(jié)點所在方向決定的。

1. 查找孩子節(jié)點

還是繼續(xù)按照上面程序舉的例子，看看如何查找孩子節(jié)點的屠阻。

我們把 Level 13 - Level 17 的節(jié)點都打印出來红省。

smallCell id = 3932700015901802496 (level = 13)/
smallCell(14).Parent = 3932700020196769792 (level = 14)/ 
smallCell(15).Parent = 3932700016975544320 (level = 15)/
smallCell(16).Parent = 3932700016170237952 (level = 16)/
smallCell(17).Parent = 3932700015968911360 (level = 17)/

畫在圖上，

從 Level 13 是如何變換到 Level 14 的呢国觉？我們知道當前選擇的是圖0的方向吧恃。那么當前 Level 14是圖0 中的2號的位置。

所以從右往左數(shù) 64 - 3 - 1 - 13 * 2 = 34位和35位麻诀，應該分別填上01痕寓，從前往后就是10，對應的就是上圖中的2的位置蝇闭，并且末尾的那個標志位1往后再挪2位呻率。

11011010010011110000011101010000000000000000000000000000000000   13
11011010010011110000011101010100000000000000000000000000000000   14  

即可從 Level 13 變換到 Level 14 。這就是從父親節(jié)點到孩子節(jié)點的變換方法呻引。

同理在看看 Level 15礼仗，Level 16，Level 17 的變換方法逻悠。

前面說過元践，查看孩子節(jié)點的時候需要知道當前節(jié)點的其他3個兄弟節(jié)點的方向。

根據(jù)下圖童谒，Level 14 對應的是圖0单旁，并且當前選擇了2號位置，從下圖中可以看到圖0中的2號位置的下一級的圖是“U”形的饥伊，說明還是圖0的樣子慎恒。

所以可以知道當前 Level 14 所處的方向依舊是圖0 。按照方向標識在圖上撵渡，如下圖融柬。

所以如果還是選擇上圖中0號的位置，那么 Level 15 的從右往左數(shù) 64 - 3 - 1 - 14 * 2 = 32位和第33位上填入00 趋距。

11011010010011110000011101010100000000000000000000000000000000   14 
11011010010011110000011101010001000000000000000000000000000000   15

由于選擇了圖0的0號位置粒氧，所以下一級的方向對應的是圖1 。(注意整個圖的方向是向左旋轉了90°) 节腐。

圖1中繼續(xù)選擇0號的位置外盯，所以 Level 16 的從右往左數(shù) 64 - 3 - 1 - 15 * 2 = 30位和31位填上00 。那么就可以得到 Level 16 翼雀。

11011010010011110000011101010001000000000000000000000000000000   15
11011010010011110000011101010000010000000000000000000000000000   16

由于選擇了圖1的0號位置饱苟，所以下一級的方向對應的是還是圖0。

圖0中繼續(xù)選擇0號的位置狼渊，所以 Level 17 的從右往左數(shù) 64 - 3 - 1 - 16 * 2 = 28位和第29位填上00 箱熬。那么就可以得到 Level 17 类垦。

11011010010011110000011101010000010000000000000000000000000000   16
11011010010011110000011101010000000100000000000000000000000000   17

同理，其他的孩子節(jié)點都可以按照這個方法推算得到城须。

從 Level 13 開始蚤认，由于 Level 13 對應的方向是圖0，當前選擇3號位置糕伐，就可以得到 Level 14砰琢，所以 Level 14 的末尾標志位1前面的兩位是 11 。于是就可以從 Level 13 變換到 Level 14 良瞧。

11011010010011110000011101010000000000000000000000000000000000   13 3932700015901802496
11011010010011110000011101011100000000000000000000000000000000   14 3932700028786704384

由于圖0選擇了3號位置陪汽，那么 Level 14 的方向就是圖3 。

Level 14 對應的方向是圖3褥蚯，當前選擇3號位置挚冤，就可以得到 Level 15，所以 Level 15 的末尾標志位1前面的兩位是 11 遵岩。于是就可以從 Level 14 變換到 Level 15 你辣。

11011010010011110000011101011100000000000000000000000000000000   14 3932700028786704384
11011010010011110000011101011111000000000000000000000000000000   15 3932700032007929856

由于圖3選擇了3號位置巡通，那么 Level 15 的方向就是圖0尘执。

Level 15 對應的方向是圖0，當前選擇0號位置宴凉，就可以得到 Level 16誊锭，所以 Level 16 的末尾標志位1前面的兩位是 00 。于是就可以從 Level 15 變換到 Level 16 弥锄。

11011010010011110000011101011111000000000000000000000000000000   15 3932700032007929856
11011010010011110000011101011110010000000000000000000000000000   16 3932700031202623488

由于圖0選擇了0號位置丧靡，那么 Level 16 的方向就是圖1。

Level 16 對應的方向是圖1籽暇，當前選擇1號位置温治，就可以得到 Level 17，所以 Level 17 的末尾標志位1前面的兩位是 01 戒悠。于是就可以從 Level 16 變換到 Level 17 熬荆。

11011010010011110000011101011110010000000000000000000000000000   16 3932700031202623488
11011010010011110000011101011110001100000000000000000000000000   17 3932700031135514624

由于圖1選擇了1號位置，那么 Level 18 的方向還是圖1绸狐。

到此讀者應該對查找 CellID 孩子節(jié)點的流程了然于心了卤恳。在 Google S2 中，查找孩子節(jié)點的具體實現(xiàn)代碼如下寒矿。

func (ci CellID) Children() [4]CellID {
    var ch [4]CellID
    lsb := CellID(ci.lsb())
    ch[0] = ci - lsb + lsb>>2
    lsb >>= 1
    ch[1] = ch[0] + lsb
    ch[2] = ch[1] + lsb
    ch[3] = ch[2] + lsb
    return ch
}

現(xiàn)在在來看這段代碼應該毫無壓力了吧突琳。

這里比較重要的位運算的操作就是 lsb 了。從名字上其實也可以知道它是做什么的符相。

// lsb 返回最低有效位
func (ci CellID) lsb() uint64 { return uint64(ci) & -uint64(ci) }

這里需要注意的一點就是負數(shù)的存儲方式是以原碼的補碼拆融，即符號位不變，每位取反再加1 。

舉個例子冠息，Level 16 的某個 CellID 如下：

11011010010011110000011101011110010000000000000000000000000000   16 3932700031202623488

對它進行 lsb 計算：

得到的結果就是最低有效位為1挪凑，其他每位都為0 。

ch[0] = ci - lsb + lsb>>2

這一行實際是把 Level 對應的下一級 Level 的末尾標志位1移動到位逛艰。即往后挪2位躏碳。并且標志位前面2位都為0，所以這步操作完成以后就是0號的孩子散怖。

0號孩子找到以后接下來就很好辦了菇绵。lsb 往右移動一位以后，不斷的加上這個值镇眷，就可以得到剩下的4個孩子了咬最。如下圖：

這樣就可以得到4個孩子，上面這一小段程序挺簡單的欠动，比前面從地圖上解釋的更簡單永乌，原因是因為沒有可視化的4個孩子的相互位置關系，這個關系需要從當前所在的方向來決定具伍。前面地圖上也一再強調每一級的方向位置關系也是為了可視化展現(xiàn)在地圖上是符合希爾伯特曲線的相對位置翅雏。

2. 判斷是否是葉子節(jié)點

如果對 CellID 的數(shù)據(jù)結構很了解，這個判斷就很簡單了人芽。

func (ci CellID) IsLeaf() bool { return uint64(ci)&1 != 0 }

由于 CellID 是64位的望几，末尾有一個1的標志位，如果這個標志位到了最后一位萤厅，那么就肯定是葉子節(jié)點了橄抹，也就是 Level 30 的 Cell。

3. 查找當前孩子位置關系

在前面講解查找孩子節(jié)點的時候惕味，由于是四叉樹楼誓，每個父親下面對應4個孩子，00名挥，01疟羹，10，11躺同，所以判斷4個孩子之間相對的位置關系只需要判斷這兩個二進制位就可以了阁猜。

func (ci CellID) ChildPosition(level int) int {
    return int(uint64(ci)>>uint64(2*(maxLevel-level)+1)) & 3
}

上面這個函數(shù)入?yún)⑹且粋€父親節(jié)點的 Level 等級，返回的是這個父親節(jié)點下面孩子節(jié)點的位置信息蹋艺。即是 00剃袍，01，10捎谨，11 中的一個民效。

4. 查找父親節(jié)點

在 Google S2 中憔维，由于默認生成出來的 Cell 就是 Level 30 的，也就是 Level 最低的畏邢，位于樹的最下層的葉子節(jié)點业扒。所以生成 Level 比較低的 Cell 必須只能查找父親節(jié)點。

由于前面講解了如何查找孩子節(jié)點舒萎，查找父親節(jié)點就是逆向的過程程储。

func lsbForLevel(level int) uint64 { return 1 << uint64(2*(maxLevel-level)) }

第一步就是先找到最右邊的標志位，它決定了 Level 的值臂寝。

(uint64(ci) & -lsb)

第二步是保留住標志位前面所有的二進制位上的值章鲤。這里對第一步的 lsb 的相反數(shù)進行按位與操作就可以實現(xiàn)。lsb 的相反數(shù)其實就是 lsb 低位往左的高位都為1 咆贬，相當于一個掩碼败徊。

最后一步將標志位1放好就可以了。

func (ci CellID) Parent(level int) CellID {
    lsb := lsbForLevel(level)
    return CellID((uint64(ci) & -lsb) | lsb)
}

以上就是查找父親節(jié)點的具體實現(xiàn)掏缎。

二. LCA 查找最近公共祖先

關于 CellID 的計算皱蹦，還有很關鍵的一部分就是查找最近公共祖先的問題。問題背景：給定一棵四叉樹中任意兩個 Level 的 CellID 眷蜈，如何查詢兩者的最近公共祖先沪哺。

由 CellID 的數(shù)據(jù)結構我們知道，想查找兩個 Level 的最近公共祖先的問題可以轉化為從左往右查找兩個二進制串最長公共序列端蛆，最長的即是從根節(jié)點開始最遠的公共祖先凤粗，也就是最近公共祖先酥泛。

那么現(xiàn)在問題就轉換成從左往右找到第一個不相同的二進制位今豆，或者從右往左找到最后一個不相同的二進制位。

查找過程中存在一個特殊情況柔袁，那就是要查找公共祖先的兩個節(jié)點本身就在一個分支上呆躲，即其中一個 CellID 本來就是另外一個 CellID 的祖先，那么他們倆的公共祖先就直接是 CellID 大的那個捶索。

那么到此就可以確定出接下來查找的流程插掂。

第一步，先對兩個 CellID 進行異或腥例，找到不同的二進制位分別在那些位置上辅甥。

    bits := uint64(ci ^ other)

第二步，判斷是否存在特殊情況：兩個存在祖先關系燎竖。

    if bits < ci.lsb() {
        bits = ci.lsb()
    }
    if bits < other.lsb() {
        bits = other.lsb()
    }

第三步璃弄，查找左邊最高位不同的位置。

func findMSBSetNonZero64(bits uint64) int {
    val := []uint64{0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000, 0xFFFFFFFF00000000}
    shift := []uint64{1, 2, 4, 8, 16, 32}
    var msbPos uint64
    for i := 5; i >= 0; i-- {
        if bits&val[i] != 0 {
            bits >>= shift[i]
            msbPos |= shift[i]
        }
    }
    return int(msbPos)
}

由于 CellID 是 64 位的构回，所以兩者不同的位數(shù)可能的范圍是 [0夏块，63]疏咐。分別準備6種掩碼，對應的分別是0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000, 0xFFFFFFFF00000000脐供。如下圖浑塞。

查找的過程就是利用的二分的思想。64位先查找高位32位政己，如果對高32位的掩碼進行按位與運算以后結果不為0酌壕，那么就說明高32位是存在不相同的位數(shù)的，那么最終結果 msbPos 加上32位歇由，并把數(shù)字右移32位仅孩。因為高32位存在不同的數(shù)，由于我們需要求最左邊的印蓖，所以低32位就可以直接舍去了辽慕，直接右移去掉。

同理赦肃，繼續(xù)二分溅蛉，16位，8位他宛，4位船侧，2位，1位厅各，這樣循環(huán)完镜撩，就一定能把最左邊的不同的位數(shù)找到，并且結果位即為 msbPos队塘。

第四步袁梗，判斷 msbPos 的合法性，并輸出最終結果憔古。

如果 msbPos 比60還要大遮怜，那么就是非法值，直接返回 false 即可鸿市。

    msbPos := findMSBSetNonZero64(bits)
    if msbPos > 60 {
        return 0, false
    }
    return (60 - msbPos) >> 1, true

最終輸出的為最近公共祖先的 Level 值锯梁，所以 60 - msbPos 以后還需要再除以2 。

完整的算法實現(xiàn)如下：

func (ci CellID) CommonAncestorLevel(other CellID) (level int, ok bool) {
    bits := uint64(ci ^ other)
    if bits < ci.lsb() {
        bits = ci.lsb()
    }
    if bits < other.lsb() {
        bits = other.lsb()
    }

    msbPos := findMSBSetNonZero64(bits)
    if msbPos > 60 {
        return 0, false
    }
    return (60 - msbPos) >> 1, true
}

舉個例子：

在上面的例子中焰情，我們挑選不存在祖先關系的兩個 Level 的 CellID陌凳。

11011010010011110000011101010000000100000000000000000000000000   17
11011010010011110000011101011111000000000000000000000000000000   15

如果從這串二進制里面直接找最近公共祖先，一定可以發(fā)現(xiàn)内舟，從左往右最長的公共二進制串是：

1101101001001111000001110101

那么他們倆的最近公共祖先就是：

11011010010011110000011101010000000000000000000000000000000000

對應的 Level 是13合敦，CellID 是 3932700015901802496。

空間搜索系列文章：

空間搜索系列文章：

如何理解 n 維空間和 n 維時空
高效的多維空間點索引算法 — Geohash 和 Google S2
Google S2 中的 CellID 是如何生成的 谒获？
Google S2 中的四叉樹求 LCA 最近公共祖先
神奇的德布魯因序列
四叉樹上如何求希爾伯特曲線的鄰居 蛤肌？

GitHub Repo：Halfrost-Field

Follow: halfrost · GitHub

Source: https://halfrost.com/go_s2_lowest_common_ancestor/