Value Bits Vs Object Bits

[Tomás]

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 GetQuantityValu eBits(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 - GetQuantityValu eBits()
-Tomás

[Eric Sosman]

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((UIntT ype)-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
es*****@acm-dot-org.invalid

[Hallvard B Furuseth]

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)%0x3fffffff L+1) /0x3fffffffL %0x3fffffffL *30 \
+ (m)%0x3fffffffL /((m)%31+1)/31%31*5 + 4-12/((m)%31+3))

So IMAX_BITS((unsi gned_type)-1) computes the number of bits in an
unsigned integer type. IMAX_BITS(INT_M AX) 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
readable.

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

[Thad Smith]

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)%0x3fffffff L+1) /0x3fffffffL %0x3fffffffL *30 \
+ (m)%0x3fffffffL /((m)%31+1)/31%31*5 + 4-12/((m)%31+3))

So IMAX_BITS((unsi gned_type)-1) computes the number of bits in an
unsigned integer type.

Great job. Thanks!

--
Thad

[Eric Sosman]

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)%0x3fffffff L+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
es*****@acm-dot-org.invalid

[Hallvard B Furuseth]

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)%0x3fffffff L+1) /0x3fffffffL %0x3fffffffL *30 \
+ (m)%0x3fffffffL /((m)%31+1)/31%31*5 + 4-12/((m)%31+3))

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

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

--
Hallvard

[Frederick Gotham]

Hallvard B Furuseth posted:

#define IMAX_BITS(m) ((m) /((m)%0x3fffffff L+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)%0x3fffffff L+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]

Frederick Gotham wrote:

Hallvard B Furuseth posted:

#define IMAX_BITS(m) ((m) /((m)%0x3fffffff L+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]

Frederick Gotham wrote:

Hallvard B Furuseth posted:

#define IMAX_BITS(m) ((m) /((m)%0x3fffffff L+1) /0x3fffffffL
%0x3fffffff L *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
es*****@acm-dot-org.invalid

[Frederick Gotham]

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

"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