Daniel Kraft said:

> Hi,
>
> I do need to implement something similar to C++'s std::bitset in C; for
> this, I use an array of int's to get together any desired number of
> bits, possibly larger than 32/64 or anything like this.
>
> So of course it does not matter how many bits a single int has, but I do
> need a reliable way to find it out.
>
> I think of something like
> CHAR_BITS*sizeof(int)
> will do the trick, am I right here?

Well, you mean CHAR_BIT, but yes, that will give you the total number of
bits occupied by the int - including the sign bit, at least (but possibly
more than) 15 value bits, and at least (but possibly more than) no padding
bits.

> I'm just confused that it is *CHAR*_BITS; in reference to the usual
> example, there are some machines where char's have 9 bits--but is in
> this case int required to have some multiple of 9 bits, too?

Yes, CHAR_BIT gives the number of bits in a char, and a char is exactly one
byte wide, and every object must be a whole number of bytes wide. If
CHAR_BIT is 9, then objects must be a multiple of 9 bits wide.

The usual way to implement a "bit array", though, is as follows:

1) decide how many bits, B, you want your array to have (if you decide this
at runtime, you'll need to allocate the memory in step 2 dynamically,
check that you've got it, and release it when you're done);
2) allocate (B + CHAR_BIT - 1) / CHAR_BIT bytes (unsigned char foo[N] = {0}
or unsigned char *foo = calloc((B + CHAR_BIT - 1) / CHAR_BIT, 1),
initialising it all to 0 (you can use = {0} unless you allocate
dynamically, in which case use calloc - one of the rare occasions where
this is a good idea);
3) use macros to get, set, and test individual bits.

http://www.snippets.org has some macros that can be used for this purpose.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

It is CHAR_BIT and not CHAR_BITS, ignoring that, if sizeof(anything)
== 2
we know that it's twice the size of a `char'.

Richard Heathfield <rjh@see.sig.invalid> writes:

