# need a function

Max Alekseyev maxale at gmail.com
Sat Jun 14 09:53:28 CEST 2008

```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.
>> >
>

```