Friday, August 17, 2012

Generic Bitcount Algorithm in ANSI C

The purpose of the Bitcount algorithm is to return the number of bits set to 1 in a memory block.

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
 */
As you observed in the example above, the generic bitcount algorithm can any type of data as opposite to the simple bitcount algorithm who can only work with integers.

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!

Related Posts Plugin for WordPress, Blogger...
Recommended Post Slide Out For Blogger