为了账号安全,请及时绑定邮箱和手机立即绑定

快速计数正整数中的非零位的方法

快速计数正整数中的非零位的方法

蛊毒传说 2019-11-12 14:40:58
我需要一种快速的方法来计算python中整数的位数。我当前的解决方案是bin(n).count("1")但我想知道是否有更快的方法?PS :(我将一个大型2D二进制数组表示为单个数字列表并进行按位运算,这将时间从几小时缩短为几分钟。现在,我想摆脱那些多余的分钟。编辑:1.它必须在python 2.7或2.6中对小数字进行优化并不重要,因为这并不是一个明显的瓶颈,但是在某些地方,我确实拥有1万+位的数字例如,这是一个2000位的情况:12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L
查看完整描述

3 回答

?
人到中年有点甜

TA贡献1895条经验 获得超7个赞

对于任意长度的整数,这bin(n).count("1")是我在纯Python中可以找到的最快的速度。


我尝试修改Óscar和Adam的解决方案以分别处理64位和32位块中的整数。两者都比至少慢了十倍bin(n).count("1")(32位版本花了大约一半的时间)。


另一方面,gmpy popcount()大约花费了时间的1/20 bin(n).count("1")。因此,如果可以安装gmpy,请使用它。


为了回答注释中的问题,对于字节,我将使用查找表。您可以在运行时生成它:


counts = bytes(bin(x).count("1") for x in range(256))  # py2: use bytearray

或者只是从字面上定义它:


counts = (b'\x00\x01\x01\x02\x01\x02\x02\x03\x01\x02\x02\x03\x02\x03\x03\x04'

          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'

          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'

          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'

          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'

          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'

          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'

          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'

          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'

          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'

          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'

          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'

          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'

          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'

          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'

          b'\x04\x05\x05\x06\x05\x06\x06\x07\x05\x06\x06\x07\x06\x07\x07\x08')

然后counts[x]得到0≤x≤255处的1位数目x。


查看完整回答
反对 回复 2019-11-12
  • 3 回答
  • 0 关注
  • 581 浏览
慕课专栏
更多

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信