[Xing]

Description: Following program makes use of look up table to find the number of bits set in a number. It checks 4 least significant bits at a time.

#include <iostream>
#include <climits>

int CountBits(unsigned int);

int main() {

    unsigned int Number;
    std::cout<<"Enter a positive integer >= 0 and <= "<<INT_MAX<<": ";
    std::cin>>Number;
    std::cout<<"The Number of bits set in "<<Number<<": "<<CountBits(Number)<<std::endl;
    return 0;

    }

int CountBits(unsigned int Number) {
    int bits = 0;

    //Cache: Number of bits set in first 16 numbers starting from 0
    int LookUpTable[]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};

    //Counting by checking 4 least significant bits at a time
    for(; Number != 0; Number >>= 4) {
        bits += LookUpTable[ Number & 0x0f ];
       }
    return bits;
    }

[mikeblas]

There are some interesting optimizations that you might not know about which can help this code. The most important one is pretty universal. The way the code is written right now, LookUpTable is a local int array in the CountBits() function. Odds are that the compiler will emit code to create a local copy of that array each and every time this function is called. In other words, this function starts with a memcpy() of a 64 byte block of memory! This is because LookUpTable is a non-static local. You've told the compiler that you want a distinct, fresh copy of LookUpTable each time you run this function, and it obliges you. If you make LookUpTable static const, however, the compiler will assure that you never write to the memory referenced by LookUpTable, and will then put the table in a static data segment. It won't initialize any memory each time the function is called; instead, it'll just lookup into that table. Now that we know we have a stable table, other optimizations are possible depending on the processor we're targeting. Note how none of the values in LookUpTable are more than 4. Yet, we're using an int to store them, and an int might be 4 bytes long. Most of the memory in use by the table is full of zeroes. If we use a narrower data type, we can pack more data into a smaller array. After all, no integer has more than 32 bits set to 1, right? Why is this important? Well, the code is going to look up into that array repeatedly. Certainly, the code would run faster if we could fit that whole array into cache. To help that happen, we should try to make the array as small as possible. If it can fit into one single cache line, we'll know that any reference to the array will bring the whole array into cache the first time the array is referenced. Once the array is small enough, it would be great to align it; most compilers have an __align() pragma or modifier just for that purpose.

[clarence_cool03]

{-='guY'z can u heLp me hOw tO prOgram a supermarket or grocery prOgraM??.. 'pLs i neED 8 2morROW... 'pLS heLp... 'tHank"s a Lot... 'jUz email me d prOgram gUy'z pLs asap... [email protected]=-}