Re: 0 is not a power of 2

[John Colvin via Digitalmars-d]

On Tuesday, 19 May 2015 at 05:16:48 UTC, Andrei Alexandrescu 
wrote:
So there's this classic trick:

bool isPowerOf2(uint x)
{
    return (x & (x - 1)) == 0;
}
Pretty neat, but it wrongly returns true for x == 0. So the 
obvious fix is:

bool isPowerOf2(uint x)
{
    return x && (x & (x - 1)) == 0;
}

But that has branches in it. So I came up with:

bool isPowerOf2(uint x)
{
    return (x & (x - 1) | !x) == 0;
}

which has no branches at least with dmd, see 
http://goo.gl/TVkCwc.

Any ideas for faster code?


Thanks,

Andrei

I tested with a few different (modern) backends to see what was 
generated, they all essentially give you this (gcc 5.1.0 -O3 
-march=broadwell):

isPowerOf2:
        xorl    %eax, %eax
        testl   %edi, %edi
        je      .L5
        blsr    %edi, %edi
        testl   %edi, %edi
        sete    %al
.L5:
        ret
isPowerOf2b:
        blsr    %edi, %edx
        xorl    %eax, %eax
        testl   %edi, %edi
        sete    %al
        orl     %eax, %edx
        sete    %al
        ret

but if your not restricting the build to such recent processor, 
you can't emit BLSR, so you get this instead (gcc 5.1.0 -O3):

isPowerOf2b:
        leal    -1(%rdi), %eax
        xorl    %edx, %edx
        andl    %edi, %eax
        testl   %edi, %edi
        sete    %dl
        orl     %edx, %eax
        sete    %al
        ret