Checking if an Integer is an Exact Binary Power

[deadalnix via Digitalmars-d]

On Monday, 25 April 2016 at 12:56:27 UTC, Andrei Alexandrescu 
wrote:
> On 4/25/16 6:42 AM, Solomon E wrote:
>> On Monday, 25 April 2016 at 05:35:12 UTC, Andrei Alexandrescu 
>> wrote:
>>>
>>> With gdc https://godbolt.org/g/jcU4np isPow2B is the winner 
>>> (shortest
>>> code, simplest instructions). -- Andrei
>>
>> I generalized function isPow2B to work for negative numbers in 
>> case of a
>> signed type, while keeping the assembly the same or better. 
>> (That also
>> incidentally made it correctly return false for zero.)
>>
>>> bool isPow2B(T)(T x)
>>> {
>>>    return (x & -x) > (x - 1);
>>> }
>>
>> bool isPow2F(T)(T x)
>> {
>>      return (x & -x) > (x >>> 1);
>> }
>>
>> assembly diff:
>> --        subl    $1, %edi
>> ++        shrl    %edi
>>
>
> That's smaller and faster, thanks. But how do you show it is 
> still correct? -- Andrei

x & -x is the smallest power of 2 that divides x. Basically, if x 
= xxxx1000 , x & -x = 00001000 . This is easy to proves 
considering -x = ~x + 1 .

Now, x >> 1 will be of the form 0xxxx100 . If one of these digit 
is one, then (x >> 1) >= (x & -x) . If they are all zeros, (x >> 
1) < (x & -x) which is the case where you have a power of 2.

0 is a special case, can it can be checked that the function 
return false for this specific input.

This looks like it is correct.