A simple implementation of the Bitcount algorithm would be:
/*
* Description:
* The function returns the number of bits set the 1 in a integer
* Parameters:
* data - the integer who will be verified
* Returns:
* The number of bits set to 1
*/
int SimpleBitCount(unsigned long data)
{
/*Calculates the number of bits in a unsigned integer*/
int size = sizeof(data) * 8;
int counter = 0;
/*Sets the first bit of the mask*/
unsigned long mask = 0x0001U;
int i;
for(i = 0; i < size; i++)
{
/*Checks if an 1 was encountered*/
if( (mask & data) !=0)
{
counter++;
}
/*Sets the next bit of the mask, clears the bit before*/
mask<<=1;
}
return counter;
}
The main disadvantage of this implementation is that the data must be a integer or convertible to an integer.Example:
#include<stdio.h>
int SimpleBitCount(unsigned long data);
int main(void)
{
unsigned long v1 = 1539;
long v1_ones = SimpleBitCount(v1);
long v1_zeroes = (sizeof(unsigned long)*8) - v1_ones;
printf("Size %d bits\nOnes: %ld bits\nZeroes: %ld bits",
sizeof(unsigned long)*8, v1_ones, v1_zeroes);
return 0;
}
/*Output:
Size 32 bits
Ones: 4 bits
Zeroes: 28 bits
*/
To eliminate the the disadvantage mentioned before we need to make the sent data generic using a void pointer. Since, we couldn't possibly know the size of the sent data we must send the size of the data as a parameter./*
* Description:
* The function returns the number of bits set the 1 in a memory block
* Parameters:
* data - a generic pointer to the memory block
* bytes - the size of the memory block in bytes
* Returns:
* The number of bits set to 1 in the memory block
*/
long GenericBitCount(void* data, size_t bytes)
{
unsigned char* iterator = NULL;
unsigned char mask;
unsigned int i, j;
long counter = 0;
/*Positions the iterator at the beginning of the memory block*/
iterator = data;
/*Iterates through all the bytes in the memory block*/
for (i = 0; i < bytes; i++)
{
/*Reinitializes the mask for checking the first bit*/
mask = 1;
/*Iterates through all the bits of a byte from the memory block*/
for (j = 0; j < 8; j++)
{
/*Checks if an 1 was encountered*/
if ( ( (*iterator) & mask ) !=0 )
{
counter++;
}
/*Modifies the mask so the next bit from the byte can be checked*/
mask <<= 1;
}
/*Moves the the next byte*/
iterator = iterator + 1;
}
return counter;
}
Example:#include<stdio.h>
#include<string.h>
typedef struct
{
char firstByte;
char secondByte;
}SampleStruct;
long GenericBitCount(void* data, size_t bytes);
int main(void)
{
unsigned long v1 = 1539;
char v2[] = "The bird is the word";
SampleStruct v3 = {0xFF, 0xFF};
long v1_ones = GenericBitCount(&v1,sizeof(unsigned long));
long v1_zeroes = (sizeof(unsigned long)*8) - v1_ones;
long v2_ones = GenericBitCount(&v2,sizeof(char) * strlen(v2));
long v2_zeroes = (sizeof(char) * strlen(v2)*8) - v2_ones;
long v3_ones = GenericBitCount(&v3,sizeof(SampleStruct));
long v3_zeroes = (sizeof(SampleStruct)) * 8 - v3_ones;
printf("v1 : Size %5d bits Ones: %5ld bits Zeroes: %5ld bits\n"
"v2 : Size %5d bits Ones: %5ld bits Zeroes: %5ld bits\n"
"v3 : Size %5d bits Ones: %5ld bits Zeroes: %5ld bits\n",
sizeof(unsigned long)*8, v1_ones, v1_zeroes,
sizeof(char)*strlen(v2)*8, v2_ones, v2_zeroes,
sizeof(SampleStruct)*8, v3_ones, v3_zeroes );
return 0;
}
/*Output:
v1 : Size 32 bits Ones: 4 bits Zeroes: 28 bits
v2 : Size 160 bits Ones: 67 bits Zeroes: 93 bits
v3 : Size 16 bits Ones: 16 bits Zeroes: 0 bits
*/
