On Monday, 25 April 2016 at 19:37:45 UTC, Andrei Alexandrescu wrote:
> On 04/25/2016 03:21 PM, Solomon E wrote:
>> I'm more concerned with getting the application
>> logic right when I program than optimizing for speed or bytes, until
>> something is noticeably pausing or taking extra megabytes.
>
> This is a luxury not available to library writers.

I agree.

>
>> bool isPow2D(T)(T x)
>> {
>>      return (x > 0) && !(x & (x - 1));
>> }
>
> This is worse than what we have now, which is easy to show is correct.
>
>
> Andrei

I wasn't recommending isPow2D for the library, just for the luxury use case of writing cautiously to show the logic is correct.

It's easy to show that the current code for experimental.common.isPowerOf2 (the same logic as isPow2B) does wrong things when a signed type is forced into it.

I was hoping to suggest that if isPow2F isn't wrong, it might be used, because it has been proved and checked to be correct in this thread. However, I don't know if it actually is faster, and it would be difficult to test the speed up, if any, since the function variants are all so small, and isPow2F compiles to different instructions when used with different types. So it might not be worthwhile, unless there's an advantage of correctness or type-safety, which I'm not experienced enough in D to judge.

(The library's descriptions of std.math.nextPow2 are vastly oversimplified compared to what it does as shown in the examples, so attempting to use that for recognizing simple powers of 2 would be a complexity mismatch.)

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

x & -x is the smallest power of 2 that divides x. Basically, if x = xxxx1000 , x & -x = 00001000 . This is easy to proves considering -x = ~x + 1 .

Now, x >> 1 will be of the form 0xxxx100 . If one of these digit is one, then (x >> 1) >= (x & -x) . If they are all zeros, (x >> 1) < (x & -x) which is the case where you have a power of 2.

0 is a special case, can it can be checked that the function return false for this specific input.

This looks like it is correct.

On Monday, 25 April 2016 at 22:15:31 UTC, Solomon E wrote:
> ...
>
> I was hoping to suggest that if isPow2F isn't wrong, it might be used, because it has been proved and checked to be correct in this thread. ...
>

On second thought, no one's going to understand why the code (x & -x) > (x >>> 1) parameterized for all integer types is in the library, if it ever breaks because of some compiler backend problem with the different generated code for the different integer types. So I'll take back suggesting that for the library, (at least until I or someone else understands why it would never break like that.)

The ways to improve D that occur to me based on this are:

(1) It would be better to have a compiler warning on passing signed types to unsigned parameter functions. There wasn't with popcnt, on GDC 5.2.1. There should be more of other warnings like that too.

I like to compile with practically all the warnings & errors on when I try writing a little C, such as a chess engine with no heap allocation that I wrote in January.

-Wall -Wextra -fno-common -Wcast-align -Wredundant-decls -Wbad-function-cast -Wwrite-strings -Waggregate-return -Wstrict-prototypes -Wmissing-prototypes -pedantic -Wformat=2 -Wdouble-promotion -Winit-self -Wmissing-include-dirs -Wswitch-default -Wswitch-enum -Wfloat-equal -Wconversion -Wlogical-op -Wredundant-decls -Wjump-misses-init -Wshadow -Wcast-qual -Wvla -Wsuggest-attribute=pure -fipa-pure-const -Wsuggest-attribute=const

No segfaults from that program, which was not the case with learning to make a thread local class variable in D.

(2) More thorough, precise descriptions in the online library documentation. Some things are told in very loose terms, with unexpected complexities shown in the examples. See std.math.nextPow2 for what I'm talking about. I'd like to rewrite the docs, if I could, or maybe an alternate expanded version, but it's a lot and it's a moving target.

On Monday, 25 April 2016 at 22:42:38 UTC, deadalnix wrote:
> x & -x is the smallest power of 2 that divides x. Basically, if x = xxxx1000 , x & -x = 00001000 . This is easy to proves considering -x = ~x + 1 .
>
> Now, x >> 1 will be of the form 0xxxx100 . If one of these digit is one, then (x >> 1) >= (x & -x) . If they are all zeros, (x >> 1) < (x & -x) which is the case where you have a power of 2.
>
> 0 is a special case, can it can be checked that the function return false for this specific input.
>
> This looks like it is correct.

Yes. Except for the case 0x80000000 (= int.min), because this is negative so NOT smaller than 0x40000000 (= int.min>>>1), which is considered positive.
So the algorithm doesn't work for signed integers (without extra cast).

On Tuesday, 26 April 2016 at 08:12:02 UTC, Dominikus Dittes Scherkl wrote:
> On Monday, 25 April 2016 at 22:42:38 UTC, deadalnix wrote:
>> x & -x is the smallest power of 2 that divides x. Basically, if x = xxxx1000 , x & -x = 00001000 . This is easy to proves considering -x = ~x + 1 .
>>
>> Now, x >> 1 will be of the form 0xxxx100 . If one of these digit is one, then (x >> 1) >= (x & -x) . If they are all zeros, (x >> 1) < (x & -x) which is the case where you have a power of 2.
>>
>> 0 is a special case, can it can be checked that the function return false for this specific input.
>>
>> This looks like it is correct.
>
> Yes. Except for the case 0x80000000 (= int.min), because this is negative so NOT smaller than 0x40000000 (= int.min>>>1), which is considered positive.
> So the algorithm doesn't work for signed integers (without extra cast).

Well, it depends a bit on how you define "is a power of two":

 If you define "x is a power of 2" as "there is a natural number n, so that x == 2*2*...*2 (n-times)" with * defined as multiplication in the ring of integers modulo 2^32 (i.e. int or uint), then int.min and 0 are powers of two because the multiplication overflows.

 If you define "x is a power of 2" as above but based on the multiplication in the ring of integers, then int.min (== -2^31) and 0 are not powers of two.

Am Mon, 25 Apr 2016 17:04:43 +0000
schrieb tsbockman <thomas.bockman@gmail.com>:

> On Monday, 25 April 2016 at 16:48:14 UTC, Lass Safin wrote:
> > Example;
> >
> > import core.bitop;
> > import core.cpuid;
> >
> > int count;
> > if(hasPopcnt)
> >     count = _popcnt; // Uses x86-instruction "popcnt".
> > else
> >     count = popcnt; // Phobos's software implementation.
> >
> > // Do stuff with count
> 
> That is not right (since 2.069, I think?). Adding that check just makes things slower and more complicated:
> 
> core.bitop.popcnt() itself already checks hasPopcnt, and forwards to the intrinsic if it is available.

Can we just use __traits(hasTargetFeature, "popcnt") already
and get rid of _popcnt?

-- 
Marco

On Monday, 25 April 2016 at 15:35:14 UTC, Dominikus Dittes Scherkl wrote:
> On Monday, 25 April 2016 at 15:27:02 UTC, Xinok wrote:
>> 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);

