### Bits counting trick

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.