Checking if an Integer is an Exact Binary Power

[Matthias Bentrup via Digitalmars-d]

On Tuesday, 26 April 2016 at 08:12:02 UTC, Dominikus Dittes 
Scherkl wrote:
> On Monday, 25 April 2016 at 22:42:38 UTC, deadalnix wrote:
>> 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.
>
> Yes. Except for the case 0x80000000 (= int.min), because this 
> is negative so NOT smaller than 0x40000000 (= int.min>>>1), 
> which is considered positive.
> So the algorithm doesn't work for signed integers (without 
> extra cast).

Well, it depends a bit on how you define "is a power of two":

  If you define "x is a power of 2" as "there is a natural number 
n, so that x == 2*2*...*2 (n-times)" with * defined as 
multiplication in the ring of integers modulo 2^32 (i.e. int or 
uint), then int.min and 0 are powers of two because the 
multiplication overflows.

  If you define "x is a power of 2" as above but based on the 
multiplication in the ring of integers, then int.min (== -2^31) 
and 0 are not powers of two.