Bit length of int or long?

[François Pinard]

Guido van Rossum <guido at python.org> writes:

> In my defense: Francois didn't mention long ints in his first post.

Sorry, I might not have been clear.  I did have longs in head.

There is something amusing, but very intensive on bignums, called Fractran.
This is a programming language for a strange machine doing only multiplies
(and sometime outputting bit lengths), where programs are written as a
sequence of fractions.  Anything computable can be written in Fractran.
I should translate a Fractran engine and share the results with you. :-)

> You're right of course that a method of ints and longs is the right
> solution.  Another method should count '1' bits (useful when using long
> ints as sets of ints).

Besides the bit length of an integer, and the (one-)population count, there
is another useful operation that a few of us once needed: the reversal
of all bits (the number you get by reading the bits backwards, from the
least significative to the most significative).  This last operation pops
up naturally in things like Fourier transforms.

A funny story about the population count is that, for the Cyber CDC 800
series, we wrote an assembler routine doing it faster than the provided
single micro-instruction, using a divide and conquer (or logarithmic)
approach.

Bit reversal of a single computer word is also much faster when done by
divide and conquer.  I do not know how well it would generalise for a long.

-- 
François Pinard   http://www.iro.umontreal.ca/~pinard