On Saturday, 23 April 2016 at 20:34:52 UTC, Nordlöw wrote:
> 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?

CPUID: https://en.wikipedia.org/wiki/CPUID.
You can check for the presence of a lot of instructions with this instruction.
However this will only work on x86 and only run-time.

On Saturday, 23 April 2016 at 20:42:25 UTC, Lass Safin wrote:
> CPUID: https://en.wikipedia.org/wiki/CPUID.
> You can check for the presence of a lot of instructions with this instruction.
> However this will only work on x86 and only run-time.

Code you give a complete code example in D, please or point out a suitable place in druntime/phobos?

On Saturday, 23 April 2016 at 21:04:52 UTC, Nordlöw wrote:
> On Saturday, 23 April 2016 at 20:42:25 UTC, Lass Safin wrote:
>> CPUID: https://en.wikipedia.org/wiki/CPUID.
>> You can check for the presence of a lot of instructions with this instruction.
>> However this will only work on x86 and only run-time.
>
> Code you give a complete code example in D, please or point out a suitable place in druntime/phobos?

https://dlang.org/phobos/core_cpuid.html#.hasPopcnt

However, it is usually better to use the methods stated by Andrei / Dmitry* rather than population count for checking powers of two.

* With the code given by Dmitry you have to check for zero, otherwise it will return true for 0. e.g.  x && !(x & (x - 1))

On Saturday, 23 April 2016 at 20:34:52 UTC, Nordlöw wrote:
> So is there a way to check if popcnt builtin is available on current platform?

As Andrei pointed out, it's not only popcnt being available, it's also it being fast. A function implementing the classic hand-written version compiles down to something like

	lea	eax, [rdi - 1]
	test	eax, edi
	sete	al
	ret

which is already quite good.

There is also blsi to consider on Haswell and above.

 — David

On Saturday, 23 April 2016 at 21:04:52 UTC, Nordlöw wrote:
> On Saturday, 23 April 2016 at 20:42:25 UTC, Lass Safin wrote:
>> CPUID: https://en.wikipedia.org/wiki/CPUID.
>> You can check for the presence of a lot of instructions with this instruction.
>> However this will only work on x86 and only run-time.
>
> Code you give a complete code example in D, please or point out a suitable place in druntime/phobos?

core.bitop.popcnt() uses core.cpuid.hasPopcnt() to choose between the intrinsic _popcnt() and a software fallback algorithm at runtime:
    https://github.com/dlang/druntime/blob/master/src/core/bitop.d#L343

The relative complexity of softPopcnt() also shows why you don't really want to use popcnt() for this task unless you know the intrinsic will be available.

Am Sat, 23 Apr 2016 20:34:52 +0000
schrieb Nordlöw <per.nordlow@gmail.com>:

> 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?

We argued in another, unrelated thread ("Any usable SIMD
implementation?") for compile-time information on the target.
That would include __traits("hasTargetFeature", "popcnt")
A runtime check requires at least a read of a global variable
and I doubt it is faster than `x & (x-1)`.

-- 
Marco

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.
>
> 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.

Note that (A | B) & -(A | B) will give you the minimal power of 2 that divide A and B.

Now, if A == B, you get (A & -A) == A to test if A is a power of 2.

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

I'm not sure why do you test against x - 1 when you could test for equality. Not only it looks like it is going to require an extra computation (x - 1) but also it doesn't work for 0.

On 23 April 2016 at 15:56, Andrei Alexandrescu via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
> 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
>

That can easily be changed. ;-)

On 04/24/2016 02:57 AM, deadalnix wrote:
> On Saturday, 23 April 2016 at 15:29:08 UTC, Andrei Alexandrescu wrote:
>> Yah, that's the canonical. I forgot why I chose (x & -x) > (x - 1)
>> over it.
>
> I'm not sure why do you test against x - 1 when you could test for
> equality. Not only it looks like it is going to require an extra
> computation (x - 1) but also it doesn't work for 0.

So if you do (x & -x) == x that returns 1 for x == 0. For many applications you want to yield 0. So you test for (x & -x) > (x - 1) such that for x == 0 the right hand side is a large number. -- Andrei