need a function

[Jack Brennen]

If you're permitted a lookup table of size 32, just use TAB[n%37];
I'm sure you can figure out how to fill in TAB[].  (The value of
the function for non-powers-of-two will be pretty much useless,
but if you know the input is a power of two, it works good.

n%37 can be written as n-(n/37)*37, if / throws away the remainder.

If you don't require the function to be "small":

   f(n) = (n/2)%2+
          (n/4)%2+
          (n/8)%2+
          (n/16)%2+
          ...+
          (n/2^30)%2+
          (n/2^31).

    Use the substitution a%b = a-(a/b)*b.

    (Again, assuming that / throws away the remainder.)

Brendan McKay wrote:
> Hi seqfans.  This little problem might amuse someone and the answer
> might even be useful.
> 
> We are considering arithmetic in the non-negative integers mod 2^32.
> The problem is, define a function f(n) using only +-*/ (where / throws
> away the remainder) such that f(2^i) = i for i=0,1,...,31.
> 
> If that is too onerous, you can also use bit-wise boolean operations.
> 
> The corresponding problem for 2^64 is also of interest.
> 
> Cheers, Brendan.
> 
>