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.

About these ads