在python计数非零位的快速方法 [英] fast way of counting non-zero bits in python

问题描述

我需要一个快速的方法来计算Python中的一个整数位的数量。
我目前的解决方案是

 斌（N）.Count之间（1）
 

但我想知道是否有这样做的任何更快的方法？

PS：（我再presenting一个大的二维二进制数组作为一个数字燎名单和做位运算，而带来的时间缩短从数小时到数分钟，现在我想摆脱那些。额外分钟。

编辑：
1.它必须是在Python 2.7或2.6

和小型数字不管那么多了，因为这不会是一个明显的瓶颈优化，但我确实在一些地方有10 000 +位号

例如，这是一个2000位情况：

<$p$p><$c$c>12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L

解决方案

有关任意长度的整数，斌（N）.Count之间（1）是最快的我能找到的纯Python。

我试图适应奥斯卡和亚当的解决方案来处理64位和32位数据块的整数，分别为。均高于斌（N）.Count之间的慢至少十倍（1）（32位版本又花了大约一半的时间）。

在另一方面， gmpy popcount（）花了大约1/20的斌（N）.Count之间的时间（1）。所以，如果你可以安装gmpy，使用它。

I need a fast way to count the number of bits in an integer in python. My current solutions is

bin(n).count("1")

but I am wondering if there is any faster way of doing this?

PS: (i am representing a big 2D binary array as a singe list of numbers and doing bitwise operations, and that brings the time down from hours to minutes. and now i would like to get rid of those extra minutes.

Edit: 1. it has to be in python 2.7 or 2.6

and optimizing for small numbers does not matter that much since that would not be a clear bottle neck, but I do have numbers with 10 000 + bits at some places

for example this is a 2000 bit case:

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L

解决方案

For arbitrary-length integers, bin(n).count("1") is the fastest I could find in pure Python.

I tried adapting Óscar's and Adam's solutions to process the integer in 64-bit and 32-bit chunks, respectively. Both were at least ten times slower than bin(n).count("1") (the 32-bit version took about half again as much time).

On the other hand, gmpy popcount() took about 1/20th of the time of bin(n).count("1"). So if you can install gmpy, use that.

这篇关于在python计数非零位的快速方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！