如何用简单的位操作实现高级算法

后台回复关键字 “黑魔法”，即可获取明哥整理的《Python黑魔法指南》

我们知道，在十进制的世界里面，如果我想把3个数字：7，34，562拼接成一个长整数：734562，一般我们会这样做：

7 * 100000 + 34 * 1000 + 562 = 734562


那么在二进制的世界中，我们应该如何把三个二进制数：1、11、10拼接为11110呢？这就涉及到移位的操作了。

在 Python 中，移位操作的符号是<<，例如我们要把1左移3位，就写为：

1 << 3

结果如下图所示：

这个数字8看起来不够直观，我们把它转成二进制看看：

bin(1 << 3)


运行结果如下图所示：

所以， 1 << 3对应二进制1000。同理，1 << n对应的二进制是1后面跟 n 个零。

那么第二个问题，现在我已经有了一个二进制数100，我怎么把另一个二进制11【拼】上去，形成111呢？这个时候，我们就可以使用或操作。在 Python 中，或操作的符号是一根竖线|。或操作满足，两个操作数中，只要有一个数是1，那么结果就是1：

1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0

如下图所示：

于是，如果我们把100与11进行或操作，得到的结果是什么呢？我们看一下：

所以，如果要把1、11、10拼接成11110，我们只需要通过如下代码完成：

bin(1 << (0b11).bit_length() | 0b11 << 0b10.bit_length() | 0b10)


运行效果如下图所示：

好了，理论讲完了。我们来看看上面这个理论可以用了干什么事情。

感谢 KSHMR 提供图片

现在我给你一个汉字到二进制数的对应表：

字符	二进制
发	00
黑	010
化	011
肥	10
灰	110
会	1110
挥	11110
;	11111

那么，对于绕口令：黑化肥发灰会挥发；灰化肥挥发会发灰，它对应的二进制数就是01001110001101110111100011111110011101111000111000110

我们在 Python 里面，看看这个二进制数对应的十进制数是多少：

我们来看看这个数字，它占用的储存空间是多少：

只占用32 byte 的内存（sys.getsizeof 返回的数据会比实际占用的空间大）。

再来看看原来绕口令字符串所占用的空间：

通过这样一个二进制的映射，我们把字符串的大小缩减为原来的30%。压缩率高达70%！

但不要忘记，如果要还原数据，我们还需要上面的汉字与二进制数的对应表。所以，需要压缩的数据越大，重复率越高，那么压缩效率就越好。

以上就是霍夫曼(Huffman)编码的基本原理了。其中字符到二进制的对应关系是通过字符出现的概率来算的，出现概率越高，它对应的二进制数就越短，这样就可以保证转换后的总二进制数最短。