home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / compress / research / 99 < prev   
Encoding:
Internet Message Format  |  1992-07-28  |  2.7 KB
  1. Xref: sparky comp.compression.research:99 comp.arch:8393 comp.lang.c:11679
  2. Newsgroups: comp.compression.research,comp.arch,comp.lang.c
  3. Path: sparky!uunet!utcsri!skule.ecf!torn!watserv1!watmath!watcgl!watpix.waterloo.edu!awpaeth
  4. From: awpaeth@watpix.waterloo.edu (Alan Wm Paeth)
  5. Subject: Re: Algorithm for finding set bits in a bit-string (and MSB).
  6. Message-ID: <Bs46JC.35n@watcgl.uwaterloo.ca>
  7. Sender: news@watcgl.uwaterloo.ca (USENET News System)
  8. Organization: University of Waterloo
  9. References: <1992Jul26.010325.9885@infonode.ingr.com> <MOSS.92Jul25222337@ibis.cs.umass.edu> <Bs3yBx.7AA@watserv1.uwaterloo.ca>
  10. Date: Tue, 28 Jul 1992 19:37:58 GMT
  11. Lines: 53
  12.  
  13. Given a 'very sparse' integer having only one bit set in position 'p', this
  14. C fragment detects 'very sparseness' and returns p. It is based on two entries
  15. appearing in _Graphics Gems II_ (Academic Press, 1992, ed: Jim Arvo). These
  16. describe integer operations combining bitwise-logic and arithmetic to perform
  17. sparesness tests, bit tallying, etc. (The two entries are by Ken Shoemake and
  18. Alan Paeth; I've forgotten their exact titles).
  19.  
  20. int sparsebit(i)
  21.     long i;
  22.     {
  23.     int p;
  24.     p = 0;
  25. /* return position 'p' on range [0..31] of a "lone bit" integer (value 2^p) */
  26. /* otherwise, return -1. This is "little-Endian form" as the lsb is at p=0. */
  27.     if (i == 0) return(-1);        /* no bits set */
  28.     if ((i & (-i)) != i) return(-1);    /* two or more bits set */
  29.     if (i & 0xAAAAAAAA) p++;
  30.     if (i & 0xCCCCCCCC) p += 2;
  31.     if (i & 0xF0F0F0F0) p += 4;
  32.     if (i & 0xFF00FF00) p += 8;
  33.     if (i & 0xFFFF0000) p += 16;
  34.     return(p);
  35.     }
  36.  
  37.  
  38. The msb of a sparse word having any number of bits set can be found by using:
  39.  
  40. int msbbit(i)
  41.     long i;
  42.     {
  43.     long i2;
  44. /* return the bit position of the msb as [0..31]; return -1 on arg of zero */
  45.     while (i2 = (i & (-i)) i = i2;
  46.     return(sparsebit(i));
  47.     }
  48.  
  49. which removes the set bits (if any) having least weight until merely the msb
  50. remains and then invokes the first subroutine. (This is described in the second
  51. Gem). Note that the first algorithm has worse-case running time which grows
  52. by log2(W) for world length W: 32-bit longs and especially 64-bit longs are big
  53. wins. The bit-discard loop of the second procedure has run time proportional to
  54. the number of 'on' bits in the input. Its worst-case running time occurs when
  55. called with an input of -1 (W passes through the loop).
  56.  
  57. When non-sparse input is anticipated the stock shift-and-test or byte-table
  58. methods give much better average-case performance. In these cases msbbit()
  59. can be sped up significantly with simple heuristics. For instance, a prefacing
  60.  
  61.     if (i < 0) return(-1);
  62.  
  63. in msbbit() gives fast returns for 50% of its input, including the worst case.
  64.  
  65.    /Alan Paeth
  66.