Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

Bit Count solutions...

3 views

Skip to first unread message

David Jacobson rimux

unread,

Jul 2, 1991, 10:05:32 AM7/2/91

Well,

I never realized that the "bit count" puzzle had been hashed-over
quite so much allready in comp.lang.c ... but, never-the-less,
much thanks to all those who responded to my query. An accumulation
of responses follows including one from Chris Torek which is an
accumulation itself of "bit count" solutions. There are a couple
of new/unique ones:

=============================================================================
Date: Mon, 01 Jul 91 15:09:02 -0700
From: luc...@canuck.Berkeley.EDU

It appeared on this thread some months ago. The final "best" solution
was table lookup on 8 bit chunks (via a static array of 256 integers)
and shift/mask to transform to 8 bits.
Bye !
Luciano

=============================================================================
Date: Mon, 1 Jul 91 18:15:52 EDT
From: a...@cblph.att.com (Arthur S Kamlet)
Organization: AT&T Bell Laboratories, Columbus, Ohio

In article <6...@shrike.AUSTIN.LOCKHEED.COM> you write:
>Ok,
>
>I've got a puzzle for those interested ... it may have been
>solved many times before but not by me.
>
>I'd like a series of bit operations in C that will return,
>as an int in base 10 form, the number 1's (on bits) in a
>byte (8 bit field). For example:
>
>have 01011010 (90)
>want 00000100 (4) ...number of on bits in 01011010
>
>I was thinking of modding 01011010 (90) by 256 and then doing
>some type of operation on the result but nothing came to me.
>
>Any ideas would be greatly appreciated. Please respond via
>e-mail. I'll post various answers,

Well, if you're limiting yourself to just 8 bit numbers, which can
be represented as a decimal 0-63, why not define a table

int
table[]={ /* 0 00000000 */ 0,
/* 1 00000001 */ 1,
/* 2 00000010 */ 1,
/* 3 00000011 */ 2,
/* 4 00000100 */ 1,
/* 5 00000101 */ 2,

...
...

/*62 11111110 */ 7,
/*63 11111111 */ 8
} ;

And have your foo() return the table[] value.

Not elegant? Why not? Very CPU efficient, methinks?

Why do you need bit operations for an 8-bit number?

(Now if you have large numbers -- say, oh, 64-bit numbers, this
method has certain, ah, limitations :^) In that case, break into
several 8-bit numbers, (through shift and & operations) treat
each part as an 8-bit number, apply the table to each part, and add.

=============================================================================
Date: Mon, 1 Jul 91 16:00:07 -0700
From: "Dave Schaumann" <da...@cs.arizona.edu>
Organization: U of Arizona CS Dept, Tucson

In article <6...@shrike.AUSTIN.LOCKHEED.COM> you write:
|Ok,
|
|I've got a puzzle for those interested ... it may have been
|solved many times before but not by me.
|
|I'd like a series of bit operations in C that will return,
|as an int in base 10 form, the number 1's (on bits) in a
|byte (8 bit field). For example:
|
|have 01011010 (90)
|want 00000100 (4) ...number of on bits in 01011010
|
|I was thinking of modding 01011010 (90) by 256 and then doing
|some type of operation on the result but nothing came to me.
|
|Any ideas would be greatly appreciated. Please respond via
|e-mail. I'll post various answers,

The easiest & quickest way is to simply have a lookup-table:

int nbits1[256] = { 0, 1, 1, 2, 1, 1, 1, 3, ... } ;

