Check if power of 2 algorithm ???

[bellefy@gmail.com]

Hi All,

I have a question about a formula I found online at
http://graphics.stanford.edu/~seande...mineIfPowerOf2.

To determine if an integer is a power of 2, the author states that:

f = (v & (v -1)) == 0;

I am very proficient with scripting techniques using PHP so I
understand what we're trying to accomplish here.

However, I can't seem to figure out how to make the example work... :-(

Take, for example, 16.

f = (16 & (16 - 1)) == 0;
f = (16 & (15)) == 0;

The test is always false????????

I think I am not understanding the steps completely...

For reference, in PHP, there is no operator &. The logical AND operator
is &&.

In PHP, the same formula would be written as:

if((v && (v-1)) == 0){
return true;
}

Can anyone explain this to me? I would greatly appreciate any help.

Thanks in advance,

Tim Bellefy

[Chung Leong]

Re: Check if power of 2 algorithm ???

Emmm, you know you need to prefix variable names with dollar signs,
right?

[bellefy@gmail.com]

Re: Check if power of 2 algorithm ???

Sorry...

if(($v && ($v-1)) == 0){
return true;
}

OR

$r = ($v && ($v) == 0 ? true : false);

[bellefy@gmail.com]

Re: Check if power of 2 algorithm ???

Well I fell like a moron...

The & is a bitwise operator and the function works just fine...

I forgot all about those littly guys.

Sorry for my rookie mistake.

[Rik]

Re: Check if power of 2 algorithm ???

bellefy@gmail.c om wrote:[color=blue]
> Well I fell like a moron...
>
> The & is a bitwise operator and the function works just fine...
>
> I forgot all about those littly guys.
>
> Sorry for my rookie mistake.[/color]

Hehe, and it's even in the url: "bithacks" :-)

Grtz,
--
Rik Wasmus

[Toby Inkster]

Re: Check if power of 2 algorithm ???

bellefy@gmail.c om wrote:
[color=blue]
> $r = ($v && ($v) == 0 ? true : false);[/color]

Better:

$r = (($v & ($v-1)) == 0);

NEVER code '?true:false' (or the opposite).

--
Toby A Inkster BSc (Hons) ARCS
Contact Me ~ http://tobyinkster.co.uk/contact

[David Haynes]

Re: Check if power of 2 algorithm ???

Toby Inkster wrote:[color=blue]
> bellefy@gmail.c om wrote:
>[color=green]
>> $r = ($v && ($v) == 0 ? true : false);[/color]
>
> Better:
>
> $r = (($v & ($v-1)) == 0);
>
> NEVER code '?true:false' (or the opposite).
>[/color]
This makes 0 a power of two...

Try:
$r = !($v & ($v-1)) && $v;

-david-

[Dana Cartwright]

Re: Check if power of 2 algorithm ???

"David Haynes" <david.haynes2@ sympatico.ca> wrote in message
news:_DYbg.9301 8$6.44147@fe82. usenetserver.co m...[color=blue]
> Toby Inkster wrote:[color=green]
>> bellefy@gmail.c om wrote:
>>[color=darkred]
>>> $r = ($v && ($v) == 0 ? true : false);[/color]
>>
>> Better:
>>
>> $r = (($v & ($v-1)) == 0);
>>
>> NEVER code '?true:false' (or the opposite).
>>[/color]
> This makes 0 a power of two...
>
> Try:
> $r = !($v & ($v-1)) && $v;
>[/color]

Since it also fails for negative numbers, you might as well include that
case:

$r = !($v & ($v-1)) && ($v > 0);

- Dana