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 */
No comments:
Post a Comment
Got a question regarding something in the article? Leave me a comment and I will get back at you as soon as I can!