Then, you can just index into the array to get your answer.
Of course, you'll have to calculate the entries into the array,
but you only have to do that once. (You should probably write
a probram to create the table, to make sure it's right).

--
_
_ //\miga! | Dave Schaumann | I just hate it when people quote themselves
\X/~~\ | da...@cs.arizona.edu | in their own .sig - me^H^H er, Anonymous

=============================================================================
Date: Mon, 1 Jul 91 21:34:48 EDT
From: Andrew Shapira <sha...@ecse.rpi.edu>

Hi, this is in reference to your question in comp.lang.c about how to
count the number of "1" bits in a byte.

If you want a series of "bit operations", you can do something like:

#define BITCOUNT(bb) \
((bb)&0x1) + (((bb)&0x2)!=0) + (((bb)&0x4)!=0) + ... + (((bb)&0x80)!=0)

There's probably something more elegant along the lines I think you are
looking for, but I wouldn't bother. (If you are interested in the
puzzle aspect of this, then that's something else.) Practically,
there is a better-looking, faster way that does not involve bit
operations. There are only 256 possible values that a byte can have,
so an array with 256 elements covers all possible cases. Given a byte,
the array gives the number of "1" bits in the byte. It looks like
this:

unsigned char bitcount[256] = {
0, /* 00000000 */
1, /* 00000001 */
1, /* 00000010 */
2, /* 00000011 */
1, /* 00000100 */
2, /* 00000101 */
2, /* 00000110 */
3, /* 00000111 */
1, /* 00001000 */
...
7, /* 11111110 */
8 /* 11111111 */
};

When you want to know how many "1" bits there are in "byte", you look
at bitcount[byte]. You may want to write a little program to
automatically generate the code that initializes the table.

Note: I am pretty sure that some machines have hardware instructions to do this,
but an array is portable, easy, and probably fast enough.

-Andrew
sha...@ecse.rpi.edu

=============================================================================
From: David Ian Raymond <dav...@cs.uow.edu.au>
Date: Tue, 2 Jul 91 13:59:44 EST

I think this will work:

#define BITS = 8

main ()
{
int powers[BITS] ;
int calc() ;
int num ;
int i, x=0 ;

powers[0] = 1 ;
for ( i=1; i<BITS; i++ )
powers[i] = powers[i-1] * 2 ;

printf ( "Enter number: " ) ;
scanf ( "%d", &num ) ;

for ( i=7; i>=0; i-- )
x += calc ( &num, powers[i] ) ;

printf ("Number of 1's = %d\n",x) ;
}

int calc ( num, power )
int *num, power ;
{
int val ;

val = *num/power ;
*num %= power ;
return ( val ) ;
}

Regards,
David

=============================================================================
Date: Tue, 2 Jul 91 06:36:03 UT
From: eych...@SUNCUB.BBSO.CALTECH.EDU (Another casualty of applied metaphysics.)

You write:
>I'd like a series of bit operations in C that will return,
>as an int in base 10 form, the number 1's (on bits) in a
>byte (8 bit field). For example:
>
>have 01011010 (90)
>want 00000100 (4) ...number of on bits in 01011010
>
>I was thinking of modding 01011010 (90) by 256 and then doing
>some type of operation on the result but nothing came to me.

I use a little loop in a function call:

int find_bits (int byte) /* Could be char byte; doesn't matter */
{
int num_bits_on = 0;

while (byte) {
num_bits_on += byte & 1;
byte >>= 1;
}
return (num_bits_on);
}

This could, of course, be compressed until sufficiently obfuscated. :-)

-G.
******************************************************************************
Glenn Eychaner - Big Bear Solar Observatory - eych...@suncub.bbso.caltech.edu
"There is no monopoly of common sense / On either side of the political fence"
-Sting, "Russians"

=============================================================================
From: J. Horsmeier <j...@and.nl>
Date: Tue, 2 Jul 91 10:13:29 +0200
Message-Id: <5462.91...@baby.and.nl>
X-Organization: AND Software bv
Westersingel 108
3015 LD Rotterdam
The Netherlands
X-Phone: +31 (10) 436 7100
X-Fax: +31 (10) 436 7110
Organization: AND Software BV Rotterdam

Hi there,

try this one:

int NofBits(Num)
int Num;
{
int Cnt;

for (Cnt= 0; Num; Cnt++)
Num&= (Num-1);

return(Cnt);

} /* NofBits */

Hope you like it!

Jos

+----------------------------------------------------------------------+
|O J.A. Horsmeier AND Software B.V. phone : +31 10 4367100 O|
|O Westersingel 106/108 fax : +31 10 4367110 O|
|O 3015 LD Rotterdam NL e-mail: j...@and.nl O|
|O--------------------------------------------------------------------O|
|O I am a Hamburger (F. Zappa 1974) O|
+----------------------------------------------------------------------+

=============================================================================
Date: Tue, 2 Jul 91 12:06:52 +0200
From: kfe...@nl.oracle.com (Kevin Feeney)

> I'd like a series of bit operations in C that will return,
> as an int in base 10 form, the number 1's (on bits) in a
> byte (8 bit field). For example:

