Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Value Bits Vs Object Bits (http://www.velocityreviews.com/forums/t442970-value-bits-vs-object-bits.html)

 Tomás 06-02-2006 06:11 AM

Value Bits Vs Object Bits

The quantity of bits used by an unsigned integer type in memory can be
determined by:

typedef unsigned long long UIntType;

CHAR_BIT * sizeof(UIntType)

However, what would be a good portable way to determine how many of these
bits are value bits? If possible, it would be nice to have it as a
compile time constant.

Here's something I played around with:

typedef unsigned long long UIntType;

unsigned GetQuantityValueBits(void)
{
/* We know it's atleast 8 in anyway */

unsigned quantity = 8;

UIntType val = 128;

while (val <<= 1) ++quantity;

return quantity;
}

Also, we could determine the amount of non-value bits (trapping bits
perhaps) from:

sizeof(UIntType) * CHAR_BIT - GetQuantityValueBits()

-Tomás

 Eric Sosman 06-02-2006 12:26 PM

Re: Value Bits Vs Object Bits

Tomás wrote:

> The quantity of bits used by an unsigned integer type in memory can be
> determined by:
>
>
> typedef unsigned long long UIntType;
>
> CHAR_BIT * sizeof(UIntType)
>
>
> However, what would be a good portable way to determine how many of these
> bits are value bits? If possible, it would be nice to have it as a
> compile time constant.

Speaking for myself, I've never been able to discover a
way to write a constant expression for this. However, it's
easy enough to determine at run-time by starting with a value
of all-ones and counting how many one-bit shifts are required
before the value becomes zero. You could also try something
like ceil(log((UIntType)-1)/log(2)).

It is occasionally annoying that this information is not
easily available. For many uses an upper bound is all that's
needed and CHAR_BIT*sizeof(UIntType) is good enough. For a
different class of uses a range bound is wanted, and you can
get that from (UIntType)-1. But for things like managing
"arrays" of single-bit flags packed into larger units, it is
annoying that the value bits can't be counted at compile time.

Confession: I usually ignore the possibility of P.B.s and
just pretend CHAR_BIT*sizeof is the Right Answer. The nasal
demons haven't punished me yet (for that sin, anyway), but of
course the Standard makes no guarantee about the timeliness
of retribution.

--
Eric Sosman
esosman@acm-dot-org.invalid

 Hallvard B Furuseth 06-02-2006 05:11 PM

Re: Value Bits Vs Object Bits

Eric Sosman writes:
> Tomás wrote:
>
>> The quantity of bits used by an unsigned integer type in memory can be
>> determined by:
>> typedef unsigned long long UIntType;
>> CHAR_BIT * sizeof(UIntType)
>> However, what would be a good portable way to determine how many of
>> these bits are value bits? If possible, it would be nice to have it as
>> a compile time constant.

>
> Speaking for myself, I've never been able to discover a
> way to write a constant expression for this.

I have. Posted it before.

/* Number of bits in inttype_MAX, or in any (1<<k)-1 where 0 <= k < 3.2E+10 */
#define IMAX_BITS(m) ((m) /((m)%0x3fffffffL+1) /0x3fffffffL %0x3fffffffL *30 \
+ (m)%0x3fffffffL /((m)%31+1)/31%31*5 + 4-12/((m)%31+3))

So IMAX_BITS((unsigned_type)-1) computes the number of bits in an
unsigned integer type. IMAX_BITS(INT_MAX) computes the number of bits
in an int. Until someone implements a 4-gigabyte integer type:-)

Or if you are less paranoid about how large UINTMAX_MAX can get:

/* Number of bits in inttype_MAX, or in any (1<<k)-1 where 0 <= k < 2040 */
#define IMAX_BITS(m) ((m)/((m)%255+1) / 255%255*8 + 7-86/((m)%255+12))

> Confession: I usually ignore the possibility of P.B.s and
> just pretend CHAR_BIT*sizeof is the Right Answer. The nasal
> demons haven't punished me yet (for that sin, anyway), but of
> course the Standard makes no guarantee about the timeliness
> of retribution.

As long as that just wastes a bit of memory when it's wrong, that's my
preference too. IMAX_BITS is a fun little hack, but not exactly

Explanation, were 'x**y' means x raised to the power of y:
Line 1 computes (number of whole 30-bit chunks) * 30:
For m = (2**(K*n+r))-1 and P = (2**K)-1 with K=30, P=0x3fffffff,
m = (P+1)**n * 2**r - 1,
m % P + 1 = 1 * 2**r - 1 + 1 = 2**r when 2**r-1<P so r<K,
m /(m%P+1) = (P+1)**n - 1
= ((P+1)-1) * ((P+1)**0 +...+ (P+1)**(n-1)),
.../P%P*K = ( 1**0 +...+ 1**(n-1)) % P * K
= n*K when n < P.
Part 2 does the same to the remainder (m%0x3fffffff) with K=5, P=31.
Part 3 "happens" to count the final 0-4 bits in m%31=[0/1/3/7/15].
m % 31 is short for m % 0x3fffffff % 31, because 0x3fffffff % 31 = 0.
0x3fffffffL is the largest portable 2**x-1 with such a 2**y-1 factor.

--
Hallvard

Re: Value Bits Vs Object Bits

Hallvard B Furuseth wrote:

> /* Number of bits in inttype_MAX, or in any (1<<k)-1 where 0 <= k < 3.2E+10 */
> #define IMAX_BITS(m) ((m) /((m)%0x3fffffffL+1) /0x3fffffffL %0x3fffffffL *30 \
> + (m)%0x3fffffffL /((m)%31+1)/31%31*5 + 4-12/((m)%31+3))
>
> So IMAX_BITS((unsigned_type)-1) computes the number of bits in an
> unsigned integer type.

