Excerpts from internet.cypherpunks: 3-Jul-94 Re: Dr. Dobbs Dev. Update 1.. by Eli Brandt@jarthur.cs.hm
int byte_ones(int a) // hope this is correct... { a = (a & 0x55) + (a & 0xAA)/2; // 0x55 == 01010101b a = (a & 0x33) + (a & 0xCC)/4; // 0x33 == 00110011b a = (a & 0x0F) + (a & 0xF0)/16; // 0x0F == 00001111b e> return a; }
Note that some compilers might not be smart enough to use logical shift ops and instead use expensive division ops. Just to be safe... int byte_ones(int a) { a = (a & 0x55) + ((a & 0xAA) << 1); // 0x55 == 01010101b a = (a & 0x33) + ((a & 0xCC) << 2); // 0x33 == 00110011b a = (a & 0x0F) + ((a & 0xF0) << 4); // 0x0F == 00001111b return a; } And this runs in O(lg n) where n is the number of bits in `a'. Does anybody have an algorithm for this that beats O(lg n)? _____________________________________________________________________________ Tim Nali \ "We are the music makers, and we are the dreamers of tn0s@andrew.cmu.edu \ the dreams" -Willy Wonka and the Chocolate Factory