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