> Daniel Kraft said:
>
>> I do need to implement something similar to C++'s std::bitset in C;
<snip>
> The usual way to implement a "bit array", though, is as follows:
<snip>
> 2) allocate (B + CHAR_BIT - 1) / CHAR_BIT bytes (unsigned char
> foo[N] = {0}
<snip>

It is probably worth adding the reason one uses an unsigned integer
type is that shift operations are well-defined on these, and the
reason one uses unsigned char in particular is that it is guaranteed
not to have any padding bits.

--
Ben.

Ben Bacarisse said:

<snip>

> It is probably worth adding the reason one uses an unsigned integer
> type is that shift operations are well-defined on these, and the
> reason one uses unsigned char in particular is that it is guaranteed
> not to have any padding bits.

It is indeed worth adding. Thank you.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

vipvipvipvip.ru@gmail.com wrote:
> It is CHAR_BIT and not CHAR_BITS, ignoring that, if sizeof(anything)
> == 2
> we know that it's twice the size of a `char'.

Yes, but we do not know that it contains twice as many 'usable' bits.

E.g. one could have

CHAR_BIT == 9
sizeof(int) == 2
INT_MIN == -32767
INT_MAX == 32767

and it would be perfactly fine as far as the C standard is concerned.
In this case an int would occupy 18 bits, but 2 of those bits would
be padding and such an int would not be able to hold than a 16-bit wide
int without padding would.




--
<Insert your favourite quote here.>
Erik Trulsson
ertr1013@student.uu.se

Hi,

I do need to implement something similar to C++'s std::bitset in C; for
this, I use an array of int's to get together any desired number of
bits, possibly larger than 32/64 or anything like this.

So of course it does not matter how many bits a single int has, but I do
need a reliable way to find it out.

I think of something like
CHAR_BITS*sizeof(int)
will do the trick, am I right here?

I'm just confused that it is *CHAR*_BITS; in reference to the usual
example, there are some machines where char's have 9 bits--but is in
this case int required to have some multiple of 9 bits, too? I.e., does
sizeof(something) always give the size of this as multiples of
sizeof(char) or could such a 9 bit char be paired with 16/32 bit integers?

Thank you very much,
Daniel

--
Got two Dear-Daniel-Instant Messages
by MSN, associate ICQ with stress--so
please use good, old E-MAIL!

Daniel:

> I think of something like
> CHAR_BITS*sizeof(int)
> will do the trick, am I right here?


What you're looking for is the quantity of "value representational
bits". These are the bits that actually take place in arithmetic and
bit-shifting, and they are distinct from the other two varieties of
bits that can be present in an int type (i.e. the single sign bit and
the padding bits). On most systems, integer types don't have
padding... but the Standard permits that they may, which is why in
fully-portable programming you should shy away from
sizeof(unsigned)*CHAR_BIT for getting the VR bits.

The C Standard doesn't provide an operator or macro or anything for
determing the quantity of VR bits, but such a macro can be "own-
rolled". Of course, you can use a simple loop to work it out, but it's
a little trickier to get the figure as a compile-time constant (e.g.
for use in array dimensions).

A chap called Hallvard B Furuseth, (a genius if you ask me), devised a
macro called IMAX_BITS that's used for determing the amount of bits
you need to represent a given number, and he has it as a compile time
constant. (The only restriction is that the "given number" must be all
one's in binary: e.g. 1111, or 11111, or 111111). Given that the
highest number for any unsigned integer type will always be all-one's,
we can use this macro. Here's an example:

Quantity of value bits in unsigned short = IMAX_BITS(USHRT_MAX)

I've reshaped Hallvard's macro so that it can be used in the following
form:

Quantity of value bits in unsigned short = VALUE_BITS_UINT(unsigned
short)

The macro is a follows:

#define VALUE_BITS_UINT(my_type) (((my_type)-1) /
(((my_type)-1)%0x3fffffffL+1) \
/0x3fffffffL %0x3fffffffL *30 \
+ ((my_type)-1)%0x3fffffffL \
/(((my_type)-1)%31+1)/31%31*5 + 4-12/(((my_type)-1)%31+3))

Don't ask me how it works coz I haven't a clue. What I do know is that
it's tried and tested and definitely does work.

There's probably a way of getting the VR bits for a signed type also
but to be honest I've no interest in it because I shudder at the
thought of using signed types for bit manipulation.

Best of luck.

Martin

Daniel:

> I think of something like
> CHAR_BITS*sizeof(int)
> will do the trick, am I right here?


What you're looking for is the quantity of "value representational
bits". These are the bits that actually take place in arithmetic and
bit-shifting, and they are distinct from the other two varieties of
bits that can be present in an int type (i.e. the single sign bit and
the padding bits). On most systems, integer types don't have
padding... but the Standard permits that they may, which is why in
fully-portable programming you should shy away from
sizeof(unsigned)*CHAR_BIT for getting the VR bits.

The C Standard doesn't provide an operator or macro or anything for
determing the quantity of VR bits, but such a macro can be "own-
rolled". Of course, you can use a simple loop to work it out, but it's
a little trickier to get the figure as a compile-time constant (e.g.
for use in array dimensions).

A chap called Hallvard B Furuseth, (a genius if you ask me), devised a
macro called IMAX_BITS that's used for determing the amount of bits
you need to represent a given number, and he has it as a compile time
constant. (The only restriction is that the "given number" must be all
one's in binary: e.g. 1111, or 11111, or 111111). Given that the
highest number for any unsigned integer type will always be all-one's,
we can use this macro. Here's an example:

Quantity of value bits in unsigned short = IMAX_BITS(USHRT_MAX)

I've reshaped Hallvard's macro so that it can be used in the following
form:

Quantity of value bits in unsigned short = VALUE_BITS_UINT(unsigned
short)

The macro is a follows:

#define VALUE_BITS_UINT(my_type) (((my_type)-1) /
(((my_type)-1)%0x3fffffffL+1) \
/0x3fffffffL %0x3fffffffL *30 \
+ ((my_type)-1)%0x3fffffffL \
/(((my_type)-1)%31+1)/31%31*5 + 4-12/(((my_type)-1)%31+3))

Don't ask me how it works coz I haven't a clue. What I do know is that
it's tried and tested and definitely does work.

There's probably a way of getting the VR bits for a signed type also
but to be honest I've no interest in it because I shudder at the
thought of using signed types for bit manipulation.

Best of luck.

Martin