hartley@emily.uvm.edu (Stephen J. Hartley) (12/21/90)
>From: hartley@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@newton.uvm.edu (Steve Chappelow) scs@adam.mit.edu (Steve Summit) Dean Cookson <dean@usenet.INS.CWRU.Edu> Marc Brandis <brandis@inf.ethz.ch> Jo Are Rosland <jar@ifi.uio.no> Robert S. Sutor <rssutor@math.Princeton.EDU> ken@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@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@math.Princeton.EDU Mon Dec 17 15:24:58 1990 From: Robert S. Sutor <rssutor@math.Princeton.EDU> Date: Mon, 17 Dec 90 15:24:15 -0500 To: hartley@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@math.princeton.edu sutor@yktvmz, sutor@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@uvm.edu || ...!uvm.edu!hartley || ...!uunet!uvm-gen!hartley