array of bits

I feel like I might be overlooking something obvious, but...

I want to store an array of bits (0's and 1's) in the cheapest possible way.
The array might be 1,000 to 10,000 elements long. What variable type/
structure should I use?

Thanks!

re: array of bits

"Darius Fatakia" <darius_fatakia@yahoo.com> writes:
[color=blue]
> I feel like I might be overlooking something obvious, but...
>
> I want to store an array of bits (0's and 1's) in the cheapest possible way.
> The array might be 1,000 to 10,000 elements long. What variable type/
> structure should I use?[/color]

Use an array of integer type (`unsigned char' or `unsigned int',
for instance), then use bitwise operators to access individual
bits.
--
"Given that computing power increases exponentially with time,
algorithms with exponential or better O-notations
are actually linear with a large constant."
--Mike Lee

re: array of bits

On Thu, 15 Jan 2004 17:38:19 -0800, "Darius Fatakia"
<darius_fatakia@yahoo.com> wrote in comp.lang.c:
[color=blue]
> I feel like I might be overlooking something obvious, but...
>
> I want to store an array of bits (0's and 1's) in the cheapest possible way.
> The array might be 1,000 to 10,000 elements long. What variable type/
> structure should I use?
>
> Thanks!
>[/color]

You must have somehow missed this question (and its answer) when you
read the FAQ for this group, as you are supposed to and surely did
before you posted here:

20.8 How can I implement sets or arrays of bits?

There's a link to the FAQ for comp.lang.c, which includes the answer
to this question as well as many, many others, in my signature block.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html

re: array of bits

Darius Fatakia wrote:[color=blue]
>
> I feel like I might be overlooking something obvious, but...[/color]

It's called the FAQ.
[color=blue]
>
> I want to store an array of bits (0's and 1's) in the cheapest
> possible way. The array might be 1,000 to 10,000 elements long.
> What variable type/ structure should I use?[/color]

Something that can hold 10,000 bits. I suggest you start with:

#define BITCOUNTMAX 10000

and go on from there. Define cheap.

--
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

re: array of bits

Jack Klein wrote:[color=blue]
> On Thu, 15 Jan 2004 17:38:19 -0800, "Darius Fatakia"
> <darius_fatakia@yahoo.com> wrote in comp.lang.c:[/color]

[color=blue][color=green]
>>I want to store an array of bits (0's and 1's) in the cheapest possible way.
>>The array might be 1,000 to 10,000 elements long. What variable type/
>>structure should I use?[/color][/color]
[color=blue]
> You must have somehow missed this question (and its answer) when you
> read the FAQ for this group, as you are supposed to and surely did
> before you posted here:
>
> 20.8 How can I implement sets or arrays of bits?
>
> There's a link to the FAQ for comp.lang.c, which includes the answer
> to this question as well as many, many others, in my signature block.[/color]

He didn't just ask how he can implement array of bits, but
how to do it in the cheapest way.

Unfortunately he didn't say what cheap was.

On some machines the fastest (cheapest execution time) is to store
each bit in a single char or int array element.

Cheapest in memory used is to use the logical operators and
store the appropriate number of bits in an unsigned char or
unsigned int array element.

You might need to try both to see which is best on your machine.

-- glen

re: array of bits

"Jack Klein" <jackklein@spamcop.net> wrote:[color=blue]
> You must have somehow missed this question (and its answer)
> when you read the FAQ for this group, as you are supposed
> to and surely did before you posted here:
>
> 20.8 How can I implement sets or arrays of bits?[/color]

The macros given in the FAQ:
#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITSLOT(b) ((b) / CHAR_BIT)
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))

Seem to be missing a way to clear a bit?
#define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))

May as well add a toggler too:
#define BITFLIP(a, b) ((a)[BITSLOT(b)] ^= BITMASK(b))

--
Simon.