Path: utzoo!attcan!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!csun!kithrup!sef
From: sef@kithrup.COM (Sean Eric Fagan)
Newsgroups: comp.lang.c
Subject: Re: which bits are set
Message-ID: <1990Dec18.093905.17196@kithrup.COM>
Date: 18 Dec 90 09:39:05 GMT
References: <3047:Dec1618:51:1590@kramden.acf.nyu.edu> <1990Dec17.071404.6544@kithrup.COM> <15598:Dec1804:57:0390@kramden.acf.nyu.edu>
Organization: Kithrup Enterprises, Ltd.
Lines: 57

In article <15598:Dec1804:57:0390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>Eek. Why do you want to make this so slow?

Well, let's see.  The problem was to convert something like

	0x12345678

into something like

	bit_set[0] = 0;
	bit_set[1] = 0;
	bit_set[2] = 0;
	bit_set[3] = 1;
/* ... */

Using a table, the way I would think of is something like

	struct bits_set_struct {
		/* int val; -- optional */
		int bit1, bit2, bit3, bit4;
	} bits_set_array[16] = {
		{ 0, 0, 0, 0 },
		{ 1, 0, 0, 0 },
		{ 0, 1, 0, 0 },
		{ 1, 1, 0, 0 },
	/* ... */
	};

	/* ... */

	get_bits_set(word32_t val, int *array) {
		word32_t temp;
		int i;

		for (i=0; i<8; i++) {
			temp = val&0xf;
			memcpy (array, bit_set_array[temp], 4*sizeof(int));
			array+=4;
			val>>=4;
		}
	}

Right?  You could increase the size of the tables, of course, at expense of
memory.

But, to be honest, I don't think that (the one I just did) is going to be
any faster than the method I suggested earlier.  Since I don't really have a
lot of interest in this (just some spare time before going to sleep 8-)), I
haven't tested and timed them.  They're probably so close it doesn't matter
for most purposes (i.e., I'm not going to run a few million or billion tests
to see which one is faster).

-- 
Sean Eric Fagan  | "I made the universe, but please don't blame me for it;
sef@kithrup.COM  |  I had a bellyache at the time."
-----------------+           -- The Turtle (Stephen King, _It_)
Any opinions expressed are my own, and generally unpopular with others.