Finding number of bits of integer

[Richard Heathfield]

pete said:

Richard Heathfield wrote:

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.

Yes, I think I wrote that one as I was going along, and forgot to go back
to edit out the claim that it is deducible. (It might yet be, but in fact
I failed to do it.)

Let's just say that I would certainly worry about the possibility of a
non-ASCII character set, I have been known to worry about the number of
bits in a byte being greater than 8, I might worry about the endianness of
a machine being different to the endianness of data in a file on that
machine, and I could even conceivably worry about the result of
right-shifting a negative value - but I would not be even slightly
concerned about the possibility of an implementation using more than
INT_MAX value bits in an unsigned int.

 

[DiAvOl]

My question is probably off-topic, but can someone please explain me
what are padding bits in an unsigned integer? (and how can affect the
code)

One more question:

This code

#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;

}

should always give 32 on a 4 byte int system, is this correct?

Thanks for your time

 

[Richard Heathfield]

DiAvOl said:

My question is probably off-topic, but can someone please explain me
what are padding bits in an unsigned integer?

They are bits that do not contribute to the value of the object, but which
are there for the convenience of the implementor (or, perhaps they are
inconveniently there, and are ignored for the convenience of the
implementor!).

Let's just say, for the sake of argument, that you wanted to write a C
compiler on a system with 8-bit bytes, and that you wanted to give a
*guarantee* to your users that any legal pointer could be converted to a
legal unsigned int and vice versa - but you only had a 28-bit address
space, i.e. 256 MB of RAM. It would be sensible to keep your byte size at
the natural size for the machine, 8 bits, and it's clear you're going to
need four bytes for an unsigned int on this system. But if *any* unsigned
int value translates to a valid pointer value and you only have 2^28
addresses, then it's clear that you're not going to be able to use the top
four bits of your unsigned int. So you'd probably define UINT_MAX as
268435455 and ignore the top four bits completely. They'd still be there,
of course, but they would not contribute to the value of the unsigned int.
In fact, you'd probably have to mask them out during calcs, just in case
some bright spark managed to set them anyway.

One more question:

This code

#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;

}

should always give 32 on a 4 byte int system, is this correct?

No, it isn't correct. Consider a "4 byte int" system with bytes that are
117 bits in size, and no padding bits. On such a system, the function will
return 468.

 

[DiAvOl]

Let's just say, for the sake of argument, that you wanted to write a C

compiler on a system with 8-bit bytes, and that you wanted to give a
*guarantee* to your users that any legal pointer could be converted to a
legal unsigned int and vice versa - but you only had a 28-bit address
space, i.e. 256 MB of RAM. It would be sensible to keep your byte size at
the natural size for the machine, 8 bits, and it's clear you're going to
need four bytes for an unsigned int on this system. But if *any* unsigned
int value translates to a valid pointer value and you only have 2^28
addresses, then it's clear that you're not going to be able to use the top
four bits of your unsigned int. So you'd probably define UINT_MAX as
268435455 and ignore the top four bits completely. They'd still be there,
of course, but they would not contribute to the value of the unsigned int.
In fact, you'd probably have to mask them out during calcs, just in case
some bright spark managed to set them anyway.

What values would those 4 top "padded bits" contain? 0 or 1?
I'm trying to figure out if padding bits affects the code in any way,
for example what if the user wanted to use those 4 top bits for
bitwise operations?

Can someone give an example how would the code be affected when
running on a system without padding bit ints and when running on one
with padding bit ?

Thanks for the above example & sorry for my bad english.

 

[Richard Heathfield]

DiAvOl said:

What values would those 4 top "padded bits" contain? 0 or 1?

One or other of those, yes.

I'm trying to figure out if padding bits affects the code in any way,
for example what if the user wanted to use those 4 top bits for
bitwise operations?

The user could actually do this, of course, simply by accessing the object
representation via type punning:

unsigned int n = some_value;
unsigned char *p = (unsigned char *)&n;
/* can now write to n's object representation via p[0] through p[(sizeof n)
- 1] */

If the user chooses to bitshift via a series of p hacks, he could, and
the padding bits would then muddy the waters. But if the user instead
shifted the unsigned int itself, well, that's a value-based operation, so
the padding bits would have no effect on the value of the shifted unsigned
int (and the implementation would have to ensure that this was the case).

 

[Army1987]

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.

That'd require one unsigned int to occupy at least 4 KB

 

[Army1987]

The number of value bits in type unsigned isn't
guaranteed to be representable as an int type value.

Finding the greatest lower bound for the fraction of padding bits
among the bits of int on any implementation where log2(UINT_MAX+1.0)
is greater than INT_MAX is left as an exercise to the reader.

Now an implementation which wastes more than 99.5% (Hint: unless
I had something wrong, this is strictly less than the greatest
lower bound) of the bits in an int is an implementation I would
rather never have *anything* to do with (including "being to
within one light-year of each other").

 

[Charlie Gordon]

That'd require one unsigned int to occupy at least 4 KB

And the corresponding int representation to have at least 16368 padding bits
;-)

 

[Army1987]

And the corresponding int representation to have at least 16368 padding bits
;-)

Have you found a way for such an implementation to have less than
32752 padding bits in int?
(Yes, "at least 16368" is still true if the greatest lower bound
is 32752, but I wander if you found that that lower bound is
wrong.)

 

[Charlie Gordon]

Have you found a way for such an implementation to have less than
32752 padding bits in int?
(Yes, "at least 16368" is still true if the greatest lower bound
is 32752, but I wander if you found that that lower bound is
wrong.)

No, your lower bound seems good.