## 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.
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

### Bit twiddlement question: greater of two popcounts

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&#40;a,b&#41; &#123;
while &#40;a!=0 & b!=0&#41; &#123;
a &= a - 1;
b &= b - 1;
&#125;
return a>=b;
&#125;``````
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

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&#40;a,b&#41; &#123;
while &#40;a!=0 & b!=0&#41; &#123;
a &= a - 1;
b &= b - 1;
&#125;
return a>=b;
&#125;``````
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
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

### Re: Bit twiddlement question: greater of two popcounts

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

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&#40;a,b&#41; &#123;
while &#40;a!=0 & b!=0&#41; &#123;
a &= a - 1;
b &= b - 1;
&#125;
return a>=b;
&#125;``````
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&#40;a,b&#41; &#123;
while &#40;a!=0 & b!=0&#41; &#123;
a &= a - 1;
b &= b - 1;
&#125;
return a!=0;
&#125;
``````

rjgibert
Posts: 308
Joined: Mon Jun 26, 2006 7:44 am

### Re: Bit twiddlement question: greater of two popcounts

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&#40;a,b&#41; &#123;
while &#40;a!=0 & b!=0&#41; &#123;
a &= a - 1;
b &= b - 1;
&#125;
return a>=b;
&#125;``````
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&#40;a,b&#41; &#123;
while &#40;a!=0 & b!=0&#41; &#123;
a &= a - 1;
b &= b - 1;
&#125;
return a!=0;
&#125;
``````
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&#40;a,b&#41; &#123;
while &#40;1&#41; &#123;
if &#40;b==0 | a==0&#41; return b==0;
a &= a - 1;
b &= b - 1;
&#125;
&#125;
``````
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
Posts: 484
Joined: Mon Mar 13, 2006 10:08 am
Location: Klein-Gerau, Germany
Contact:

### Re: Bit twiddlement question: greater of two popcounts

Code: Select all

``````bool popcnt_a_ge_b&#40;a,b&#41; &#123;
while &#40;a != 0 && b != 0&#41; &#123;
a &= a - 1;
b &= b - 1;
&#125;
return b == 0;
&#125; ``````

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

### Re: Bit twiddlement question: greater of two popcounts

... or even better:

Code: Select all

``````bool popcnt_a_ge_b&#40;a,b&#41; &#123;
while &#40;b != 0 && a != 0&#41; &#123;
a &= a - 1;
b &= b - 1;
&#125;
return b == 0;
&#125;``````

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

### Re: Bit twiddlement question: greater of two popcounts

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

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

Code: Select all

``````while &#40;a&#41; &#123;
if&#40;!b&#41; return true;
a&=a-1;
b&=b-1; // skippable if !a
&#125;
return false;
``````

rjgibert
Posts: 308
Joined: Mon Jun 26, 2006 7:44 am

### Re: Bit twiddlement question: greater of two popcounts

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