NetNews Usenet Archive 1993 #1/NN_1993_1.iso/spool/comp/sys/mac/programm/20804

Internet Message Format | 1993-01-06 | 1.7 KB

Path: sparky!uunet!cs.utexas.edu!natinst.com!natinst.com!not-for-mail
From: [e-mail] (Stepan Riha)
Newsgroups: comp.sys.mac.programmer
Subject: Re: (Q) Need bit manipulation algorithm
Date: 6 Jan 1993 10:57:45 -0600
Organization: National Instruments, Austin, TX
Lines: 33
Message-ID: <[e-mail]>
References: <[e-mail]> <[e-mail]> <[e-mail]>
NNTP-Posting-Host: falcon.natinst.com

In article <[e-mail]> [e-mail] (Lloyd Lim) writes:
>In article <[e-mail]> [e-mail] (Sho Kuwamoto) writes:
>>
>>Maybe not the fastest method, but a simple one:
>>   1) come up with an algorithm which counts the number of
>>      1's in a given bit pattern.  You'll either use a loop
>>      with shifts and increments in it, or you'll use masks.
>>[...]
>
>There is a neat trick for counting the number of bits in a word that
>a Microsoft geek showed me one time.  If there are k bits with 1's,
>it runs in O(k) time.
>...  Anyone remember this algorithm?

I've come up with another algorithm that's O(log(n)) where n is the number
of bits.  For a 32 bit integer it takes 5 iterations.  It works by counting
the number of ones in 2 adjacent bits, then 4 adjacent bits, then 8, etc.

long NumOnes(register unsigned long x)
{
    register int    i;
    unsigned long masks[5] = {    0x55555555, 0x33333333, 0x0F0F0F0F,
                    0x00FF00FF, 0x0000FFFF };
    register unsigned long *mask = masks;
    for (i=0; i<5; i++, mask++)
        x = (x&*mask) + ((x>>(1<<i))&*mask);
    return (long)x;
}

    - Stepan
--
   Stepan Riha -- [e-mail]