Wanted: CT-trait and run-time predicate for checking whether its single integer parameter is an exact power of two.

I guess

https://dlang.org/phobos/std_math.html#.truncPow2

or

https://dlang.org/phobos/std_math.html#.nextPow2

could be reused, but I bet there's a more efficient way of checking this.

On Saturday, 23 April 2016 at 13:04:00 UTC, Nordlöw wrote:
> Wanted: CT-trait and run-time predicate for checking whether its single integer parameter is an exact power of two.

popcnt(x) <= 1 ?

On Saturday, 23 April 2016 at 13:06:58 UTC, Vladimir Panteleev wrote:
> On Saturday, 23 April 2016 at 13:04:00 UTC, Nordlöw wrote:
>> Wanted: CT-trait and run-time predicate for checking whether its single integer parameter is an exact power of two.
>
> popcnt(x) <= 1 ?

Great.

My solution:

/** Check if `x` is an exact (binary) power of 2.
   TODO Move to std.math.
   */
bool isPow2(T)(T x)
    if (isIntegral!T)
{
    import core.bitop : popcnt;
    return popcnt(x) == 1;
}

@safe pure nothrow @nogc unittest
{
    // run-time
    assert(!7.isPow2);
    assert(8.isPow2);
    assert(!9.isPow2);

    // compile-time
    static assert(!7.isPow2);
    static assert(8.isPow2);
    static assert(!9.isPow2);
}

Destroy.

On 4/23/16 9:04 AM, Nordlöw wrote:
> Wanted: CT-trait and run-time predicate for checking whether its single
> integer parameter is an exact power of two.
>
> I guess
>
> https://dlang.org/phobos/std_math.html#.truncPow2
>
> or
>
> https://dlang.org/phobos/std_math.html#.nextPow2
>
> could be reused, but I bet there's a more efficient way of checking this.

There's stuff for that in e.g. https://github.com/dlang/phobos/blob/master/std/experimental/allocator/common.d#L462. They're package-private with the intent is to move those slowly into Phobos. -- Andrei

On 4/23/16 9:06 AM, Vladimir Panteleev wrote:
> On Saturday, 23 April 2016 at 13:04:00 UTC, Nordlöw wrote:
>> Wanted: CT-trait and run-time predicate for checking whether its
>> single integer parameter is an exact power of two.
>
> popcnt(x) <= 1 ?

Would be interesting to see how it compares to the handwritten version on different machines. popcnt has a reputation of being slow in older CPUs, in recent ones it has a latency of 3 cycles and a throughput of 1 cycle. -- Andrei

On 4/23/16 9:54 AM, Andrei Alexandrescu wrote:
> On 4/23/16 9:06 AM, Vladimir Panteleev wrote:
>> On Saturday, 23 April 2016 at 13:04:00 UTC, Nordlöw wrote:
>>> Wanted: CT-trait and run-time predicate for checking whether its
>>> single integer parameter is an exact power of two.
>>
>> popcnt(x) <= 1 ?
>
> Would be interesting to see how it compares to the handwritten version
> on different machines. popcnt has a reputation of being slow in older
> CPUs, in recent ones it has a latency of 3 cycles and a throughput of 1
> cycle. -- Andrei

Oh, and the bummer is that on gdc it's a function call: https://godbolt.org/g/dEYCcG -- Andrei

On 23-Apr-2016 16:04, Nordlöw wrote:
> Wanted: CT-trait and run-time predicate for checking whether its single
> integer parameter is an exact power of two.
>
> I guess
>
> https://dlang.org/phobos/std_math.html#.truncPow2
>
> or
>
> https://dlang.org/phobos/std_math.html#.nextPow2
>
> could be reused, but I bet there's a more efficient way of checking this.

x & (x-1) == 0

-- 
Dmitry Olshansky

On 4/23/16 10:41 AM, Dmitry Olshansky wrote:
> On 23-Apr-2016 16:04, Nordlöw wrote:
>> Wanted: CT-trait and run-time predicate for checking whether its single
>> integer parameter is an exact power of two.
>>
>> I guess
>>
>> https://dlang.org/phobos/std_math.html#.truncPow2
>>
>> or
>>
>> https://dlang.org/phobos/std_math.html#.nextPow2
>>
>> could be reused, but I bet there's a more efficient way of checking this.
>
> x & (x-1) == 0

Yah, that's the canonical. I forgot why I chose (x & -x) > (x - 1) over it. -- Andrei

On 04/23/2016 11:29 AM, Andrei Alexandrescu wrote:
> On 4/23/16 10:41 AM, Dmitry Olshansky wrote:
>> On 23-Apr-2016 16:04, Nordlöw wrote:
>>> Wanted: CT-trait and run-time predicate for checking whether its single
>>> integer parameter is an exact power of two.
>>>
>>> I guess
>>>
>>> https://dlang.org/phobos/std_math.html#.truncPow2
>>>
>>> or
>>>
>>> https://dlang.org/phobos/std_math.html#.nextPow2
>>>
>>> could be reused, but I bet there's a more efficient way of checking
>>> this.
>>
>> x & (x-1) == 0
>
> Yah, that's the canonical. I forgot why I chose (x & -x) > (x - 1) over
> it. -- Andrei

Oh I remember. If x == 0, the result should also be 0. -- Andrei

On Saturday, 23 April 2016 at 17:28:21 UTC, Andrei Alexandrescu wrote:
>> Yah, that's the canonical. I forgot why I chose (x & -x) > (x - 1) over
>> it. -- Andrei

So is there a way to check if popcnt builtin is available on current platform?