Bit twiddlement question: greater of two popcounts

[rjgibert]

Previous post was "almost" working.This should do:

Code: Select all

while (a) {
  if(!b) return true;
  a&=a-1; 
  b&=b-1; // skippable if !a
}
return false;

a = 0, b = 0 seems to fail.

In any solution, b should be tested 1st e.g.

Code: Select all

while (b) {
  if(!a) return true;
  a&=a-1; 
  b&=b-1
}
return false;

However, I think this will probably compile to the same code as some of the other working solutions.

[mcostalba]

If popcount <= 2 then

Code: Select all

if(!a) return false;
if(!b) return true;
if(b & (b-1)) return false;
return a & (a-1);

[mcostalba]

Previous post was "almost" working.This should do:

Code: Select all

while (a) {
  if(!b) return true;
  a&=a-1; 
  b&=b-1; // skippable if !a
}
return false;

a = 0, b = 0 seems to fail.

?

i understood function should return popcnt(a) > popcnt(b)

[Gerd Isenberg]

What's the fastest way to determine from two sparsely populated bitboards the one with the larger population count?

I was thinking some sort of modified Kernighan style one:

Code: Select all

popcnt_a_ge_b(a,b) {
 while (a!=0 & b!=0) {
  a &= a - 1;
  b &= b - 1;
 }
 return a>=b;
}

At the end of the loop, a or b is zero, so a>=b should be fine. Can this be improved? Seems hard, but you never know...

One minor improvement for the final return, is to reuse one already calculated expression ...

Code: Select all

bool popcnt_a_ge_b(a,b) {
 while (a!=0 & b!=0) {
  a &= a - 1;
  b &= b - 1;
 }
 return a!=0;
}

I believe your code above returns a > b rather than a >= b. Something like the following seems to have been your intent:

Code: Select all

bool popcnt_a_ge_b(a,b) {
 while (1) {
  if (b==0 | a==0) return b==0;
  a &= a - 1;
  b &= b - 1;
 }
}

On the other hand, ZW may find your version perfectly usable as is for his purposes. BTW, I'm working in Python, so I may have screwed up the translation. Apologies in advance if I did.

Yep, you are right.

[Zach Wegner]

Good suggestions everyone, interesting stuff.

If popcnt is less then 4 for each bitboard then multiply for 0x5555... Should do the trick:

return a*0x555... > b*0x555...

Well, as you and Ricardo noticed, that doesn't quite work, but it's a very nice idea. I think it might be able to be used though with a bit more trickery (semi ripped off from CPW):

Code: Select all

bool popcnt_a_ge_b(a,b)
{
    const U64 k1 = C64(0x5555555555555555);
    a =  a       - ((a >> 1)  & k1);
    b =  b       - ((b >> 1)  & k1);
    a *= k1;
    b *= k1;
    return (a >= b);
}

I think that works. It can of course give errors if either popcnt is >= 4, but I think for a quick SEE it might be worth it. That function is nicely parallel, and branchless. Looks like it should be about 6-7 cycles total. An error here (for popcount>=4) should be pretty rare and can be ignored.

Unfortunately I'm not sure if I need this function at all any more; I might need to just use full popcounts. I'll see what I come up with for this SEE, it's rather tricky.

[Zach Wegner]

Previous post was "almost" working.This should do:

Code: Select all

while (a) {
  if(!b) return true;
  a&=a-1; 
  b&=b-1; // skippable if !a
}
return false;

a = 0, b = 0 seems to fail.

In any solution, b should be tested 1st e.g.

Code: Select all

while (b) {
  if(!a) return true;
  a&=a-1; 
  b&=b-1
}
return false;

However, I think this will probably compile to the same code as some of the other working solutions.

I fear both of these are a bit too branchy. In my original code I used bitwise & to try and avoid the extra branch. Though these are easily predicted, I'd imagine you'd get at least one misprediction for every two calls. Two separate branches make it harder to predict and increase code size a bit.

[Pradu]

Code: Select all

bool popcnt_a_ge_b(a,b)
{
    const U64 k1 = C64(0x5555555555555555);
    a =  a       - ((a >> 1)  & k1);
    b =  b       - ((b >> 1)  & k1);
    a *= k1;
    b *= k1;
    return (a >= b);
}

Very cool! It looks like you could make this into a popcount when number of bits <=4:

Code: Select all

bool popcnt(U64 a)
{
    const U64 k1 = C64(0x5555555555555555);
    // a*k1 acculumates all the bits into the most significant 2 bits
    // however we want k1*&#40;1<<&#40;an_even_number&#41;) to accumulate
    // as "01" in the most significant 2 bits instead of "10"
    // and therefore subtract &#40;a>>1&#41;&k1 from a
    return ( ( a - (&#40;a>>1&#41;&k1&#41; )*k1 ) >> &#40;64-2&#41;;
&#125;

Perhaps another useful special case of the SWAR popcount is where the number of bits is assumed to be <= 16 ( maybe for rook and bishop mobility? ):

Code: Select all

int popcnt_under16(U64 x)
{
    const U64 k1 = C64(0x1111111111111111);
    const U64 k3 = C64(0x3333333333333333);
    const U64 k5 = C64(0x5555555555555555);
    //accumulate popcnt in every 2 bits
    x -= ((x>>1)&k5);
    //accumulate in every 4 bits, bring to most-significant 4-bits, 
    //and right-shift the population count back down
    return (( (x&k3) + ((x>>2)&k3) )*k1) >> (64-4);
}

And perhaps the even less useful 32-bit popcnt:

Code: Select all

int popcnt_under32(U64 x)
{
    const U64 k1  = C64(0x1111111111111111);
    const U64 k3  = C64(0x3333333333333333);
    const U64 k5  = C64(0x5555555555555555);
    const U64 k0F = C64(0x0F0F0F0F0F0F0F0F);
    const U64 k01 = C64(0x0101010101010101);

    //accumulate popcnt in every 2 bits
    x -= ((x>>1)&k5);
    //accumulate in every 4 bits
    x = ( (x&k3) + ((x>>2)&k3) );
    //accumulate in every 8 ...
    return ((x + (x >>4))&k0F)*k01;
}

[Pradu]

And perhaps the even less useful 32-bit popcnt:

Code: Select all

int popcnt_under32(U64 x)
{
    const U64 k1  = C64(0x1111111111111111);
    const U64 k3  = C64(0x3333333333333333);
    const U64 k5  = C64(0x5555555555555555);
    const U64 k0F = C64(0x0F0F0F0F0F0F0F0F);
    const U64 k01 = C64(0x0101010101010101);

    //accumulate popcnt in every 2 bits
    x -= ((x>>1)&k5);
    //accumulate in every 4 bits
    x = ( (x&k3) + ((x>>2)&k3) );
    //accumulate in every 8 ...
    return ((x + (x >>4))&k0F)*k01;
}

Mistake...

Code: Select all

int popcnt_under32(U64 x)
{
    const U64 k1  = C64(0x1111111111111111);
    const U64 k3  = C64(0x3333333333333333);
    const U64 k5  = C64(0x5555555555555555);
    const U64 k0F = C64(0x0F0F0F0F0F0F0F0F);
    const U64 k01 = C64(0x0101010101010101);

    //accumulate popcnt in every 2 bits
    x -= ((x>>1)&k5);
    //accumulate in every 4 bits
    x = ( (x&k3) + ((x>>2)&k3) );
    //accumulate in every 8 ...
    return (((x + (x >>4))&k0F)*k01) >> (64-8);
}

[mcostalba]

There exsist also 32 bit friendly versions of all of the above, you can look in cpw in case you are interested.