Article View: comp.compression.research
Article #48C-language algorithm for finding a sparse bit (repost)
From: Alan Wm Paeth
Date: Wed, 29 Jul 1992 22:58
Date: Wed, 29 Jul 1992 22:58
39 lines
1728 bytes
1728 bytes
A hand-transcription error butchered a line in the code previously posted.
Here is the full, unmolested test version used to derive the previous posting.
Many thanks to Dave Hudson (tdh@ksr.com) for bringing this to light.
/Alan Paeth
----
int sparsebit(i)
long i;
{
int p;
p = 0;
/* return position 'p' on range [0..31] of a "lone bit" integer (value 2^p) */
/* otherwise, return -1. This is "little-Endian form" as the lsb is at p=0. */
if (i == 0) return(-1); /* no bits set */
if ((i & (-i)) != i) return(-1); /* two or more bits set */
if (i & 0xAAAAAAAA) p++;
if (i & 0xCCCCCCCC) p += 2;
if (i & 0xF0F0F0F0) p += 4;
if (i & 0xFF00FF00) p += 8;
if (i & 0xFFFF0000) p += 16;
return(p);
}
int msbbit(i)
long i;
{
long i2;
/* return the bit position of the msb as [0..31]; return -1 on arg of zero */
/* if (i<0) return(31); */ /* speed-up assumes a 'long's msb is at pos 31 */
while (i2 = (i & (i-1))) i = i2;
return(sparsebit(i));
}
main(argc, argv)
char *argv[];
{
printf("%d\n", msbbit(atoi(argv[1])));
}
Technical Details
Message-ID:
<Bs6AHp.Gpz@watcgl.uwaterloo.ca>Path:
arc1-ca.pugleaf.net!sparky!uunet!cs.utexas.edu!torn!watserv1!watmath!watcgl!watpix.waterloo.edu!awpaethReferences:
<MOSS.92Jul25222337@ibis.cs.umass.edu> <Bs3yBx.7AA@watserv1.uwaterloo.ca> <Bs46JC.35n@watcgl.uwaterloo.ca>Show Full Headers
Complete Article Headers
Newsgroups: comp.compression.research,comp.arch,comp.lang.c Path: arc1-ca.pugleaf.net!sparky!uunet!cs.utexas.edu!torn!watserv1!watmath!watcgl!watpix.waterloo.edu!awpaeth From: awpaeth@watpix.waterloo.edu (Alan Wm Paeth) Subject: C-language algorithm for finding a sparse bit (repost) Message-ID: <Bs6AHp.Gpz@watcgl.uwaterloo.ca> Sender: news@watcgl.uwaterloo.ca (USENET News System) Organization: University of Waterloo References: <MOSS.92Jul25222337@ibis.cs.umass.edu> <Bs3yBx.7AA@watserv1.uwaterloo.ca> <Bs46JC.35n@watcgl.uwaterloo.ca> Date: Wed, 29 Jul 1992 22:58:36 GMT Lines: 39