Count bits set in parallel
This time it’s not something I make myself. Indeed, I still can’t “see” it 100%: I got it, but it’s a bit complex. A cute little lady counting (bits? ;-) ) It’s a method to count the number of bits in a number in O(1), in just 5 lines of code. INHUMAN. The “human” solutions Of course, there are methods that look way more easy and, given that the size of a number in memory is “fixed”, the O(1) still stands. For example: 0. Based on the “evenness/oddness” of the number 1 2 3 4 5 6 7 8 9 10 unsigned int bits_counter_v0(unsigned int x) { unsigned int count = 0; while ( x != 0 ) { // If odd, add 1 count += (x % 2 == 0) ? 0 : 1; x >>= 1; } return count; } 1. Counting one bit at a time (always the least significant one) 1 2 3 4 5 6 7 8 9 10 unsigned int bits_counter_v1(unsigned int x) { unsigned int count = 0; while ( x != 0 ) { // If least-significant bit is 1, add 1 count += (x & 1) ? 1 : 0; x >>= 1; } return count; } 2. Counting 4 bit at a time with max 8 shifts, using an “hashmap” with precalculated results The fact that it can count the bits in “max 8 shifts” has the trade off of the memory used by the hashmap. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 unsigned int bits_counter_v2(unsigned int x) { unsigned int count = 0; // "Hashmap" of the values for the least significant 4 bits unsigned int int_to_bits_count[16] = { 0, // 0 00 1, // 1 01 1, // 2 10 2, // 3 11 1, // 4 100 2, // 5 101 2, // 6 110 3, // 7 111 1, // 8 1000 2, // 9 1001 2, // 10 1010 3, // 11 1011 2, // 12 1100 3, // 13 1101 3, // 14 1110 4 // 15 1111 }; while ( x != 0 ) { // Add the bits count of the least significant 4 bits count += int_to_bits_count[ x & 15 ]; x >>= 4; } return count; } Let’s see what some insane people made. ...