> have 01011010 (90)
> want 00000100 (4) ...number of on bits in 01011010

Hi,
I've wanted a function like this a few times myself. I never got anything
better than the following:

int ones(c)
char c;
{
int count, i;

#define BITS 8
for (i = 0, count = 0; i < BITS; i++)
if (c & (1 << i))
count++;
return(count);
}

An alternative (but not slightly slower) method is:

int ones(c)
char c;
{
int count, i;

#define BITS 8
for (i = 0, count = 0; i < BITS; i++, c >>= 1)
count += (c & 1);
return(count);
}

These appear to be brute force methods to me, so if you get a more
subtle/succinct/clever function/macro could you please send it to me.

> I was thinking of modding 01011010 (90) by 256 and then doing

On most machines "x &= 0xFF" is MUCH faster than "x %= 256",
and gives the same result.

Cheers,
Kevin Feeney (kfe...@oracle.com | kfe...@meiko.nl.oracle.com)

=============================================================================
Date: Tue, 2 Jul 91 04:32:55 -0700
From: to...@elf.ee.lbl.gov (Chris Torek)
Organization: Lawrence Berkeley Laboratory, Berkeley

Bit counts come up all the time. In fact, here is a program that
is left over from the last time it came up on comp.lang.c (since
then it has come up again in comp.arch).

Chris

#ifndef lint
static char rcsid[] = "$Id: bct.c,v 1.5 90/10/13 08:44:12 chris Exp $";
#endif

/*
* bct - bitcount timing
*
* Runs a bunch of different functions-to-count-bits-in-a-longword
* (many assume 32 bits per long) with a timer around each loop, and
* tries to calcuate the time used.
*/
#include <stdio.h>
#include <sys/types.h>

#ifdef FD_SETSIZE
# define USE_GETRUSAGE
# include <sys/time.h>
# include <sys/resource.h>
#else
# include <sys/times.h>
#endif

#define SIZEOF(a) (sizeof(a)/sizeof(a[0]))

/*
* This function is used to calibrate the timing mechanism.
* This way we can subtract the loop and call overheads.
*/
int
calibrate(n)
register unsigned long n;
{
return 0;
}

/*
* This function counts the number of bits in a long.
* It is limited to 63 bit longs, but a minor mod can cope with 511 bits.
*
* It is so magic, an explanation is required:
* Consider a 3 bit number as being
* 4a+2b+c
* if we shift it right 1 bit, we have
* 2a+b
* subtracting this from the original gives
* 2a+b+c
* if we shift the original 2 bits right we get
* a
* and so with another subtraction we have
* a+b+c
* which is the number of bits in the original number.
* Suitable masking allows the sums of the octal digits in a
* 32 bit number to appear in each octal digit. This isn't much help
* unless we can get all of them summed together.
* This can be done by modulo arithmetic (sum the digits in a number by molulo
* the base of the number minus one) the old "casting out nines" trick they
* taught in school before calculators were invented.
* Now, using mod 7 wont help us, because our number will very likely have
* more than 7 bits set. So add the octal digits together to get base64
* digits, and use modulo 63.
* (Those of you with 64 bit machines need to add 3 octal digits together to
* get base512 digits, and use mod 511.)
*
* This is HACKMEM 169, as used in X11 sources.
*/
int
t0_hackmemmod(n)
register unsigned long n;
{
register unsigned long tmp;

tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}

/*
* This is the same as the above, but does not use the % operator.
* Most modern machines have clockless division, and so the modulo is as
* expensive as, say, an addition.
*/
int
t1_hackmemloop(n)
register unsigned long n;
{
register unsigned long tmp;

tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
tmp = (tmp + (tmp >> 3)) & 030707070707;
while (tmp > 63)
tmp = (tmp & 63) + (tmp >> 6);
return tmp;
}

/*
* Above, without using while loop. It takes at most 5 iterations of the
* loop, so we just do all 5 in-line. The final result is never 63
* (this is assumed above as well).
*/
int
t2_hackmemunrolled(n)
register unsigned long n;
{
register unsigned long tmp;

tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
tmp = (tmp + (tmp >> 3)) & 030707070707;
tmp = (tmp & 63) + (tmp >> 6);
tmp = (tmp & 63) + (tmp >> 6);
tmp = (tmp & 63) + (tmp >> 6);
tmp = (tmp & 63) + (tmp >> 6);
tmp = (tmp & 63) + (tmp >> 6);
return (tmp);
}

