on writing a number as 2^s * q, where q is odd

[Alan Bawden]

jak <nospam at 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