Checking if an Integer is an Exact Binary Power

Dominikus Dittes Scherkl via Digitalmars-d digitalmars-d at puremagic.com
Mon Apr 25 08:35:14 PDT 2016


On Monday, 25 April 2016 at 15:27:02 UTC, Xinok wrote:
> 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
>
> Brute force.
>
> http://dpaste.dzfl.pl/882d7cdc5f74
Yeah. And your test spares the failed case int.min (0x80000000),
because in this case x & -x is negative, but of cause x>>>1 is 
positive, so it returns false despite -(2^^31) is in fact a power 
of two. So this requires an extra cast to work correct (in fact 
no big difference in the assembly):

return (Unsigned!T)(x & -x) > (Unsigned!T)(x >>> 1);



More information about the Digitalmars-d mailing list