/*
* This function counts the bits in a long.
*
* It removes the lsb and counting the number of times round the loop.
* The expression (n & -n) yields the lsb of a number,
* but it only works on 2's compliment machines.
*/
int
t3_rmlsbsub(n)
register unsigned long n;
{
register int count;

for (count = 0; n; n -= (n & -n))
count++;
return count;
}

int
t4_rmlsbmask(n)
register unsigned long n;
{
register int count;

for (count = 0; n; count++)
n &= n - 1; /* take away lsb */
return (count);
}

/*
* This function counts the bits in a long.
*
* It works by shifting the number down and testing the bottom bit.
*/
int
t5_testlsb(n)
register unsigned long n;
{
register int count;

for (count = 0; n; n >>= 1)
if (n & 1)
count++;
return count;
}

/*
* This function counts the bits in a long.
*
* It works by shifting the number left and testing the top bit.
* On many machines shift is expensive, so it uses a cheap addition instead.
*/
int
t6_testmsb(n)
register unsigned long n;
{
register int count;

for (count = 0; n; n += n)
if (n & ~(~(unsigned long)0 >> 1))
count++;
return count;
}

int
t7_testsignandshift(n)
register unsigned long n;
{
register int count;

for (count = 0; n; n <<= 1)
if ((long)n < 0)
count++;
return (count);
}

/*
* This function counts the bits in a long.
*
* It works by masking each bit.
* This is the second most intuitively obvious method,
* and is independent of the number of bits in the long.
*/
int
t8_testeachbit(n)
register unsigned long n;
{
register int count;
register unsigned long mask;

count = 0;
for (mask = 1; mask; mask += mask)
if (n & mask)
count++;
return count;
}

/*
* This function counts the bits in a long.
*
* It works by masking each bit.
* This is the most intuitively obvious method,
* but how do you a priori know how many bits in the long?
* (except for ''sizeof(long) * CHAR_BITS'' expression)
*/
int
t9_testeachbit1shl(n)
register unsigned long n;
{
register int count;
register int bit;

count = 0;
for (bit = 0; bit < 32; ++bit)
if (n & ((unsigned long)1 << bit))
count++;
return count;
}

static char nbits[256] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};

static int inbits[256] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};

int
tA_tableshift(n)
register unsigned long n;
{

return (nbits[n & 0xff] + nbits[(n >> 8) & 0xff] +
nbits[(n >> 16) & 0xff] + nbits[n >> 24]);
}

int
tB_tableuchar(n)
unsigned long n;
{
register unsigned char *p = (unsigned char *)&n;

return (nbits[p[0]] + nbits[p[1]] + nbits[p[2]] + nbits[p[3]]);
}

int
tC_tableshiftcast(n)
register unsigned long n;
{

return nbits[(unsigned char) n] +
nbits[(unsigned char) (n >> 8)] +
nbits[(unsigned char) (n >> 16)] +
nbits[(unsigned char) (n >> 24)];
}

int
tD_itableshift(n)
register unsigned long n;
{

return (inbits[n & 0xff] + inbits[(n >> 8) & 0xff] +
inbits[(n >> 16) & 0xff] + inbits[n >> 24]);
}

int
tE_itableuchar(n)
unsigned long n;
{
register unsigned char *p = (unsigned char *)&n;

return (inbits[p[0]] + inbits[p[1]] + inbits[p[2]] + inbits[p[3]]);
}

int
tF_itableshiftcast(n)
register unsigned long n;
{

return inbits[(unsigned char) n] +
inbits[(unsigned char) (n >> 8)] +
inbits[(unsigned char) (n >> 16)] +
inbits[(unsigned char) (n >> 24)];
}

