2 ms·
Bit Counts in Python, Erlang and Clojure
- RiderOfGiraffes 16y agoRather than running down the int (or long) one bit at a time, checking to see if that bit is on and counting those that are, here's a routine that counts the number of bits in an int or long by folding it up half-length at a time. If you assume that operations on the longs are unit time (which if they're long enough they aren't, but it'll do) this runs in logarithmic time (in number of bits) rather than linear time. Your job, should you decide to accept it, is to figure out how it works. #!/usr/bin/python from sys import argv x = long(argv[1]) def count_bits(x) n_bits = 1 limit = 1 << n_bits mask = 1 while limit <= x: n_bits *= 2 limit = 1L << n_bits mask = mask*(1+limit) d,shift = x,1 div,mul = 5,3 while n_bits > 1: d = ((d>>shift) & mask) + (d & mask) shift *= 2 mask = mask/div * mul mul, div = div, (div-1)**2 + 1 n_bits /= 2 return d print x, count_bits(x) Here's a simpler version for just 8 bit bytes: def count_bits(x): x = ((x>>1) & 0x55) + (x & 0x55) x = ((x>>2) & 0x33) + (x & 0x33) return ((x>>4) & 0x0f) + (x & 0x0f) That's easy to extend for 16, 32 or 64 bits.