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;
}
Moderators: hgm, Rebel, chrisw
Code: Select all
popcnt_a_ge_b(a,b) {
while (a!=0 & b!=0) {
a &= a - 1;
b &= b - 1;
}
return a>=b;
}
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: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: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...Code: Select all
popcnt_a_ge_b(a,b) { while (a!=0 & b!=0) { a &= a - 1; b &= b - 1; } return a>=b; }
One minor improvement for the final return, is to reuse one already calculated expression ...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: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...Code: Select all
popcnt_a_ge_b(a,b) { while (a!=0 & b!=0) { a &= a - 1; b &= b - 1; } return a>=b; }
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:Gerd Isenberg wrote:One minor improvement for the final return, is to reuse one already calculated expression ...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: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...Code: Select all
popcnt_a_ge_b(a,b) { while (a!=0 & b!=0) { a &= a - 1; b &= b - 1; } return a>=b; }
Code: Select all
bool popcnt_a_ge_b(a,b) { while (a!=0 & b!=0) { a &= a - 1; b &= b - 1; } return a!=0; }
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;
}
}
Code: Select all
bool popcnt_a_ge_b(a,b) {
while (a != 0 && b != 0) {
a &= a - 1;
b &= b - 1;
}
return b == 0;
}
Code: Select all
bool popcnt_a_ge_b(a,b) {
while (b != 0 && a != 0) {
a &= a - 1;
b &= b - 1;
}
return b == 0;
}
Code: Select all
while (a) {
if(!b) return true;
a&=a-1;
b&=b-1; // skippable if !a
}
return false;
a = 128+64+2, b = 512+32+8 seems to failmcostalba wrote:If popcnt is less then 4 for each bitboard then multiply for 0x5555... Should do the trick:
return a*0x555... > b*0x555...