Finding number of bits of integer

R

Richard Heathfield

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.
 
V

vipvipvipvip.ru

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'.
 
B

Ben Bacarisse

Richard Heathfield said:
Daniel Kraft said:
The usual way to implement a "bit array", though, is as follows:
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.
 
R

Richard Heathfield

Ben Bacarisse said:

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.
 
E

Erik Trulsson

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.
 
D

Daniel Kraft

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
 
M

Martin Wells

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
 
M

Martin Wells

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
 
M

Martin Wells

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
 
D

Daniel Kraft

I do need to implement something similar to C++'s std::bitset in C;
The usual way to implement a "bit array", though, is as follows:
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.

Hm... Actually I was thinking of using int's, as the main operations in
my case are not accessing individual bits but rather doing binary and's
and or's on the whole bitset--I know, premature optimization... but it
seems to me to be much cleaner and probably "faster" to use ints for
this instead of chars (always unsigned, of course).

So is there a way to get the number of *usable* bits of a single
unsigned? Or should I use unsigned chars and do the binary operations
per-char instead of per-int?

Cheers,
Daniel
 
D

Daniel Kraft

I think of something like
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).

Of course, I also thought about calculating this once at runtime (which
is easy and should not cost much), but of course a compile-time constant
is much better--with C++ template meta-programming this shouldn't be
hard to solve, but with the C preprocessor it could get a bit trickier...

However, thanks for this nice macro! I think I can put it into
something I can use (because I do have some restrictions on which bits
are really usable for me).

Cheers,
Daniel
 
R

Richard Heathfield

Daniel Kraft said:

So is there a way to get the number of *usable* bits of a single
unsigned?

Sure. UINT_MAX has to be one less than a power of 2, so you can do this
(once only will do):

#include <limits.h>

int count_value_bits_in_unsigned_int(void)
{
int rv = 0;
unsigned int n = UINT_MAX;
while(n > 0)
{
++rv;
n >>= 1;
}
return rv;
}
Or should I use unsigned chars and do the binary operations
per-char instead of per-int?

Well, I would, but it's up to you.
 
P

pete

Richard said:
Daniel Kraft said:



Sure. UINT_MAX has to be one less than a power of 2,
so you can do this (once only will do):

#include <limits.h>

int count_value_bits_in_unsigned_int(void)
{
int rv = 0;
unsigned int n = UINT_MAX;
while(n > 0)
{
++rv;
n >>= 1;
}
return rv;
}

rv should be type unsigned, instead of type int.
The number of value bits in type unsigned isn't
guaranteed to be representable as an int type value.
 
P

Peter Pichler

pete said:
rv should be type unsigned, instead of type int.
The number of value bits in type unsigned isn't
guaranteed to be representable as an int type value.

Can you name one architecture with more than 32767 value bit
in unsigned?
 
K

Keith Thompson

Daniel Kraft said:
Of course, I also thought about calculating this once at runtime
(which is easy and should not cost much), but of course a compile-time
constant is much better--with C++ template meta-programming this
shouldn't be hard to solve, but with the C preprocessor it could get a
bit trickier...

However, thanks for this nice macro! I think I can put it into
something I can use (because I do have some restrictions on which bits
are really usable for me).

Another possibility is to write a small C program that computes the
number of value bits and writes out a valid C header file that
declares it as a macro. You can then include this generated header
file in your program.

You'll have to have some mechanism for compiling and executing this
small program as part of your build procedure. Doing so is beyond the
scope of C, but shouldn't be difficult for a "make"-like tool -- *if*
you're compiling on the same system where you're going to run the
program. If you're cross-compiling, things get a bit trickier.

Or you can maintain it manually, but that's error-prone.
 
R

Richard Heathfield

pete said:
rv should be type unsigned, instead of type int.
The number of value bits in type unsigned isn't
guaranteed to be representable as an int type value.

We can deduce from the standard that it is representable as an int type
value. The int type uses the same amount of storage as the unsigned int
type, and has the same alignment requirements. Given that UINT_MAX must be
representable as an unsigned int, and given that it must be at least 65535
(at which point rv can be at most 16), and given that n grows very much
faster than log2(n), it follows that rv will grow very slowly.

Since int must be capable of storing the value 32767, my little function
will work on any system with unsigned ints containing 32767 value bits -
that is, even if there were a disparity between the number of the value
bits in the two types so great that INT_MAX were 32767 and UINT_MAX were 1
less than 2 to the power 32767 (a number so large I hesitate to post it
here!), my function would still cope.

And with each extra value bit in an int, you more than double the UINT_MAX
it can cope with.

An implementation on which my function did not work would not merely be
run-of-the-mill clc-style pathological. It would be psychopathological.
 
M

Martin Wells

pete:
rv should be type unsigned, instead of type int.
The number of value bits in type unsigned isn't
guaranteed to be representable as an int type value.


While we're making ridiculous critiques, the most blatantly obvious
flaw if you ask me is the use of a "while" instead of a "do".

As for signed integer types Vs unsigned integer types, I default to
unsigned rather than signed.

My own function would've been something like:

unsigned VRbitsInUInt(void)
{
unsigned vr = 16;

unsigned x = 0x8000u;

while (x <<= 1) ++vr;

return vr;
}

Or a more generic one (if we pretend we can pass a type):

template <typename UIntType>
unsigned VRbitsUIntType(void)
{
unsigned vr = 8;

UIntType x = 0x80u;
while (x <<= 1) ++vr;

return vr;
}

Martin
 
P

pete

Richard said:
pete said:


We can deduce from the standard
that it is representable as an int type value.
An implementation on which my function
did not work would not merely be
run-of-the-mill clc-style pathological.
It would be psychopathological.

You can't have it both ways.

If you can deduce from the standard that it
is representable as an int type value,
then there can't be an implementation,
psychopathological or otherwise,
where your function won't work.
 
?

=?iso-2022-kr?q?=1B=24=29CHarald_van_D=0E=29=26=0F

You can't have it both ways.

If you can deduce from the standard that it is representable as an int
type value, then there can't be an implementation, psychopathological or
otherwise,
where your function won't work.

The standard doesn't guarantee that

int main(int argc, char *argv[])
{
return 0;
}

will work, since it declares two objects whose size is allowed to be
greater than 65535 bytes. This is already taking the environmental limits
to the extreme. A hosted implementation on which
UINT_MAX > (1 << INT_MAX) - 1
would require sizeof(int) to not only simply equal or exceed 2^16, but to
equal or exceed 2^32752. A freestanding implementation might be able to
get it done with a lower number of bytes, by using excessively large
bytes, but it would still require such an utterly insane implementation
that you're better off worrying about clowns breaking into your house,
doing a silly dance, and leaving with your toilet paper.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top