🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: comp.compression.research
Article #48

C-language algorithm for finding a sparse bit (repost)

#48
From: Alan Wm Paeth
Date: Wed, 29 Jul 1992 22:58
39 lines
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!awpaeth
References: <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