Program to count number of set bits in an ( big ) array |  ; Size of array 64 K ; GROUP_A - When combined with META_LOOK_UP generates count for 4 x4 elements ; GROUP_B - When combined with META_LOOK_UP generates count for 4 x4x4 elements ; GROUP_C - When combined with META_LOOK_UP generates count for 4 x4x4x4 elements ; Provide appropriate letter to generate the table ; A static table will be much faster to access ; No shifting funda ( for better readability ) ; It is fine , bypass the type system ; Count set bits in individual bytes ; Driver program , generates table of random 64 K numbers ; Seed to the random - number generator ; Generate random numbers .
#include <bits/stdc++.h> NEW_LINE #include <time.h> NEW_LINE using namespace std ; #define SIZE  (1 << 16)  NEW_LINE #define GROUP_A ( x )  x, x + 1, x + 1, x + 2  NEW_LINE #define GROUP_B ( x )  GROUP_A(x), GROUP_A(x+1), GROUP_A(x+1), GROUP_A(x+2)  NEW_LINE #define GROUP_C ( x )  GROUP_B(x), GROUP_B(x+1), GROUP_B(x+1), GROUP_B(x+2)  NEW_LINE #define META_LOOK_UP ( PARAMETER ) \NEW_LINEGROUP_##PARAMETER(0),\NEW_LINEGROUP_##PARAMETER(1),\NEW_LINEGROUP_##PARAMETER(1),\NEW_LINEGROUP_##PARAMETER(2)\NEW_LINEint countSetBits(int array[], size_t array_size) NEW_LINE { int count = 0 ; static unsigned char const look_up [ ] = { META_LOOK_UP ( C ) } ; unsigned char * pData = NULL ; for ( size_t index = 0 ; index < array_size ; index ++ ) { pData = ( unsigned char * ) & array [ index ] ; count += look_up [ pData [ 0 ] ] ; count += look_up [ pData [ 1 ] ] ; count += look_up [ pData [ 2 ] ] ; count += look_up [ pData [ 3 ] ] ; } return count ; } int main ( ) { int index ; int random [ SIZE ] ; srand ( ( unsigned ) time ( 0 ) ) ; for ( index = 0 ; index < SIZE ; index ++ ) { random [ index ] = rand ( ) ; } cout << " Total ▁ number ▁ of ▁ bits ▁ = ▁ " << countSetBits ( random , SIZE ) ; return 0 ; }