0 is not a power of 2

Almighty Bob via Digitalmars-d digitalmars-d at puremagic.com
Tue May 19 04:55:52 PDT 2015


On Tuesday, 19 May 2015 at 09:34:04 UTC, Almighty Bob wrote:
> 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;
>> }
>>
>> which has no branches at least with dmd, see 
>> http://goo.gl/TVkCwc.
>>
>> Any ideas for faster code?
>
> If you dont mind asm then after you do...
>
> tmp = x-1;
>
> you could add the borrow/carry flag back onto the tmp, so it'd 
> add back up to zero any time there's an underflow in the (x-1) 
> op.
>
> So two extra instructions, (you need a zero for the ADC) no 
> branch.

Oops, should be either add the carry onto x, or subtract the 
carry from tmp. Either way the result of the & is non zero.




More information about the Digitalmars-d mailing list