which bits are set

[Stephen J. Hartley]

  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

===============================================================================
#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, m;
        bit_set set_of_bits;
        int bits_are_set[BIT_SETSIZE];

        for (i=0; i<NELEM(test); i++) {
                set_of_bits = test[i];
                printf("0x%08x has these bits set:", set_of_bits);
                which_bits_set(bits_are_set, set_of_bits);
                for (m=0; m<BIT_SETSIZE; m++) {
                        if (bits_are_set[m] < 0) break;
                        printf(" %d", bits_are_set[m]);
                }
                printf("\n");
        }
}

/*
 * 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++) {
                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 */
}
===============================================================================
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