home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / compress / research / 101 < prev    next >
Encoding:
Text File  |  1992-07-29  |  1.7 KB  |  52 lines
  1. Xref: sparky comp.compression.research:101 comp.arch:8436 comp.lang.c:11730
  2. Newsgroups: comp.compression.research,comp.arch,comp.lang.c
  3. Path: sparky!uunet!cs.utexas.edu!torn!watserv1!watmath!watcgl!watpix.waterloo.edu!awpaeth
  4. From: awpaeth@watpix.waterloo.edu (Alan Wm Paeth)
  5. Subject: C-language algorithm for finding a sparse bit (repost)
  6. Message-ID: <Bs6AHp.Gpz@watcgl.uwaterloo.ca>
  7. Sender: news@watcgl.uwaterloo.ca (USENET News System)
  8. Organization: University of Waterloo
  9. References: <MOSS.92Jul25222337@ibis.cs.umass.edu> <Bs3yBx.7AA@watserv1.uwaterloo.ca> <Bs46JC.35n@watcgl.uwaterloo.ca>
  10. Date: Wed, 29 Jul 1992 22:58:36 GMT
  11. Lines: 39
  12.  
  13. A hand-transcription error butchered a line in the code previously posted.
  14. Here is the full, unmolested test version used to derive the previous posting.
  15. Many thanks to Dave Hudson (tdh@ksr.com) for bringing this to light.
  16.  
  17.    /Alan Paeth
  18.  
  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. int msbbit(i)
  38.     long i;
  39.     {
  40.     long i2;
  41. /* return the bit position of the msb as [0..31]; return -1 on arg of zero */
  42. /*  if (i<0) return(31); */ /* speed-up assumes a 'long's msb is at pos 31 */
  43.     while (i2 = (i & (i-1))) i = i2;
  44.     return(sparsebit(i));
  45.     }
  46.  
  47. main(argc, argv)
  48.     char *argv[];
  49.     {
  50.     printf("%d\n", msbbit(atoi(argv[1])));
  51.     }
  52.