Bits counting trick
by Mithrandir
During my chess AI project (named E85) my team run across the problem of counting the set bits from a long long constant. Of course, counting them in a loop was a solution but it was a slow solution and we wanted to see if there is something more rapid than this, preferably something without using ifs.
And there is such a thing. A quick search on the internet revealed this magical function, which seems to work on all tests until now.
#include <stdlib.h>
#include <stdio.h>
#define m1 0x5555555555555555ll
#define m2 0x3333333333333333ll
unsigned int non_iterative_popcount(const long long b) {
unsigned int n;
const long long a = b - ((b >> 1) & m1);
const long long c = (a & m2) + ((a >> 2) & m2);
n = ((unsigned int) c) + ((unsigned int) (c >> 32));
n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);
n = (n & 0xFFFF) + (n >> 16);
n = (n & 0xFF) + (n >> 8);
return n;
}
int main(){
long long a = 0xff773fff0fffffffll;
printf("%d\n", non_iterative_popcount(a));
return 0;
}
Though I don’t fully understand how this function works, it is a marvelous piece of code, a beautiful snippet.
Thanks to DARKTHOUGHT developers for this snippet.
