🚀 go-pugleaf

In article <4jbciv$2kk@solutions.solon.com>, vjarnot@mnw.net (Asmodeus) writes:
|> 
|> I have set up an array in the following manner (obviously I just need
|> 0 or 1) :
|> 
|> typedef struct my_bits {
|> 	unsigned the_bit : 1;
|> };
|> 
|> my_bits the_array[800][800];
|> 
|> 	My question is this : I have read that some operations ( =,+,- are
|> what I use) are slower when performed on bits as opposed to other
|> types.  My objective is to optimize the code for speed, and I figured
|> using less memory would help me do so, now I'm having doubts.  So what
|> is more efficient, bits or some other type???

If you are interested in speed, I suggest

	int the_bit [800][800];

If you are interested in space, one suggestion is

	# include	<limits.h>
	
	# define	UNSIGNED_BIT	(CHAR_BIT * sizeof (unsigned))

	struct {
		unsigned the_bits [UNSIGNED_BIT]: 1;
	} the_array [800][(800 + UNSIGNED_BIT - 1) / UNSIGNED_BIT];

	# define	BIT(X, Y)\
		the_array [Y][(X) / UNSIGNED_BIT].the_bits [(X) % UNSIGNED_BIT]

Konrad Schwarz

vjarnot@mnw.net (Asmodeus) writes:


>I have set up an array in the following manner (obviously I just need
>0 or 1) :

>typedef struct my_bits {
>	unsigned the_bit : 1;
>};

>my_bits the_array[800][800];

You are still allowed to take the address of "the_array[42][471]". 
If the smallest addressable unit on your machine is not one bit,
I'd expect _every_ compiler to generate objects that are at least
the size of the smallest addressable unit. It might well decide 
to use at least the size of an int (the "natural object size" on
your machine) for each "struct my_bits".

>	My question is this : I have read that some operations ( =,+,- are
>what I use) are slower when performed on bits as opposed to other
>types.  My objective is to optimize the code for speed, and I figured
>using less memory would help me do so, now I'm having doubts.  So what
>is more efficient, bits or some other type???

This depends on the capacities of your machine, not on the 
programming language you use. If your machine allows unaligned
access to memory, it is still possible that unaligned access
is _much_ slower than natural access.

In general, speed efficiency and size efficiency are incompatible
goals, and there is a trade-off between them. 

Kurt
--
| Kurt Watzka                             Phone : +49-89-2180-6254
| watzka@stat.uni-muenchen.de
| ua302aa@sunmail.lrz-muenchen.de

Asmodeus (vjarnot@mnw.net) wrote:
: 
: I have set up an array in the following manner (obviously I just need
: 0 or 1) :
: 
: typedef struct my_bits {
: 	unsigned the_bit : 1;
: };

lets say that obvious bug here was just a typo.

: 
: my_bits the_array[800][800];
: 
: 	My question is this : I have read that some operations ( =,+,- are
: what I use) are slower when performed on bits as opposed to other
: types.  My objective is to optimize the code for speed, and I figured
: using less memory would help me do so, now I'm having doubts.  So what
: is more efficient, bits or some other type???


Who makes you think the compiler will use less memory for my_bits
the_array[800][800]; compared to for instance char the_array[800][800];
The compiler may do so, but i guess most don't.

