SUMMARY: which bits are set

[Stephen J. Hartley]

>From: hartley at emily.uvm.edu (Stephen J. Hartley)
>Subject: which bits are set
>Newsgroups: comp.lang.c
>Keywords: bits, set, 32-bit integer
>Organization: University of Vermont, Department of Computer Science
>Date: Wed, 12 Dec 90 20:51:14 GMT
>
>  Remember the series of articles on counting the number of bits that are
>set in a 32-bit integer?  I have a related problem: determining the position
>numbers of all the bits that are set in a 32-bit integer.  The "brute force"
>approach follows.  Is there a faster (clever) way to do this in C?  No, I am
>not a student trying to get the net to do my homework.
>  Thanks in advance for your help.  Send e-mail and I will summarize for the
>net.
>                       Steve Hartley
>                       Computer Science faculty
>                       Trinity University in San Antonio

  Much thanks to the following for their e-mail replies.

swc at newton.uvm.edu (Steve Chappelow)
scs at adam.mit.edu (Steve Summit)
Dean Cookson <dean at usenet.INS.CWRU.Edu>
Marc Brandis <brandis at inf.ethz.ch>
Jo Are Rosland <jar at ifi.uio.no>
Robert S. Sutor <rssutor at math.Princeton.EDU>
ken at tucana.csis.dit.csiro.au

  Several people pointed out a speed enhancement to the original program:
break out of the loop as soon as all bits set are found.
  The only complete working alternative program sent to me via e-mail was
Robert Sutor's.  I did a crude timing test using the driver shown below that
calls the routine 100,000 times with the same 15 items of test data.  On
an unloaded Sun 3/80 running SunOS 4.0.3 with 8 megs of memory using cc -O,
his program took 303 seconds and mine took 134 seconds.

===============================================================================
#define BIT_SETSIZE     32
typedef unsigned long   bit_set;

#define NELEM(array) (sizeof(array)/sizeof(array[0]))

void which_bits_set();

main() {
/*
 * Some test data.
 */
        static bit_set test[] = {
                0x7, 0x40000006, 0x7007, 0xf2f4, 0x1f2001f4, 0x80000000,
                0xffffffff, 0xabcabcdd, 0x0, 0x10000000, 0x00070000,
                0x11111111, 0x22222222, 0x33333333, 0x44444444
        };
        int i, j;
        bit_set set_of_bits;
        int bits_are_set[BIT_SETSIZE];

        for (j=0; j<100000; j++) {
                for (i=0; i<NELEM(test); i++) {
                        set_of_bits = test[i];
                        which_bits_set(bits_are_set, set_of_bits);
                }
        }
}

/*
 * This procedure determines which bits are set in a 32-bit long integer
 * and fills up an array with the position numbers (zero based) of the
 * set bits.  A -1 is put into the array if there is an unused slot to
 * serve as a terminator.
 */

void which_bits_set(bits_are_set, set_of_bits)
int bits_are_set[]; bit_set set_of_bits;
{
        int j, m;

        m = 0;
        for (j=0; j<BIT_SETSIZE; j++) {
/*
 * Following line of code added after the original news article was posted.
 * Pointed out first by swc at newton.uvm.edu (Steve Chappelow).
 */
                if (set_of_bits == 0) break;

                if (set_of_bits & 1) {
                        bits_are_set[m] = j;
                        m++;
                }
                set_of_bits = set_of_bits >> 1;
        }
        if (m < BIT_SETSIZE) bits_are_set[m] = -1; /* terminator if room */
}

/*
>From rssutor at math.Princeton.EDU Mon Dec 17 15:24:58 1990
From: Robert S. Sutor <rssutor at math.Princeton.EDU>
Date: Mon, 17 Dec 90 15:24:15 -0500
To: hartley at emily.uvm.edu
Subject: Re: which bits are set
Organization: Princeton University
Status: R

Here is a program that does what you want rather efficiently without
table lookup.  It looks only at the bits which are set and then does
a binary-search-like loop to compute the position of a set bit.
--
                                Robert S. Sutor
Department of Mathematics                       Mathematical Sciences Department
Princeton University                            IBM T.J. Watson Research Center
rssutor at math.princeton.edu                      sutor at yktvmz, sutor at ibm.com
*/

/*
 * I have modified Robert S. Sutor's original program so it can be called
 * by my driver.
 *                      Steve Hartley, December 20, 1990
 */

#define BIT_SETSIZE_HALF        BIT_SETSIZE/2

void which_bits_set(bits_are_set, set_of_bits)
int bits_are_set[]; bit_set set_of_bits;
{
        unsigned bit, base, deg, delta, m, half;

        m = 0;
        half = BIT_SETSIZE_HALF;
        while (set_of_bits) {
/*
 * bit has a single 1 bit in the position
 * of the lowest order 1 bit in set_of_bits
 */
                bit = set_of_bits  & -set_of_bits;
                set_of_bits  ^= bit;    /* remove the bit from set_of_bits */
                delta = deg = half;
                while (1) {             /* compute the position of the bit
                                           via a binary search */
                        base = 1 << deg;
                        if (bit == base)
                                break;
                        delta = (delta == 1) ? 1 : delta >> 1;
                        deg = (bit > base) ? deg + delta : deg - delta;
                }
                bits_are_set[m] = deg;
                m++;
        }
        if (m < BIT_SETSIZE) bits_are_set[m] = -1; /* terminator if room */
}
Stephen J. Hartley, Assistant Professor, phone O:(512)736-7480, H:344-6523
Department of Computer Science, Trinity University, San Antonio, TX 78212
hartley at uvm.edu || ...!uvm.edu!hartley || ...!uunet!uvm-gen!hartley