How can I get the number of "1"s in the binary representation of a number without actually converting and counting ?
e.g.
def number_of_ones(n):
# do something
# I want to MAKE this FASTER (computationally less complex).
c = 0
while n:
c += n%2
n /= 2
return c
>>> number_of_ones(5)
2
>>> number_of_ones(4)
1
I'm not a python programmer, but hopefully it will be enough for you to follow.
c = 0
while n:
c += 1
n &= n - 1
return c
While a little obscure, it's primary advantage is speed and simplicity. The while loop is only iterated once for every bit set to 1 in n.
You cannot make this computationally less complex. It will be O(n) the number of bits, or, as the answer with the & trick showed, O(n) the number of bits set to 1; but unless all of the numbers you are using are a special case, the latter should on average be n/2, so both of those O(n) numbers are the same.
And the lookup-table trick, of course, is actually doing nothing for the computational complexity; it's just paying for time with space but without changing the underlying economics, which are that you must examine each bit once somehow and there is no way around that. You cannot, logically, answer a question about the bits in the number without inspecting each of them.
Now, I suppose I'm being a bit sloppy since many of these examples are actually O(n^2) since in Python you have to examine the whole number at once time, so with a Python long integer of, say, 100 bytes, a + or an & or a / operation will look at each byte at least once, and that will happen over and over until the number is reduced to zero (in the schemes outlined above), so these, again, are really O(n^2) operations. I am not sure Python will allow a true O(n) solution here.
Anyway: if you were really asking about computational complexity, which specifically means big-O analysis, that's your answer. :-)
IMO, a good approach would be to use a look-up table - create a dictionary which converts bytes to number of 1's (you can use the code you posted to generate it, it would only need to run once), and then use something like this:
def number_of_ones(n):
sum = 0
while n != 0:
sum += lookup_table[n & 0xff]
n >>= 8
return sum
I believe this is a fairly good trade-off between space and running-time.
If you want to do it in a single line, you could use:
sum( [x&(1<<i)>0 for i in range(32)] )
https://en.wikipedia.org/wiki/Hamming_weight.
Solution with O(log(n)), n is bit length
m1 = 0x5555555555555555 #binary: 0101...
m2 = 0x3333333333333333 #binary: 00110011..
m4 = 0x0f0f0f0f0f0f0f0f #binary: 4 zeros, 4 ones ...
m8 = 0x00ff00ff00ff00ff #binary: 8 zeros, 8 ones ...
m16 = 0x0000ffff0000ffff #binary: 16 zeros, 16 ones ...
m32 = 0x00000000ffffffff #binary: 32 zeros, 32 ones
h01 = 0x0101010101010101 #the sum of 256 to the power of 0,1,2,3...
def hammingWeight(x: int) -> int:
x -= (x>>1)&m1
x = (x&m2) + ((x>>2)&m2)
x = (x+(x>>4))&m4
return ((x*h01)>>56)&0x7f
And in python 3.10, the int type will have a bit_count() method
Here:
def bitCount(int_no):
c = 0
while(int_no):
int_no &= (int_no - 1)
c += 1
return c
This might be an old and efficient way to do this... originally implementated in C (Algo has a name I can't remember). It works fine for me hope it does for any other person
If you're actually concerned about speed, code it up in C (see this question for how), and interface with the C implementation using something like ctypes.
p = lambda n:n and 1+p(n&(n-1))
This uses short-circuiting and recursion, when n is greater than 0, it switches to calculate 1+p(n&(n-1)) where p(n&(n-1)) is called and so on, when n is 0 it returns 0. Complexity being O(n) since it runs the number of times the number of ones exist in the binary.
Example: p(9) = 1+p(8) = 1+1+p(0) = 1+1+0=2
I came here today to check the state of the art.
This is a subject come up from time to time, modern CPUs have a the population count algorithm. This is useful to calculate Bit Error Rate in certain communications application. This is the hamming weight, related to Hamming distance, scipy has an implementation but it works with arrays, not with the binary representation of numbers. For fixed size computation, e.g numpy arrays, the fastest approach I know is the method this answer, however the mentioned answer, I am calling this the divide and conquer method. In the general case the divide and conquer has complexity O(log(n)) instead of O(n). The accepted answer is really good for most cases, and even better in languages such as C where you could simply take ((*char)bits)[i], instead of shifting the number.
Here I give a general implementation for the divide and conquer approach where the masks are computed dynamically depending on the size of the input number.
def dq_number_of_ones(n):
nb = 1
while n >> nb:
nb *= 2
t = (1 << nb) - 1
masks = []
while nb > 1:
nb //= 2
t ^= t >> nb
masks.append(t)
t = n
s = 1
for tm in masks[::-1]:
tm = masks.pop()
t = ((tm & t) >> s) + ((tm >> s) & t)
s *= 2
return t
And for completenes here the OP's method and the accepted lookup table method
def number_of_ones(n):
# do something
# I want to MAKE this FASTER (computationally less complex).
c = 0
while n:
c += n%2
n //= 2
return c
lookup_table = [number_of_ones(i) for i in range(256)]
def lt_number_of_ones(n):
sum = 0
while n != 0:
sum += lookup_table[n & 0xff]
n >>= 8
return sum
A practical comparison of the two
import time
import matplotlib.pyplot as plt
x = []
t1 = []
t2 = []
t3 = []
for i in range(3,8000,20):
y = i**i
if i < 1000:
time.sleep(0.0001)
t0 = time.time()
w1 = number_of_ones(y)
t1.append(time.time() - t0)
else:
t1.append(np.nan)
time.sleep(0.0001)
t0 = time.time()
w2 = dq_number_of_ones(y)
t2.append(time.time() - t0)
time.sleep(0.0001)
t0 = time.time()
_ = lt_number_of_ones(y)
t3.append(time.time() - t0)
time.sleep(0.0001)
x.append(i)
plt.figure(figsize=(12, 4))
plt.subplot(121)
plt.plot(x, t1)
plt.plot(x, t2)
plt.plot(x, t3)
plt.xlim([10,None])
plt.title('Linear scale')
plt.ylabel('time to count bits in $x^x$')
plt.subplot(122)
plt.loglog(x, t1)
plt.loglog(x, t2)
plt.loglog(x, t3)
plt.xlim([10,None])
plt.title('Log scale')
plt.legend(['direct counting', 'lookup table', 'divide and conquer'])
