某一天想起之前和群友讨论过的压缩 base64 编码的事，我把一个图像转 base64 编码后用 zip 压缩文本文件，得到的文件比原图差不多大小，我又想起了大二学过的哈夫曼编码，那玩意也是用来压缩文本的。于是我有了一个想法，把图片转 base64 后用哈夫曼编码压缩一遍再和原图比较大小。
说干就干。要实现哈夫曼编码的位操作，首先得实现一个位数组。我也懒得找什么工具类了，直接自己搓一个，实现 push 和 pop 方法就行。这一篇就讲这个吧。
一开始先定义结构体：
type bit8 struct {
len byte
val byte
}
type BitList struct {
Size int
arr []bit8
}
后来写着写着突然开窍了，反正是存的二进制流，用 64 位的 int64 感觉更好，能减少数组重分配的问题，代价是 int64 的大小是 byte 的 8 倍，对于少量元素来说空间的冗余有点多。
总之是改了。
type bit64 struct {
len byte
val uint64
}
type BitList struct {
Size int
arr []bit64
}
push 方法写的差不多了，测试也通过了。突然想到还得实现一个方法把这些数据转成 byte 数组，方法名就叫 DumpBytes 吧，突然有点后悔改成 int64 存储数据了......
实现了 index 方法，先通过除法运算来定位要找的是哪个 int64，再通过位运算来截取对应的位置。这里不得不吐槽一下 go 语言的位运算了，java 的位运算有一个 >>> 运算符，表示无视符号位右移，但是 go 语言没有这玩意，进行右移是不得不考虑符号位的问题。所以我想了一个绕了一圈的方法，就是右移后再根据剩下的长度（记为 n）和 pow(2, n) - 1 进行与运算，得到的结果就是无视符号位右移的结果了。
用 byte 来举个例子 假如有一个 11001100 的 byte，右移 2 位后变成了 11110011，可以看到符号位也移了过来。此时移位后剩下的部分是后 6 位，我只需要将 pow(2, 6) - 1，也就是 00111111 和 11110011 进行与运算，就能得到 00110011，正是无符号右移 2 位的结果。
正准备实现 stringer 接口的时候，突然想到给 int64 套一个结构体真的有必要嘛，最后一个 int64 的有效长度可以算出来的。最烦这种写到一大半才发现前期的设计问题。算了，以后再优化咯。
然后开始捣鼓 DumpBytes 方法，突然想到一个妙招，用 go 语言里 const 变量的 iota 关键字生成一些“int64 的片段”（就是把 int64 按 8 位分开，每个区域都是 1，比如说 00 ... 56 个0 ... 011111111 是第一个片段，00 ... 48 个 0 ... 01111111100000000 是第二个片段，以此类推），然后用这些片段分别和原来的 int64 做与运算得到 byte，至于最后一位没有占满完整的 int64，不好用切割法，所以就直接调用 index 的那个方法来做了。其实一开始只在调用 index 方法，写到一半突然想了下，数据量大的时侯就算 index 是 O(1) 时间复杂度还是会很慢。于是就想出了这个方法，几乎比循环调用 index 方法快了 8 倍。
2022-07-24