問題描述
我需要一種快速的方法來計算 python 中整數(shù)的位數(shù).我目前的解決方案是
bin(n).count("1")但我想知道是否有更快的方法來做到這一點?
PS:(我將一個大的二維二進制數(shù)組表示為一個數(shù)字列表并進行按位運算，這將時間從幾小時縮短到幾分鐘.現(xiàn)在我想擺脫那些額外的分鐘.
1. 它必須在 python 2.7 或 2.6 中
優(yōu)化小數(shù)字并不重要，因為這不是一個明顯的瓶頸，但我確實在某些地方有 10 000 + 位的數(shù)字
例如這是一個 2000 位的情況:
<預> <代碼> 12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L對于任意長度的整數(shù)，bin(n).count("1") 是我在純 Python 中能找到的最快的.
我嘗試采用 óscar 和 Adam 的解決方案分別處理 64 位和 32 位塊中的整數(shù).兩者都比 bin(n).count("1") 慢了至少十倍(32 位版本又花了大約一半的時間).
另一方面，gmpy popcount()大約是 bin(n).count("1") 時間的 1/20.因此，如果您可以安裝 gmpy，請使用它.
要回答評論中的問題，對于字節(jié)，我會使用查找表.您可以在運行時生成它:
counts = bytes(bin(x).count("1") for x in range(256)) # py2: 使用 bytearray或者直接定義它:
計數(shù) = (b'x00x01x01x02x01x02x02x03x01x02x02x03x02x03x03x04'b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'b'x04x05x05x06x05x06x06x07x05x06x06x07x06x07x07x08')然后是 counts[x] 得到 x 中 1 的位數(shù)，其中 0 ≤ x ≤ 255.
I need a fast way to count the number of bits in an integer in python. My current solution 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 single 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 bottleneck, 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.
To answer a question in the comments, for bytes I'd use a lookup table. You can generate it at runtime:
counts = bytes(bin(x).count("1") for x in range(256)) # py2: use bytearray
Or just define it literally:
counts = (b'x00x01x01x02x01x02x02x03x01x02x02x03x02x03x03x04'
b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'
b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'
b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'
b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'
b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'
b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'
b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'
b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'
b'x04x05x05x06x05x06x06x07x05x06x06x07x06x07x07x08')
Then it's counts[x] to get the number of 1 bits in x where 0 ≤ x ≤ 255.
這篇關于以正整數(shù)計算非零位的快速方法的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網(wǎng)！