Program to count number of set bits in an (big) array | GeeksforGeeks
Given an integer array of length N (an arbitrarily large number). How to count number of set bits in the array?
The following code illustrates simple program to count set bits in a randomly generated 64 K integer array. The idea is to generate a look up for first 256 numbers (one byte), and break every element of array at byte boundary.
Read full article from Program to count number of set bits in an (big) array | GeeksforGeeks
Given an integer array of length N (an arbitrarily large number). How to count number of set bits in the array?
The following code illustrates simple program to count set bits in a randomly generated 64 K integer array. The idea is to generate a look up for first 256 numbers (one byte), and break every element of array at byte boundary.
int countSetBits(int array[], size_t array_size){ int count = 0; /* META_LOOK_UP(C) - generates a table of 256 integers whose sequence will be number of bits in i-th position where 0 <= i < 256 */ /* A static table will be much faster to access */ static unsigned char const look_up[] = { META_LOOK_UP(C) }; /* No shifting funda (for better readability) */ unsigned char *pData = NULL; for(size_t index = 0; index < array_size; index++) { /* It is fine, bypass the type system */ pData = (unsigned char *)&array[index]; /* Count set bits in individual bytes */ count += look_up[pData[0]]; count += look_up[pData[1]]; count += look_up[pData[2]]; count += look_up[pData[3]]; } return count;}