The output is

speed of twiddling: 1482 speed of a lookup table: 874

The test code was:

#include <iostream> #include <algorithm> #include <iterator> using namespace std; // ********************* BIT TWIDDLER ********************* // #define SUM_MASK1 0x55555555 #define SUM_MASK2 0x33333333 #define SUM_MASK3 0x07070707 #define SUM_MASK4 0x000f000f #define SUM_MASK5 0x0000001f unsigned int SumOfOnesTwiddle(unsigned int x) { x = (SUM_MASK1 & (x >> 1)) + (SUM_MASK1 & x); x = (SUM_MASK2 & (x >> 2)) + (SUM_MASK2 & x); x = (SUM_MASK3 & (x >> 4)) + (SUM_MASK3 & x); x = (SUM_MASK4 & (x >> 8)) + (SUM_MASK4 & x); x = (SUM_MASK5 & (x >> 16)) + (SUM_MASK5 & x); return x; } void SumOfOnesTwiddleArray(unsigned int* in, unsigned int* out, unsigned int size) { for(int i=0;i<size;i++) out[i] = SumOfOnesTwiddle(in[i]); } // ********************* LOOKUP TABLE ********************* // #define TABLE_SIZE 256 unsigned int table[TABLE_SIZE]; void computeTable() { for(int i=0; i<TABLE_SIZE; i++) table[i] = SumOfOnesTwiddle(i); } unsigned int SumOfOnesTable(unsigned int x) { return table[(x ) & 0xff] + table[(x>>8 ) & 0xff] + table[(x>>16) & 0xff] + table[(x>>24) & 0xff]; } void SumOfOnesTableArray(unsigned int* in, unsigned int* out, unsigned int size) { for(int i=0;i<size;i++) out[i] = SumOfOnesTable(in[i]); } //testing template<class itor> void printOut(itor start, itor end) { cout << hex << "0x"; copy (start, end, ostream_iterator<int>(cout, " 0x")); cout << endl << endl; } #define SIZE 5000 int main() { unsigned int indata[SIZE]; unsigned int outdata[SIZE]; unsigned int outdata2[SIZE]; clock_t start_time, end_time; computeTable(); srand(time(NULL)); for(int i=0;i < SIZE; i++) indata[i] = rand(); printOut(indata, indata+SIZE); SumOfOnesTwiddleArray(indata, outdata, SIZE); SumOfOnesTableArray (indata, outdata2, SIZE); printOut(outdata, outdata+SIZE); printOut(outdata2, outdata2+SIZE); for(int i=0;i < SIZE; i++) if(outdata[i] != outdata2[i]) cout << "BUG!" << endl; start_time = clock(); for(int i=0;i < SIZE; i++) SumOfOnesTwiddleArray(indata, outdata, SIZE); end_time = clock(); cout << dec << "speed of bit twiddling: " << (end_time - start_time) << endl; start_time = clock(); for(int i=0;i < SIZE; i++) SumOfOnesTableArray(indata, outdata, SIZE); end_time = clock(); cout << dec << "speed of a lookup table: " << (end_time - start_time) << endl; }

## No comments:

## Post a Comment