/*
* Explanation:
* First we add 32 1-bit fields to get 16 2-bit fields.
* Each 2-bit field is one of 00, 01, or 10 (binary).
* We then add all the two-bit fields to get 8 4-bit fields.
* These are all one of 0000, 0001, 0010, 0011, or 0100.
*
* Now we can do something different, becuase for the first
* time the value in each k-bit field (k now being 4) is small
* enough that adding two k-bit fields results in a value that
* still fits in the k-bit field. The result is four 4-bit
* fields containing one of {0000,0001,...,0111,1000} and four
* more 4-bit fields containing junk (sums that are uninteresting).
* Pictorially:
* n = 0aaa0bbb0ccc0ddd0eee0fff0ggg0hhh
* n>>4 = 00000aaa0bbb0ccc0ddd0eee0fff0ggg
* sum = 0aaaWWWWiiiiXXXXjjjjYYYYkkkkZZZZ
* where W, X, Y, and Z are the interesting sums (each at most 1000,
* or 8 decimal). Masking with 0x0f0f0f0f extracts these.
*
* Now we can change tactics yet again, because now we have:
* n = 0000WWWW0000XXXX0000YYYY0000ZZZZ
* n>>8 = 000000000000WWWW0000XXXX0000YYYY
* so sum = 0000WWWW000ppppp000qqqqq000rrrrr
* where p and r are the interesting sums (and each is at most
* 10000, or 16 decimal). The sum `q' is junk, like i, j, and
* k above; but it is not necessarry to discard it this time.
* One more fold, this time by sixteen bits, gives
* n = 0000WWWW000ppppp000qqqqq000rrrrr
* n>>16 = 00000000000000000000WWWW000ppppp
* so sum = 0000WWWW000ppppp000sssss00tttttt
* where s is at most 11000 and t is it most 100000 (32 decimal).
*
* Now we have t = r+p = (Z+Y)+(X+W) = ((h+g)+(f+e))+((d+c)+(b+a)),
* or in other words, t is the number of bits set in the original
* 32-bit longword. So all we have to do is return the low byte
* (or low 6 bits, but `low byte' is typically just as easy if not
* easier).
*
* This technique is also applicable to 64 and 128 bit words, but
* 256 bit or larger word sizes require at least one more masking
* step.
*/
int
tG_sumbits(n)
register unsigned long n;
{

n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
n = (n + (n >> 4)) & 0x0f0f0f0f;
n += n >> 8;
n += n >> 16;
return (n & 0xff);
}

/*
* build a long random number.
* The standard rand() returns at least a 15 bit number.
* We use the top 9 of 15 (since the lower N bits of the usual rand()
* repeat with a period of 2^N).
*/
unsigned long
bigrand()
{
#define randbits() ((unsigned long)((rand() >> 6) & 0777))
register int r;

r = randbits() << 27;
r |= randbits() << 18;
r |= randbits() << 9;
r |= randbits();
return (r);
}

/*
* Run the test many times.
* You will need a running time in the 10s of seconds
* for an accurate result.
*
* To give a fair comparison, the random number generator
* is seeded the same for each measurement.
*
* Return value is seconds per iteration.
*/
#ifndef REPEAT
#if defined(mips) || defined(sparc)
#define REPEAT (1L<<20)
#else
#define REPEAT (1L<<18)
#endif
#endif

double
measure(func)
register int (*func)();
{
#ifdef USE_GETRUSAGE
struct rusage ru0, ru1;
register long j;

srand(1);
(void) getrusage(RUSAGE_SELF, &ru0);
for (j = 0; j < REPEAT; ++j)
func(bigrand());
(void) getrusage(RUSAGE_SELF, &ru1);
ru1.ru_utime.tv_sec -= ru0.ru_utime.tv_sec;
if ((ru1.ru_utime.tv_usec -= ru0.ru_utime.tv_usec) < 0) {
ru1.ru_utime.tv_usec += 1000000;
ru1.ru_utime.tv_sec--;
}
return ((ru1.ru_utime.tv_sec + (ru1.ru_utime.tv_usec / 1000000.0)) /
(double)REPEAT);
#else
register long j;
struct tms start;
struct tms finish;

srand(1);
times(&start);
for (j = 0; j < REPEAT; ++j)
func(bigrand());
times(&finish);
return ((finish.tms_utime - start.tms_utime) / (double)REPEAT);
#endif
}

struct table {
char *name;
int (*func)();
double measurement;
int trial;
};