Great job. Thanks!

--

 Eric Sosman 06-03-2006 07:43 PM

Re: Value Bits Vs Object Bits

Hallvard B Furuseth wrote:
> Eric Sosman writes:
>
>>Tomás wrote:
>>
>>
>>>The quantity of bits used by an unsigned integer type in memory can be
>>>determined by:
>>> typedef unsigned long long UIntType;
>>> CHAR_BIT * sizeof(UIntType)
>>>However, what would be a good portable way to determine how many of
>>>these bits are value bits? If possible, it would be nice to have it as
>>>a compile time constant.

>>
>> Speaking for myself, I've never been able to discover a
>>way to write a constant expression for this.

>
>
> I have. Posted it before.
>
> /* Number of bits in inttype_MAX, or in any (1<<k)-1 where 0 <= k < 3.2E+10 */
> #define IMAX_BITS(m) ((m) /((m)%0x3fffffffL+1) /0x3fffffffL %0x3fffffffL *30 \
> + (m)%0x3fffffffL /((m)%31+1)/31%31*5 + 4-12/((m)%31+3))

Yikes! It looks like an IOCCC snippet, but ... I am in awe.

--
Eric Sosman
esosman@acm-dot-org.invalid

 Hallvard B Furuseth 06-18-2006 07:15 PM

Re: Value Bits Vs Object Bits

Some time ago I wrote:
>/* Number of bits in inttype_MAX, or in any (1<<k)-1 where 0 <= k < 3.2E+10 */
>#define IMAX_BITS(m) ((m) /((m)%0x3fffffffL+1) /0x3fffffffL %0x3fffffffL *30 \
> + (m)%0x3fffffffL /((m)%31+1)/31%31*5 + 4-12/((m)%31+3))
>
> So IMAX_BITS((unsigned_type)-1) computes the number of bits in an
> unsigned integer type. IMAX_BITS(INT_MAX) computes the number of bits
> in an int. Until someone implements a 4-gigabyte integer type:-)

Eh. An int has IMAX_BITS(INT_MAX)+1 bits - with the sign bit.

--
Hallvard

 Frederick Gotham 06-25-2006 04:53 PM

Re: Value Bits Vs Object Bits

Hallvard B Furuseth posted:

> #define IMAX_BITS(m) ((m) /((m)%0x3fffffffL+1) /0x3fffffffL
> %0x3fffffffL *30 \
> + (m)%0x3fffffffL /((m)%31+1)/31%31*5 +
> 4-12/((m)%31+3))
>

Are you sure that works? It seems to work a lot of the time... but
sometimes I get inaccurate values.

If I enter 2048 into the following program, I get 112 bits:

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

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
for(;;)
{
printf( "\nEnter a number: " );

unsigned long val;

scanf( "%lu", &val );

if ( 999 == val ) break;

printf("\n\nIt consists of: %lu bits\n\n", IMAX_BITS(val) );

system("PAUSE");
}
}

--

Frederick Gotham

 pete 06-25-2006 06:47 PM

Re: Value Bits Vs Object Bits

Frederick Gotham wrote:
>
> Hallvard B Furuseth posted:
>
> > #define IMAX_BITS(m) ((m) /((m)%0x3fffffffL+1) /0x3fffffffL
> > %0x3fffffffL *30 \
> > + (m)%0x3fffffffL /((m)%31+1)/31%31*5 +
> > 4-12/((m)%31+3))
> >

>
> Are you sure that works? It seems to work a lot of the time... but
> sometimes I get inaccurate values.
>
> If I enter 2048 into the following program, I get 112 bits:

Me too.
There are also problems with higher numbers.

--
pete

 Eric Sosman 06-25-2006 07:18 PM

Re: Value Bits Vs Object Bits

Frederick Gotham wrote:

> Hallvard B Furuseth posted:
>
>
>>#define IMAX_BITS(m) ((m) /((m)%0x3fffffffL+1) /0x3fffffffL
>>%0x3fffffffL *30 \
>> + (m)%0x3fffffffL /((m)%31+1)/31%31*5 +
>> 4-12/((m)%31+3))
>>

>
>
>
> Are you sure that works? It seems to work a lot of the time... but
> sometimes I get inaccurate values.
>
>
> If I enter 2048 into the following program, I get 112 bits:
> [code snipped; it just passes input numbers to the macro]

Somewhere along the line, somebody has snipped away the
comment that preceded the macro when originally posted:

> /* Number of bits in inttype_MAX, or in any (1<<k)-1
> where 0 <= k < 3.2E+10 */

That is, the macro is only advertised to work for arguments
that are one less than a power of two. It is not a general-
purpose compile-time log() function!

--
Eric Sosman
esosman@acm-dot-org.invalid

 Frederick Gotham 06-25-2006 08:20 PM

Re: Value Bits Vs Object Bits

Eric Sosman posted:

> Somewhere along the line, somebody has snipped away the
> comment that preceded the macro when originally posted:
>
> > /* Number of bits in inttype_MAX, or in any (1<<k)-1
> > where 0 <= k < 3.2E+10 */

>
> That is, the macro is only advertised to work for arguments
> that are one less than a power of two. It is not a general-
> purpose compile-time log() function!

Hehe... I found the code so confusing that I didn't pay attention to the

"One less than a power of two" would refer to numbers where every bit is
one, e.g.

111

11111111

11111

111111111111

Anyhow, the macro is a stroke of genius. I wonder what other gems
Hallvard B Furuseth has come up with... ?

A compile time "Log base 2" macro would be brilliant...

--

Frederick Gotham

All times are GMT. The time now is 07:29 AM.