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);
