• Create Account

### #Actualalvaro

Posted 05 October 2012 - 08:26 AM

This code (or similar) is somewhere in that bithacks page wqking linked:
unsigned popcount(unsigned x) {
x -= (x >> 1) & 0x55555555u;
x = (x & 0x33333333u) + ((x >> 2) & 0x33333333u);
x = (x + (x >> 4)) & 0x0f0f0f0fu;
return (x * 0x01010101u) >> 24; // assumes unsigned is 32 bits
}


gcc also has a function called __builtin_popcount, but on my computer the one above is three times faster. You can do it even faster using 64-bit arithmetic.

EDIT: If your hardware can take it, using __builtin_popcount and compiling with -msse4.2 issues the assembly instruction popcnt, which is extremely fast.

### #3alvaro

Posted 05 October 2012 - 08:16 AM

This code (or similar) is somewhere in that bithacks page wqking linked:
unsigned popcount(unsigned x) {
x -= (x >> 1) & 0x55555555u;
x =  (x & 0x33333333u) + ((x >> 2) & 0x33333333u);
x =  (x + (x >> 4)) & 0x0f0f0f0fu;
return (x * 0x01010101u) >> 24; // assumes unsigned is 32 bits
}


gcc also has a function called __builtin_popcount, but on my computer the one above is three times faster. You can do it even faster using 64-bit arithmetic.

EDIT: If your hardware can take it, using __builtin_popcount and compiling with -msse4.2 issues the assembly instruction popcnt, which is extremely fast.

### #2alvaro

Posted 05 October 2012 - 08:15 AM

This code (or similar) is somewhere in that bithacks page wqking linked:
unsigned popcount(unsigned x) {
x -= (x >> 1) & 0x55555555u;
x =  (x & 0x33333333u) + ((x >> 2) & 0x33333333u);
x =  (x + (x >> 4)) & 0x0f0f0f0fu;
return (x * 0x01010101u) >> 24; // assumes unsigned is 32 bits
}


gcc also has a function called __builtin_popcount, but on my computer the one above is three times faster. You can do it even faster using 64-bit arithmetic.

EDIT: If your hardware can take it, using __builtin_popcount and compiling with -msse4.2 issues the assembly instruction popcntl, which is extremely fast.

### #1alvaro

Posted 05 October 2012 - 07:58 AM

This code (or similar) is somewhere in that bithacks page wqking linked:
unsigned popcount(unsigned x) {
x -= (x >> 1) & 0x55555555u;
x =  (x & 0x33333333u) + ((x >> 2) & 0x33333333u);
x =  (x + (x >> 4)) & 0x0f0f0f0fu;
return (x * 0x01010101u) >> 24; // assumes unsigned is 32 bits
}


gcc also has a function called __builtin_popcount, but on my computer the one above is three times faster. You can do it even faster using 64-bit arithmetic.

PARTNERS