fsb@vitro.uucp (Steve Brailsford) (10/08/90)
This talk about how many bits set in a long has reminded me of a
problem I have with finding a good efficient, fast storage
mechanism for storing 100 boolean flags. Basically, I have
am algorithm that needs to mark one of 100 flags true, (after
they have all been inited to false.) And then to scan through
the flags to perform operations on those that get set. I set
aside an array of 100 chars and just set each one to 0 or 1.
I couldn't think of a way to use 100 bits worth of storage
without it getting really hairy computationally. If I use
enums and test some location, locations are maxed at 32 bits.
How could I find if the 33 bit was set without having some
array of longs. The problem is even more complex in the fact
that the 100 comes from 10x10, a defined size. If I say it's
now 20x20, I would have to write the 100 bit test stuff all over.
Anyone done anything like this?
Steve Brailsford Usenet: uunet!media!vitro!fsb
Vitro Corporation Compu$erve: 73427,1466
14000 Georgia Ave. Voice: (301) 231-1481
Silver Spring, MD 20906
--
Steve Brailsford Usenet: uunet!media!vitro!fsb
Vitro Corporation Compu$erve: 73427,1466
14000 Georgia Ave. Voice: (301) 231-1481bruce@seismo.gps.caltech.edu (Bruce Worden) (10/10/90)
In article <1990Oct8.165154.26747@vitro.uucp> fsb@vitro.uucp (Steve Brailsford) writes: > [ looking for a way to set and test boolean flags ] I don't know what you consider to be too computationally intensive, but you might want to look at the way the macros that support the "select()" function provide the exact (almost) functionality you are looking for. Four macros (with some supporting code) are provided: FD_SET, FD_CLR, FD_ISSET, and FD_ZERO. It should be a simple matter to modify them to work for any sized string of bits. They are defined in <sys/types.h>. Good luck. (Note, the select() function itself is of no interest here, just the macros that support it. If you don't have these macros, and you send my a working e-mail address, I'll send you some non-copyright-infringing copies.) -------------------------------------------------------------------------- C. Bruce Worden bruce@seismo.gps.caltech.edu 252-21 Seismological Laboratory, Caltech, Pasadena, CA 91125
rmacgreg@cs.strath.ac.uk (Sorcerer) (10/10/90)
I don't know if this will work, never having tried it myself, but C allows
for bitfields in structs. Normally these are just a couple of bits, but I
see no reason why you couldn't define a bitfield to be 100 bits long.
There has to be a problem with this as it sounds to simple, but you never
know... :-)
___
_____ / (rmacgreg @ uk.ac.strath.cs)
| |__ __ /___ ___ ___ ___ ___ ___ ___ ___
| | | |__| / / / / / / /__/ / / /__/ / /
| | | |__ ___/ /__/ / /__ /__ / /__ /
is 'Only visiting this planet.'karl@haddock.ima.isc.com (Karl Heuer) (10/11/90)
In article <4811@baird.cs.strath.ac.uk> rmacgreg@cs.strath.ac.uk (Sorcerer) writes: >I don't know if this will work, never having tried it myself, Wouldn't it have been easier to try it than to post this message around the world? >I see no reason why you couldn't define a bitfield to be 100 bits long. (a) It's not allowed by ANSI, K&R, or common practice. (b) Even if it were, it wouldn't work. What's really needed is an *array* of bitfields, which is illegal because of a technicality related to the array and pointer duality. Karl W. Z. Heuer (karl@ima.isc.com or harvard!ima!karl), The Walking Lint
userAKDU@mts.ucs.UAlberta.CA (Al Dunbar) (10/11/90)
In article <4811@baird.cs.strath.ac.uk>, rmacgreg@cs.strath.ac.uk (Sorcerer) writes: >I don't know if this will work, never having tried it myself, It must have seemed a particularly onerous task ... :-) > but C allows >for bitfields in structs. Normally these are just a couple of bits, but I >see no reason why you couldn't define a bitfield to be 100 bits long. > >There has to be a problem with this as it sounds to simple, but you never >know... :-) > > ___ > _____ / (rmacgreg @ uk.ac.strath.cs) > | |__ __ /___ ___ ___ ___ ___ ___ ___ ___ > | | | |__| / / / / / / /__/ / / /__/ / / > | | | |__ ___/ /__/ / /__ /__ / /__ / > > is 'Only visiting this planet.' Here are a couple of possible reasons: K&R2: "Fields behave like small, unsigned integers, and may participate in arithmetic expressions just like other integers." K&R2: "A field may not overlap an int boundary..." K&R2: "... they may be stored only in int's (or, equivalently, unsigned's ..." How would you declare a bitfield wider than the widest available int? -------------------+------------------------------------------- Al Dunbar | Edmonton, Alberta | this space for rent CANADA | -------------------+-------------------------------------------
peted@microsoft.UUCP (Peter DUNIHO) (10/12/90)
In article <1990Oct8.165154.26747@vitro.uucp>, fsb@vitro.uucp (Steve Brailsford) writes: > problem I have with finding a good efficient, fast storage > mechanism for storing 100 boolean flags. Basically, I have > I couldn't think of a way to use 100 bits worth of storage > without it getting really hairy computationally. If I use > enums and test some location, locations are maxed at 32 bits. > How could I find if the 33 bit was set without having some > array of longs. The problem is even more complex in the fact > > Steve Brailsford Usenet: uunet!media!vitro!fsb Well, I think it would be okay to use an array of longs (or chars, if you want to minimize wasted space). Just define a macro like this: #define BIT_SET(bitfield,bit) (bitfield[bit/sizeof(*bitfield)] & \ (0x01 << (bit % sizeof(*bitfield)))) Just off the top of my head (which often times gets me the wrong answers :) ), I think that oughta work with a minimum of trouble to you. It's easily modifed to handle larger bitfields - or, more precisely, it doesn't need to be modifed to handle larger bitfields. The data types would be unsigned long bitfield[4] /* or */ unsigned char bitfield[13]; and int bit; This could be tweaked as you need it to be...the macro will return the value of the bit (well, set will be non-zero, unset will be zero). Other macros to set the bits or do whatever else are similar. Pete D.
rmacgreg@cs.strath.ac.uk (Sorcerer) (10/16/90)
> >K&R2: "... they may be stored only in int's (or, equivalently, >unsigned's ..." > >How would you declare a bitfield wider than the widest >available int? > Good question... I dunno, but maybe (just maybe) those nice people at ANSII decided to change it so you could have bitfields as large as you like (not very probable, but you never know) :-) ___ _____ / (rmacgreg @ uk.ac.strath.cs) | |__ __ /___ ___ ___ ___ ___ ___ ___ ___ | | | |__| / / / / / / /__/ / / /__/ / / | | | |__ ___/ /__/ / /__ /__ / /__ / is 'Only visiting this planet.'