前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >如何用简单的位操作实现高级算法

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

作者头像
青南
发布2020-05-21 08:50:06
6850
发布2020-05-21 08:50:06
举报
文章被收录于专栏:未闻Code

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

代码语言:txt
复制
7 * 100000 + 34 * 1000 + 562 = 734562

那么在二进制的世界中,我们应该如何把三个二进制数:11110拼接为11110呢?这就涉及到移位的操作了。

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

代码语言:txt
复制
1 << 3

结果如下图所示:

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

代码语言:txt
复制
bin(1 << 3)

运行结果如下图所示:

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

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

代码语言:txt
复制
1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0

如下图所示:

于是,如果我们把10011进行或操作,得到的结果是什么呢?我们看一下:

所以,如果要把11110拼接成11110,我们只需要通过如下代码完成:

代码语言:txt
复制
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)编码的基本原理了。其中字符到二进制的对应关系是通过字符出现的概率来算的,出现概率越高,它对应的二进制数就越短,这样就可以保证转换后的总二进制数最短。

如果大家对如何生成这个对应码表有兴趣,请在文章下面留言。超过一定量,我再写篇文章讲讲如何转换。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-05-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 未闻Code 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
文件存储
文件存储(Cloud File Storage,CFS)为您提供安全可靠、可扩展的共享文件存储服务。文件存储可与腾讯云服务器、容器服务、批量计算等服务搭配使用,为多个计算节点提供容量和性能可弹性扩展的高性能共享存储。腾讯云文件存储的管理界面简单、易使用,可实现对现有应用的无缝集成;按实际用量付费,为您节约成本,简化 IT 运维工作。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档