Bit twiddlement question: greater of two popcounts

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Bit twiddlement question: greater of two popcounts

Post by Zach Wegner » Thu Aug 06, 2009 12:54 am

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
Posts: 308
Joined: Mon Jun 26, 2006 7:44 am

Re: Bit twiddlement question: greater of two popcounts

Post by rjgibert » Thu Aug 06, 2009 2:35 am

Zach Wegner wrote: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.

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Bit twiddlement question: greater of two popcounts

Post by Zach Wegner » Thu Aug 06, 2009 3:44 am

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
Posts: 2206
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Bit twiddlement question: greater of two popcounts

Post by Gerd Isenberg » Thu Aug 06, 2009 6:33 am

Zach Wegner wrote: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
Posts: 308
Joined: Mon Jun 26, 2006 7:44 am

Re: Bit twiddlement question: greater of two popcounts

Post by rjgibert » Thu Aug 06, 2009 7:51 am

Gerd Isenberg wrote:
Zach Wegner wrote: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.

User avatar
smrf
Posts: 484
Joined: Mon Mar 13, 2006 10:08 am
Location: Klein-Gerau, Germany
Contact:

Re: Bit twiddlement question: greater of two popcounts

Post by smrf » Thu Aug 06, 2009 8:16 am

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

User avatar
smrf
Posts: 484
Joined: Mon Mar 13, 2006 10:08 am
Location: Klein-Gerau, Germany
Contact:

Re: Bit twiddlement question: greater of two popcounts

Post by smrf » Thu Aug 06, 2009 8:20 am

... 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
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Bit twiddlement question: greater of two popcounts

Post by mcostalba » Thu Aug 06, 2009 11:38 am

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

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

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Bit twiddlement question: greater of two popcounts

Post by mcostalba » Thu Aug 06, 2009 3:49 pm

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
Posts: 308
Joined: Mon Jun 26, 2006 7:44 am

Re: Bit twiddlement question: greater of two popcounts

Post by rjgibert » Thu Aug 06, 2009 3:52 pm

mcostalba wrote: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

Post Reply