How is it wrong? Negative numbers are NOT powers of two (unless you have an imaginary/complex exponent), so it's still correct to return false for -int.min. Should it not?

http://www.wolframalpha.com/input/?i=solve+2^n+%3D+-%282^31%29+for+n

On Tuesday, 26 April 2016 at 14:37:46 UTC, Marco Leise wrote:
> Can we just use __traits(hasTargetFeature, "popcnt") already
> and get rid of _popcnt?

No, because DMD does not currently support setting SSE4 as the minimum target. Thus, `__traits(hasTargetFeature, "popcnt")` must always return `false` at compile time.

As for LDC and GDC - both already treat `popcnt()` as an intrinsic, and don't need your proposed change.

On Tuesday, 26 April 2016 at 16:53:00 UTC, tsbockman wrote:
> On Tuesday, 26 April 2016 at 14:37:46 UTC, Marco Leise wrote:
>> Can we just use __traits(hasTargetFeature, "popcnt") already
>> and get rid of _popcnt?
>
> No, because DMD does not currently support setting SSE4 as the minimum target. Thus, `__traits(hasTargetFeature, "popcnt")` must always return `false` at compile time.
>
> As for LDC and GDC - both already treat `popcnt()` as an intrinsic, and don't need your proposed change.

It's strange why it emits an branch.

http://goo.gl/jJbSYd
Det version doesn't use cmp and should be fast.

On Tuesday, 26 April 2016 at 08:12:02 UTC, Dominikus Dittes Scherkl wrote:
> On Monday, 25 April 2016 at 22:42:38 UTC, deadalnix wrote:
>> x & -x is the smallest power of 2 that divides x. Basically, if x = xxxx1000 , x & -x = 00001000 . This is easy to proves considering -x = ~x + 1 .
>>
>> Now, x >> 1 will be of the form 0xxxx100 . If one of these digit is one, then (x >> 1) >= (x & -x) . If they are all zeros, (x >> 1) < (x & -x) which is the case where you have a power of 2.
>>
>> 0 is a special case, can it can be checked that the function return false for this specific input.
>>
>> This looks like it is correct.
>
> Yes. Except for the case 0x80000000 (= int.min), because this is negative so NOT smaller than 0x40000000 (= int.min>>>1), which is considered positive.
> So the algorithm doesn't work for signed integers (without extra cast).

You got to explain me how you end up with a negative number by multiplying 2 by 2 a bunch of time.