我試圖計(jì)算出我可以用 5 個(gè) base64 字符、6 個(gè)字符等編碼的無(wú)符號(hào)整數(shù)的估計(jì)值。通過(guò)編程方法我發(fā)現(xiàn)我可以編碼2^28 - 1 = 268,435,455有 6 個(gè)字符和2^35 - 1 = 34,359,738,368有 7 個(gè)字符。（-1 因?yàn)槲覐?uint 1 開始）不過(guò)，我正在努力概括這一點(diǎn)，因?yàn)槲視?huì)假設(shè)它從 開始，2^8 = 256但我不明白我是如何結(jié)束的28和35。這是我在 Go 中的實(shí)現(xiàn)func Shorten(num uint64) string { buf := make([]byte, binary.MaxVarintLen64) n := binary.PutUvarint(buf, num) b := buf[:n] encoded := base64.URLEncoding.EncodeToString(b) return strings.Replace(encoded, "=", "", -1)}還0 -> AA128 -> gAE16384 -> gIAB2097152 -> gICAAQ268435456 -> gICAgAE所以看起來(lái)它以 7 個(gè)增量上升：2^7、2^14、2^21 等，但為什么是 7？
1 回答
小怪獸愛吃肉
TA貢獻(xiàn)1852條經(jīng)驗(yàn) 獲得超1個(gè)贊
一個(gè)字節(jié)是 8 位，因此有 256 個(gè)可能的值。Base 64 使用 64 個(gè)不同的字符進(jìn)行編碼，因此使用 6 位。那么 6 位可以容納多少個(gè) 8 位對(duì)象？如果四舍五入則為 0，否則為 3/4。當(dāng)您開始談?wù)搶?duì)整數(shù)進(jìn)行編碼時(shí)，您的數(shù)字似乎沒(méi)有意義。您是在談?wù)撚?ascii 編寫的整數(shù)嗎？有 6 個(gè) base64 字符，你有 36 位可以玩，所以如果你談?wù)摱M(jìn)制 32 位無(wú)符號(hào)整數(shù)，你可以一次編碼一個(gè)，但你可以編碼任何你想要的 2**32 種不同的可能性，然后4個(gè)浪費(fèi)位。使用 ascii 你會(huì)有 4 個(gè)字符，所以它有 10000 種不同的可能性（0 到 9999）。
您會(huì)得到意想不到的結(jié)果，因?yàn)槟褂玫氖俏淳幋a為常規(guī)二進(jìn)制整數(shù)的 go varint。一些 ipython 輸出給你：
In [22]: base64.b64encode((128).to_bytes(1,'little'))
Out[22]: b'gA=='
因?yàn)?128 可以編碼為單個(gè) 8 位字節(jié)，所以它只有 2 個(gè)字符和一些填充?？纯催@個(gè)：
In [3]: base64.b64decode('gAE=')
Out[3]: b'\x80\x01'
In [4]: int.from_bytes(_,'little')
Out[4]: 384
因此，正如您所看到的，PutUVarint 不只是編碼一個(gè)可變長(zhǎng)度的整數(shù)，它還在編碼一個(gè)可變整數(shù)，即它的編碼方式可以在事先不知道它的大小的情況下進(jìn)行解碼。如果您查看varint go 模塊的源代碼它描述了這個(gè)過(guò)程。Go 使用每個(gè)字節(jié)的 7 位來(lái)保存實(shí)際的整數(shù)二進(jìn)制數(shù)據(jù)，最高有效位是一個(gè)標(biāo)志，表示是否還有更多數(shù)據(jù)尚未到來(lái)。128 只是一個(gè)字節(jié)集的最高有效位。所以基本上你根據(jù)完成這項(xiàng)任務(wù)的方式進(jìn)行了兩次編碼。如果您有一個(gè)給定的整數(shù)將其編碼為 var int，則您需要整數(shù)使用 *8/7 來(lái)存儲(chǔ)該值的字節(jié)數(shù)，然后您對(duì)該結(jié)果進(jìn)行 base64 編碼，因此您需要該值 *8/6 來(lái)存儲(chǔ)它。根據(jù)你對(duì) base64 的處理方式，你可能可以確定你正在玩多少字節(jié)而無(wú)需求助于 go varints 然后計(jì)算將只是 8/6 轉(zhuǎn)換（這是 4/3 我只是將它留在位中以更緊密地匹配 varint 過(guò)程。）
添加回答
舉報(bào)
0/150
提交
取消