jak <nos...@please.ty> writes:
Oscar Benjamin ha scritto:
...
If we now use the function being discussed:
powers_of_2_in(n)
(63, 1)
we can see that the bit_count() method had to do 63 iterations to count
the bits....
I certainly hope that the bit_count method doesn't count bits by
iterating over them one-by-one. You can count bits _much_ faster than
that.
You can count the bits in a 62-bit number as follows:
def bit_count_62(n):
n = (n - ((n >> 1) & 0o333333333333333333333)
- ((n >> 2) & 0o111111111111111111111))
n = ( (n & 0o307070707070707070707)
+ ((n & 0o070707070707070707070) >> 3))
return n % 63
Then if you want to count the bits in arbitrarily large integers, you
iterate over them in N-bit chunks, for some N <= 62. Your choice of N
will depend on how you represent your big integers. Probably N is 56 or
48 or 32.
And why 62 bits? Because the bit_count method is certainly written in
C, where every step in bit_count_62 would use 64-bit integers.
If you like this sort of stuff, check out the book "Hacker's Delight" by
Henry Warren. See <https://en.wikipedia.org/wiki/Hacker%27s_Delight>.
- Alan
--
https://mail.python.org/mailman/listinfo/python-list
