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