need a function

[Brendan McKay]

Sorry Max, but I want a *formula*.  No tables to look up.  "Simple" is
not defined, but we will know it when we see it.

Andrew Weimholt just posted a formula (thanks Andrew!) but probably
we can make it simpler.

If table-lookup is allowed, it would be hard to do better than this:

int xyz[] = {0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18};
answer := xyz[n%37];

Brendan.

* Max Alekseyev <maxale at gmail.com> [080614 17:54]:
> Brendan,
> 
> I'm not sure what "simple" means to you. One of those link suggest the
> following code:
> 
> ===
> // OR (IF YOU KNOW v IS A POWER OF 2):
> 
> const unsigned int b[] = {0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0,
> 0xFF00FF00, 0xFFFF0000};
> register unsigned int c = (v & b[0]) != 0;
> for (i = 4; i > 0; i--) // unroll for speed...
> {
>   c |= ((v & b[i]) != 0) << i;
> }
> ===
> 
> For me it looks simple and efficient.
> 
> As of loops - they are hard to avoid. Even computing a value of a
> polynomial (such as Lagrange interpolating polynomial) implies a kind
> of a loop.
> 
> Regards,
> Max
> 
> On Sat, Jun 14, 2008 at 12:35 AM, Brendan McKay <bdm at cs.anu.edu.au> wrote:
> > Thanks, but I am looking for something that is not a loop (unrolled
> > or not) or involves a table lookup. The fact that it only needs to
> > work for powers of 2 should make it easier.  Just the existence is
> > not interesting, I'm hoping for something _simple_.
> >
> > Brendan,
> >
> >
> > * Max Alekseyev <maxale at gmail.com> [080614 17:13]:
> >> Take a look at:
> >> http://aggregate.org/MAGIC/#Log2%20of%20an%20Integer
> >> http://www.cs.utk.edu/~vose/c-stuff/bithacks.html#IntegerLogObvious
> >> http://www.jjj.de/bitwizardry/bitwizardrypage.html
> >> etc.
> >>
> >> Regards,
> >> Max
> >>
> >> On Fri, Jun 13, 2008 at 11:09 PM, Brendan McKay <bdm at cs.anu.edu.au> 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.
> >> >
> >