[SciPy-dev] fft code for testing

[Pearu Peterson]

On Sat, 31 May 2003, Chuck Harris wrote:

> > Btw, does anybody know an efficient way how to test if
> > an integer is a power-of-two in C? Currently djbfft wrapper
> > uses
> >   switch (n) {
> >     case 2:;case 4:;... case 8192: ..
> >   }
> > but there must be a better way.
> 
> Fooling around a bit, I think the construction
> 
> int foo(int n)
> {
>     int ok = 1;
> 
>     if ( n == 1 ||
> 	 n == 2 ||
> 	 n == 4 ||
> 	 n == 8 );
>     else
>         ok = 0;
>     return ok;
> }
> 
> produces the best looking assembly here.

There are 31 C int's that are power of two (assuming 32 bit
machines). Though, may be only the first 24 or so are used in real
applications; for instance, the size of double complex array of length
2**24 is 256MB.

So, when n is not a power-of-two, then at least 31 C int comparisons are
required. I wonder if this is the lowest bound of #operations or
can we do better?

Pearu