Re: Dr. Dobbs Dev. Update 1/5 July 94 & Schneier

["Timothy L. Nali" <tn0s+@andrew.cmu.edu>]

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