Bit twiddlement question: greater of two popcounts

[Zach Wegner]

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

[rjgibert]

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

A very interesting question. I'll have to think about it some more, but for now I can offer a special case acceleration of your method. The special case is where you know that a and b have many 1 bits held in common. By preceding your while loop with:

t = a
a &= ~b
b &= ~t

you can zero out in parallel all those 1 bits held in common

Beware, that If there are no bits held in common, this "acceleration" becomes a deacceleration, since these 3 lines will then accomplish nothing

I hope this helps.

[Zach Wegner]

Hmm, good idea, but unfortunately for my application the bitboards are guaranteed to not have any bits in common at all.

I was just thinking of a way to formulate a super-fast-usually-accurate SEE approximation. Since the popcounts will be around 0-2 in most cases, I think it should be hard to beat the first idea.

[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;
}

[rjgibert]

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.

[smrf]

How about:

Code: Select all

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

[smrf]

... or even better:

Code: Select all

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

[mcostalba]

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

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

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

[rjgibert]

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

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

a = 128+64+2, b = 512+32+8 seems to fail