In fact i just tried it here, and the result was that your version
used 4 times as much memory as the char version. (The compiler uses
4 bytes (his int) for my_bits.

But if you want to optimize for speed, there is no general solution,
you should check how your compiler handles bitfields and can decide then
if it makes sense or not.

Herbert
-- 
Herbert Kremser                                      |  "On the Internet,
kremser@flinux.tu-graz.ac.at                         |   nobody knows
kremser@sbox.tu-graz.ac.at                           |   you're a dog." 

In article <4jbciv$2kk@solutions.solon.com> vjarnot@mnw.net "Asmodeus" writes:

>
>I have set up an array in the following manner (obviously I just need
>0 or 1) :
>
>typedef struct my_bits {
>        unsigned the_bit : 1;
>};

I assume you meant:

typedef struct {
        unsigned the_bit : 1;
} my_bits;

The first problem here is that the struct does *not* consist of just one bit.
The smallest size it can have is 1 byte (char) and it could well be more
depending on how your compiler allocates bitfields.

>my_bits the_array[800][800];
>
>        My question is this : I have read that some operations ( =,+,- are
>what I use) are slower when performed on bits as opposed to other
>types.

On most archetectures, yes.

> My objective is to optimize the code for speed, and I figured
>using less memory would help me do so, now I'm having doubts.  So what
>is more efficient, bits or some other type???

Unless you ave platform specific information to the contrary you should
assume that int/unsigned int are the most efficient integer types.

-- 
-----------------------------------------
Lawrence Kirby | fred@genesis.demon.co.uk
Wilts, England | 70734.126@compuserve.com
-----------------------------------------

In article <4jbciv$2kk@solutions.solon.com>, vjarnot@mnw.net wrote:

|I have set up an array in the following manner (obviously I just need
|0 or 1) :

|typedef struct my_bits {
|        unsigned the_bit : 1;
|};
|
|my_bits the_array[800][800];
|
|        My question is this : I have read that some operations ( =,+,- are
|what I use) are slower when performed on bits as opposed to other
|types.  My objective is to optimize the code for speed, and I figured
|using less memory would help me do so, now I'm having doubts.  So what
|is more efficient, bits or some other type???

I think the idea of 'bit-fields' have mislead you. The size of the matrix
above is at least 800*800 chars, not 800*800 bits as you might have thought.

This is what the Standard has to say about bit fields:

6.5.2.1. Structure and union specifiers

Constraints

An implementation may allocate any addressable storage unit large enough
to hold a bit-field. If enough space remains, a bit-field that immediately
follows another bit-field in a structure shall be packed into adjacent
bits of the same unit.

[ end of quote ]

The smalles addressable storage unit is a char and an implementation 
is not required to pack adjacent structures in an addressable storage
unit, so you might a well have written:

char the_array[800][800];

because that's the cheapest you can get here without explicit (expensive)
bit fiddling implemented by yourself ...

kind regards,

Jos aka jos@and.nl
-- 
Atnwgqkrl gy zit vgksr, ug qshiqwtzoeqs!

I posted the following suggestion for a ``packed array'' of bits yesterday:

|> If you are interested in space, one suggestion is
|> 
|> 	# include	<limits.h>
|> 	
|> 	# define	UNSIGNED_BIT	(CHAR_BIT * sizeof (unsigned))
|> 
|> 	struct {
|> 		unsigned the_bits [UNSIGNED_BIT]: 1;
|> 	} the_array [800][(800 + UNSIGNED_BIT - 1) / UNSIGNED_BIT];
|> 
|> 	# define	BIT(X, Y)\
|> 		the_array [Y][(X) / UNSIGNED_BIT].the_bits [(X) % UNSIGNED_BIT]

Upon further reflection, I now am more inclined toward the following:

	struct {
		unsigned b [800][800]:1;
	} the_array;

Furthermore, in yesterdays posting making the size of the cell sizeof (unsigned)
is arbitrary; in particular, it has nothing to do with the fact that the
type of the bitfield is unsigned.  In the environment I am currently
computing in, a cell size of sizeof (void *) would be more likely to make
the cell size equal to the machine word length.  I doubt that either choice
will make much of a difference speed wise.

Konrad Schwarz

In article <4je1p1$g1s@solutions.solon.com>
schwarz@mips.complang.tuwien.ac.at (Konrad Schwarz) writes:

|> I posted the following suggestion for a ``packed array'' of bits yesterday:

|> |> If you are interested in space, one suggestion is
|> |> 
|> |>   # include   <limits.h>
|> |>   
|> |>   # define    UNSIGNED_BIT    (CHAR_BIT * sizeof (unsigned))
|> |> 
|> |>   struct {
|> |>       unsigned the_bits [UNSIGNED_BIT]: 1;
|> |>   } the_array [800][(800 + UNSIGNED_BIT - 1) / UNSIGNED_BIT];
|> |> 
|> |>   # define    BIT(X, Y)\
|> |>       the_array [Y][(X) / UNSIGNED_BIT].the_bits [(X) % UNSIGNED_BIT]

|> Upon further reflection, I now am more inclined toward the following:

|>  struct {
|>      unsigned b [800][800]:1;
|>  } the_array;

So what does your compiler have to say about it?  According to all of
the documation I've read (including ISO 9899), bit fields must have
integral types.  And an array is not an integral type.

I've generally used the following macros (BM: Bit Map):

    #define BM_SIZE( n )        ((n) / CHAR_BITS + ((n) % CHAR_BITS != 0))
    #define BM_ISSET( b , n )   \
        (((b)[ (n) / CHAR_BITS ] & (1 << ((n) % CHAR_BITS))) != 0)
    #define BM_SET( b , n )     \
        ((b)[ (n) / CHAR_BITS ] |= (1 << ((n) % CHAR_BITS)))
    #define BM_RESET( b , n )   \
        ((b)[ (n) / CHAR_BITS ] &= ~(1 << ((n) % CHAR_BITS)))


    /*  For a bitmap of `unsigned char'                     */
    char                bm[ BM_SIZE( UCHAR_MAX + 1 ) ] ;
    memset( bm , 0 , sizeof( bm ) ) ;
    BM_SET( bm , (unsigned char)( 'a' ) ) ;
    if ( BM_ISSET( bm , (unsigned char)( 'b' ) )
        ...

Care is needed in their use, since they evaluate there arguments several
times, but I've found them quite useful in the past.
-- 
James Kanze           (+33) 88 14 49 00          email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs Bourgeois, 67000 Strasbourg, France
Conseils en informatique industrielle --
                            -- Beratung in industrieller Datenverarbeitung

vjarnot@mnw.net (Asmodeus) wrote:


>I have set up an array in the following manner (obviously I just need
>0 or 1) :

>typedef struct my_bits {
>	unsigned the_bit : 1;
>};

>my_bits the_array[800][800];

>	My question is this : I have read that some operations ( =,+,- are
>what I use) are slower when performed on bits as opposed to other
>types.  My objective is to optimize the code for speed, and I figured
>using less memory would help me do so, now I'm having doubts.  So what
>is more efficient, bits or some other type???

>				Thanks in advance for your help.


compile both cases with the "generate assembly output file"  option
and compare the assemply output, then count the cpu cycles for each of
the instructions used on each of the outputs

vjarnot@mnw.net (Asmodeus) writes:
>I have set up an array in the following manner (obviously I just need
>0 or 1) :

>typedef struct my_bits {
>	unsigned the_bit : 1;
>};

I see a struct tag, but where is the identifier that typedef is supposed
to be defining?  Surely you meant

typedef struct {
    unsigned the_bit: 1;
} my_bits;


>my_bits the_array[800][800];

I don't see the point of this.
*EVERY* C object is a whole number of bytes.
Why?  Because the standard says so.

This means that each instance of your struct occupies AT LEAST one byte.
There are many C systems on which each instance of your struct will
occupy four bytes.

You can pack bit fields within a record, but array elements CANNOT be
packed tighter than bytes in C.

>	My question is this : I have read that some operations ( =,+,- are
>what I use) are slower when performed on bits as opposed to other >types.

Completely bogus.  Operations such as + and - are not performed on bits
at all.  As soon as you mention a bitfield, such as

	the_array[10][20].the_bit

the spell causes it to materialise as an 'unsigned' (if you had declared
the bit field as "signed int the_bit: 1;" it would have materialised as
a 'signed int').  + and - then operate on the unsigned value just as they
normally would.

A better way to think about it is that LOADING and STORING bit fields
may be slower than loading or storing normal arithmetic values; on the
other hand it may not be.

>My objective is to optimize the code for speed, and I figured
>using less memory would help me do so, now I'm having doubts.  So what
>is more efficient, bits or some other type???

Packing to the bit level is a good way to optimise SPACE but a truly
dreadful way to optimise TIME, particularly when you aren't even optimising
space in the first place.

A good compromise would be to use

	typedef char my_bit;

	my_bit the_array[800][800];

Be warned that some modern machines are not particularly speedy with
objects smaller than a word (think "Alpha"), so that

	#ifdef	CHAR_IS_SLOW
	typedef int my_bit;
	#else
	typedef char my_bit;
	#endif
	my_bit the_array[800][800];

might be better.

-- 
Result of state election = 50% Victorians didn't get MP of their choice.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.

schwarz@mips.complang.tuwien.ac.at (Konrad Schwarz) writes:
>Upon further reflection, I now am more inclined toward the following:

>	struct {
>		unsigned b [800][800]:1;
>	} the_array;

*Sigh*.  This is not legal C.

The standard says (Section 6.2.1, Semantics paragraph 5) that
	"A bit field shall have a type that is a qualified or
	unqualified version of one of int, unsigned int, or signed int."

The type here is "array [800] of array [800] of unsigned int", so this
is not legal.

There is *NO* way of directly getting a packed array of bits yourself
in standard C (or C++).  You will _have_ to program it yourself using
shifts and masks.

>Furthermore, in yesterdays posting making the size of the cell sizeof (unsigned)
>is arbitrary; in particular, it has nothing to do with the fact that the
>type of the bitfield is unsigned.  In the environment I am currently
>computing in, a cell size of sizeof (void *) would be more likely to make
>the cell size equal to the machine word length.

There are machines in which sizeof (void *) greatly exceeds the size of
any integral type.  If you want a packed array of bits, you will need
a plain array whose elements are of some integral type; it will be
simpler if they are unsigned.  The reasonable implementations are

	#define round_up(x,t) (((x) + (CHAR_BIT * sizeof (t) - 1)) \
			      / (CHAR_BIT * sizeof (t)) )

	unsigned char  uc[round_up(x, unsigned char)];

	unsigned short us[round_up(x, unsigned short)];

	unsigned int   ui[round_up(x, unsigned int)];

	unsigned long  ul[round_up(x, unsigned long)];

--- modulo mistakes in the round_up() macro ---
and the best of them is probably the third.

-- 
Result of state election = 50% Victorians didn't get MP of their choice.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.

Richard A. O'Keefe (ok@cs.rmit.edu.au) wrote:

> Packing to the bit level is a good way to optimise SPACE but a truly
> dreadful way to optimise TIME, particularly when you aren't even optimising
> space in the first place.

Packing to bit level can be a good way both to optimize space and time, in
suitable circumstances. A trivial example is that if your application only
require (a multiple of) boolean operations you can do 32 of them at the
same time in a 32 bit machine by using bitwise operations, performing
32-times faster. (No optimizing compiler can do this for you, unluckily.)
A more crazy application pack 8 nibbles to the same word and the only
thing he want to do to it is to add up them nibble by nibble as unsigned
integers and there's guaranteed to be no overflow. This is done 8 times
faster (in a routine in a MPEG encoder). I also see a program which pack
the whole row of a scene of reversi (or othello, whatever you call it)
in a 8-bit char, so that he can use a precalculated array to find the
leftmost bit set and rightmost bit set in single cycle rather than some
dozens. The craziest one I've seen is one from the Sun strlen() routine,
which pack 4 characters in a single memory word and use boolean
operations to test whether there's a 0 in any of the characters, allowing
a 10% increase in performance (as compared to loading the word and extract
the characters one by one within memory) and also allowing speedup if
memory word size grow.

Of course, no one will use such tricks everywhere (or you'll have perfect
secure code by obscurity :>), but in the bottleneck of a loop everything
would be exploited. Of course, relying in compiler support for this is, I
believe, stupid.

--
/-----------------------------------v
|Isaac To, kar-keung                |
|MPhil, Computer Science            |
|Mail: mailto:kkto@cs.hku.hk        |
|      mailto:kkto@hkusub.hku.hk    |
|      mailto:h9206479@hkuxa.hku.hk |
|URL: http://www.cs.hku.hk/~kkto    |
\-----------------------------------^

In article <4jr74b$h95@solutions.solon.com>, ok@cs.rmit.edu.au (Richard A. O'Keefe) writes:

[catches my error] Just checking if you're all awake! :)

|> >Furthermore, in yesterdays posting making the size of the cell sizeof (unsigned)
|> >is arbitrary; in particular, it has nothing to do with the fact that the
|> >type of the bitfield is unsigned.  In the environment I am currently
|> >computing in, a cell size of sizeof (void *) would be more likely to make
|> >the cell size equal to the machine word length.
|> 
|> There are machines in which sizeof (void *) greatly exceeds the size of
|> any integral type.

Rumour has it that the AS/400 uses pointers of length 128 bytes, which contain
not only addressing information but capabilities as well.
How is C implemented on such a machine, in particular, how are pointers
or arrays implemented?  (If the full 128 bytes are accessed for every pointer
and there is no such integral type, it must be fantastically slow.)

Konrad Schwarz

In article <4jq1dc$a1g@solutions.solon.com>,
richard mross <uar@southwind.net> wrote:
>compile both cases with the "generate assembly output file"  option
>and compare the assemply output, then count the cpu cycles for each of
>the instructions used on each of the outputs

Someone should note that this approach really only works for extremely
simple systems (no virtual memory, no cache, no superscalar, etc.).
These performance enhancers also add a lot of variability to how
long a given instruction takes.  Someone who is good enough to be
able to predict cache hit rates (and how they will affect the
performance of the code) from a static analysis of the assembly
output probably wouldn't be posting here asking which approach
was more efficient.  For most people, actual measurement of the
run time on the intended hardware is a better way to go.
-- 
Dave Wallace		(wallace@netcom.com)

kkto@csd.hku.hk (Isaac To ~{6E<RG?~}) writes:

>A more crazy application pack 8 nibbles to the same word and the only
>thing he want to do to it is to add up them nibble by nibble as unsigned
>integers and there's guaranteed to be no overflow. 
  
I would assume that a nibble is a subdivision of a byte.  
But just out of curiosity, exactly how much *is* a nibble? 
  
                       - Kevin JaY Miller 
 `  

I wrote, in connection with a failed attempt to obtain
ELEMENT-WISE access to a packed array of bits, that

>> Packing to the bit level is a good way to optimise SPACE but a truly
>> dreadful way to optimise TIME, particularly when you aren't even optimising
>> space in the first place.

kkto@csd.hku.hk (Isaac To ~{6E<RG?~}) writes:

>Packing to bit level can be a good way both to optimize space and time, in
>suitable circumstances.

but shifts the grounds of comparison to *successful* packing of sets
and doing SET-WISE operations.  That is a *very* different matter, because
(a) word-at-a-time operations do 16 or 32 or 64 or however many
    element operations in parallel
(b) the packing is effective (the method I was discussing is not)
(c) element-wise access to bits has overhead:

	b = a[i];
=>
	r1 := i				-- bit index
	r2 := r1 >> 3			-- byte index
	r1 := r1 & 7			-- bit within byte
	r2 := Byte[a + r2]		-- fetch byte
	r2 := r2 >> r1			-- shift so bit is in bit 0
	r2 := r2 & 1			-- isolate required bit
	b  := r1

    Contrast this with access to a byte:

	r2 := i
	r2 := Byte[a + r2]
	b  := r2

    Ignoring the initial fetch of "i" and the store to "b", because they
    may be bound to registers anyway, and the compiler can probably 
    eliminate those instructions, we find that

    ELEMENT-WISE fetch from a packed bit array has about 4 cycles of
    overhead compared with ELEMENT-WISE fetch from a byte array.

(d) In favour of set-wise operations, I note that byte access itself is
    expensive on some machines.


Note the following trick for walking through an array of unsigned longs,
processing each bit.  It assumes that each bit in the array is used.

	void walk_bits_in_ulongs(
	    unsigned long const *base,
	    unsigned             nwords,
	    void (*f)(unsigned /*bitno*/, int /*bit*/)
	) {
	    unsigned bitno;
	    unsigned i;

	    for (bitno = 0, i = 0; i < nwords; i++) {
		unsigned long const word = base[i];
		unsigned long mask;

		for (mask = 1; mask != 0; mask <<= 1, bitno++)
		    f(bitno, (word & mask) != 0);
	    }
	}

Again, the saving comes about because we are NOT fetching bits in a
true ELEMENT-WISE fashion, but in groups.

It is also worth noting that some machines have bit load, store, &c
operations.  Where would the 8051 be without them?  Bit packing makes
a lot of sense in such a case.  Not in portable C.

-- 
Result of state election = 50% Victorians didn't get MP of their choice.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.

In article <4k1q4o$5cn@solutions.solon.com> kjm@quirk.physics.ucsb.edu
( Kevin Miller) writes:

> kkto@csd.hku.hk (Isaac To ~{6E<RG?~}) writes:

>> A more crazy application pack 8 nibbles to the same word and the
>> only thing he want to do to it is to add up them nibble by nibble
>> as unsigned integers and there's guaranteed to be no overflow.

> I would assume that a nibble is a subdivision of a byte.  But just
> out of curiosity, exactly how much *is* a nibble?

A nibble is half a byte, or 4 bits.  It was frequently used on Apple
II computers, although I don't remember why.

Just a Thought,
Jim Trigg

Kevin Miller (kjm@quirk.physics.ucsb.edu) wrote:
: kkto@csd.hku.hk (Isaac To ~{6E<RG?~}) writes:

: >A more crazy application pack 8 nibbles to the same word and the only
: >thing he want to do to it is to add up them nibble by nibble as unsigned
: >integers and there's guaranteed to be no overflow. 
:   
: I would assume that a nibble is a subdivision of a byte.  
: But just out of curiosity, exactly how much *is* a nibble? 

Half a byte (4 bits).  I remember the term from programming 8 bit
CPUs; one would often store information in the "high nibble" and
"low nibble" much the same way one uses the high and low bytes on
16 bit CPUs.  For example, one of the reasons 16 colors was popular on
8 bit CPUs was that foreground/background colors for a point fit
nicely into one byte that way (one color in the high nibble, one in
the low).

I haven't heard the term in _ages_, though.  Maybe 10 years?  Help me!
I'm not old enough to feel old!

---------------------------------------------------------------------------
Tim Hollebeek         | Disclaimer :=> Everything above is a true statement,
Electron Psychologist |                for sufficiently false values of true.
Princeton University  | email: tim@wfn-shop.princeton.edu
----------------------| http://wfn-shop.princeton.edu/~tim (NEW! IMPROVED!)

On 4 Apr 1996, Kevin Miller wrote:

> I would assume that a nibble is a subdivision of a byte.  
> But just out of curiosity, exactly how much *is* a nibble? 
>   

A bit less than a handfull, meaning 4 bits ... 

Richard A. O'Keefe (ok@cs.rmit.edu.au) wrote:
: [ bitset operations ]

: Note the following trick for walking through an array of unsigned longs,
: processing each bit.  It assumes that each bit in the array is used.

: 	void walk_bits_in_ulongs(
: 	    unsigned long const *base,
: 	    unsigned             nwords,
: 	    void (*f)(unsigned /*bitno*/, int /*bit*/)
: 	) {
: 	    unsigned bitno;
: 	    unsigned i;

: 	    for (bitno = 0, i = 0; i < nwords; i++) {
: 		unsigned long const word = base[i];
: 		unsigned long mask;

>>>             if (!word) continue;

: 		for (mask = 1; mask != 0; mask <<= 1, bitno++)
: 		    f(bitno, (word & mask) != 0);
: 	    }
: 	}

: Again, the saving comes about because we are NOT fetching bits in a
: true ELEMENT-WISE fashion, but in groups.

The above trick inserted (>>>) is a good one to remember when working
with bitsets.  On many CPUs, the above check is essentially 'free',
since it just depends on a condition flag that gets set when the value
is loaded anyway.

Intersection and union, of course, are very efficient (just use & and
|) in terms of bitsets.

Of course, you can do even better than that.  I timed a similar
algorithm on a wide variety of architectures, and the following
algorithm won for finding the set bit in a bitfield (or giving an
error if more than one is set):

static int get_single(unsigned int *, bv) {
    int i, res = -1;

    for (i = 0; i < NUM_BITVEC_INTS; i++) {
        if (bv[i]) { /* test 16 bits at a time! */
            if (res != -1) return -1;
	    res = i;
        }
    }
    if (res == -1) return res;

    i = bv[res];
    /* Binary search for the set bit, unrolled for speed. */
    if (i & 0x0000ffff) {
        if (i & 0xffff0000)
            return -1;
    } else {
        i >>= 16;
        res += 16;
    }

    if (i & 0x00ff) {
        if (i & 0xff00)
            return -1;
    } else {
        i >>= 8;
        res += 8;
    }
    
    if (i & 0x0f) {
        if (i & 0xf0)
            return -1;
    } else {
        i >>= 4;
        res += 4;
    }
    
    if (i & 0x3) {
        if (i & 0xc)
            return -1;
    } else {
        i >>= 2;
        res += 2;
    }
    
    if (i & 0x1) {
        if (i & 0x2)
            return -1;
	return res;
    } else {
        return res + 1;
    }
}

If you're wondering why the shifts are there, remember shifts are
cheap, and it turns out the full 32 bit integer constants (like
0xaaaaaaaa) appear to be rather slow on many RISC CPUs, so it's faster
to reduce the problem to one involving smaller constants.

Similar tricks for counting bits exist; I think the C FAQ has some of them.

---------------------------------------------------------------------------
Tim Hollebeek         | Disclaimer :=> Everything above is a true statement,
Electron Psychologist |                for sufficiently false values of true.
Princeton University  | email: tim@wfn-shop.princeton.edu
----------------------| http://wfn-shop.princeton.edu/~tim (NEW! IMPROVED!)