struct table table[] =
{
{ "hackmemmod", t0_hackmemmod },
{ "hackmemloop", t1_hackmemloop },
{ "hackmemunrolled", t2_hackmemunrolled },
{ "rmlsbsub", t3_rmlsbsub },
{ "rmlsbmask", t4_rmlsbmask },
{ "testlsb", t5_testlsb },
{ "testmsb", t6_testmsb },
{ "testsignandshift", t7_testsignandshift },
{ "testeachbit", t8_testeachbit },
{ "testeachbit1shl", t9_testeachbit1shl },
{ "tableshift", tA_tableshift },
{ "tableuchar", tB_tableuchar },
{ "tableshiftcast", tC_tableshiftcast },
{ "itableshift", tD_itableshift },
{ "itableuchar", tE_itableuchar },
{ "itableshiftcast", tF_itableshiftcast },
{ "sumbits", tG_sumbits },
};

main(argc, argv)
int argc;
char **argv;
{
double calibration, v, best;
int j, k, m, verbose;

verbose = argc > 1;
/*
* run a few tests to make sure they all agree
*/
srand(getpid());
for (j = 0; j < 10; ++j) {
unsigned long n;
int bad;

n = bigrand();
for (k = 0; k < SIZEOF(table); ++k)
table[k].trial = table[k].func(n);
bad = 0;
for (k = 0; k < SIZEOF(table); ++k)
for (m = 0; m < SIZEOF(table); ++m)
if (table[k].trial != table[m].trial)
bad = 1;
if (bad) {
printf("wrong: %08lX", n);
for (k = 0; k < SIZEOF(table); ++k)
printf(" %3d", table[k].trial);
printf("\n");
}
}

/*
* calibrate the timing mechanism
*/
calibration = measure(calibrate);
if (verbose)
printf("calibration: %g\n", calibration);

/*
* time them all, keeping track of the best (smallest)
*/
for (j = 0; j < SIZEOF(table); ++j) {
v = measure(table[j].func) - calibration;
if (verbose)
printf("%s: %g\n", table[j].name, v);
table[j].measurement = v;
if (!j || v < best)
best = v;
}
(void) printf("%-24s %-14sratio\n", "function", "time");
for (j = 0; j < SIZEOF(table); ++j) {
(void) printf("%-24s %#10.8g %6.3f\n",
table[j].name,
table[j].measurement,
table[j].measurement / best);
}
exit(0);
}

=============================================================================
Date: Tue, 2 Jul 91 08:58:25 -0400
From: mmk@d62iwa (Morris M. Keesan)

int onebits_in(char byte)
{
register unsigned char rbyte = byte; /* unsigned char so >> 0-fills */
register int bits = 0;

while( rbyte != '\0' ) /* While there are any 1-bits */
{
if( rbyte & '\01' )
++bits; /* low order bit is on -- count it */

rbyte >>= 1; /* Shift low order off into bit bucket */
}

return bits;
}
--------------------------------
Morris M. Keesan m...@d62iwa.mitre.org until 12 July 1991
???@bsw.com after 16 July 1991

The previous version I sent you was the straightforward approach of counting
the bits each time. If this is a heavily used operation, you might consider
another approach, which works for 8-bit quantities, but which I wouldn't want
to use for larger objects, due to memory requirements:

char bytebits[256] =
{
0, 1, 1, 2, 1, 2, 2, 3, /* 0, 1, 2, 3, 4, 5, 6, 7 */
1, 2, 2, 3, 2, 3, 3, 4, /* 8, 9, 10, 11, 12, 13, 14, 15 */
etc.
};

#define Bitsinbyte(byte) (bytebits[(unsigned char)(byte)])

The cast to unsigned char protects you against sign-extension in case you
pass a signed char to Bitsinbyte.

This method, using a lookup table, is the same method that's commonly used in
implementations of the "ctype" operations (isupper,islower,isdigit, etc. in
<ctype.h>).

By the way, if you're really doing these operations on an 8-bit object, mod 256
is a no-op. You just need to make sure that you treat the object as unsigned,
so nothing unwanted happens in promotions to int.
----------------------------------------------------
Morris M. Keesan m...@d62iwa.mitre.org until 12 July 1991
???@bsw.com after 16 July 1991

=============================================================================

____________________________________ _______________________________________
. | David C. Jacobson
=========___/ \___ Lockheed | (512) 386-4267
=======`/ . \' Austin Division | INTERNET:
===/' `\ (LAD) | d...@austin.lockheed.com
____________________________________|_______________________________________
`Nothing of what I say has anything to do with anybody in any way.'

0 new messages