Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!rutgers!seismo!umcp-cs!cvl!umd5!zben
From: zben@umd5 (Ben Cranston)
Newsgroups: comp.lang.c
Subject: Re: Portable arrays of bits
Message-ID: <1353@umd5>
Date: Sun, 9-Nov-86 21:39:11 EST
Article-I.D.: umd5.1353
Posted: Sun Nov  9 21:39:11 1986
Date-Received: Mon, 10-Nov-86 05:07:08 EST
References: <140@houligan.UUCP> <8828@sun.uucp> <608@kodak.UUCP> <3862@caip.RUTGERS.EDU>
Reply-To: zben@umd5.umd.edu (Ben Cranston)
Organization: University of Maryland, College Park
Lines: 25
Summary: The shifting can cost you

In article <3862@caip.RUTGERS.EDU> brisco@caip.RUTGERS.EDU (Thomas Paul Brisco) writes:

>> Is there a standard, machine independant way of defining an array 
>> of bits?  I am writing code and do not want to have to do a function
>> call each time I reference a bit, but want a Boolean array packed
>> as tightly as possible.

> A better approach is to define a subroutine or macro as following:
> #define getbit(x,p) ((x >> p)&~(~0 << 1))

Unless your hardware has a barrel-shifter this can cost you lots of cycles.
I usually define a structure like:

char bitsmask[8] = { 1, 2, 4, 8, 16, 32, 64, 128 };

and do operations like:   if ( x[p/8] & bitsmask[p%8] ) ...
or setting them like:     x[p/8] |= bitsmask[p%8];

The idea is that an 8 byte table is cheap, and is perhaps faster than a
shift instruction.  I have done this with a 32 word table of ints as well.
It does seem to be difficult to parameterize for different word lengths tho.
-- 
                    umd5.UUCP    <= {seismo!umcp-cs,ihnp4!rlgvax}!cvl!umd5!zben
Ben Cranston zben @ umd2.UMD.EDU    Kingdom of Merryland Sperrows 1100/92
                    umd2.BITNET     "via HASP with RSCS"