Amount of bits needed (as a compile time constant)

[Martin Wells]

Anyone know a good compile-time constant to tell you how many bits are
needed to store a given value?

For instance:

CALC_BITS_NEEDED(0) == 1
CALC_BITS_NEEDED(1) == 1
CALC_BITS_NEEDED(2) == 2
CALC_BITS_NEEDED(3) == 2
CALC_BITS_NEEDED(4) == 3
CALC_BITS_NEEDED(7) == 3
CALC_BITS_NEEDED(8) == 4

I need it as a compile-time constant coz I'll be using as an array
size. I first though of trying IMAX_BITS but it only works on numbers
where all bits are 1.

Martin

 

[jacob navia]

Anyone know a good compile-time constant to tell you how many bits are
needed to store a given value?

For instance:

CALC_BITS_NEEDED(0) == 1
CALC_BITS_NEEDED(1) == 1
CALC_BITS_NEEDED(2) == 2
CALC_BITS_NEEDED(3) == 2
CALC_BITS_NEEDED(4) == 3
CALC_BITS_NEEDED(7) == 3
CALC_BITS_NEEDED(8) == 4

I need it as a compile-time constant coz I'll be using as an array
size. I first though of trying IMAX_BITS but it only works on numbers
where all bits are 1.

Martin

Hi Martin

#include <math.h>
#include <stdlib.h>
#include <stdio.h>
int main(int argc,char *argv[])
{
double d;

if (argc < 2) {
printf("Usage: %s <number>\n",argv[0]);
return EXIT_FAILURE;
}
d = strtod(argv[1],NULL);
printf("%g\n",ceil(log2(d)));
}

Compile that, and then insert the answer in your program.
I do not see any way to do it at compile time other than
that.

 

[Willem]

Martin wrote:
) Anyone know a good compile-time constant to tell you how many bits are
) needed to store a given value?

I'm not sure if the Standard requires it, but on my compiler, a?b:c reduces
to a constant if the arguments are constants.

So you could use something like:

#define CALC_BITS_02(x) ((x) ? 1+CALC_BITS_03((x)>>1) : 0)
#define CALC_BITS_01(x) ((x) ? 1+CALC_BITS_02((x)>>1) : 0)
#define CALC_BITS_NEEDED ((x) ? 1+CALC_BITS_01((x)>>1) : 0)

and just copy/paste as many as you need, increasing the number each time.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Ben Bacarisse]

Martin wrote:
) Anyone know a good compile-time constant to tell you how many bits are
) needed to store a given value?

I'm not sure if the Standard requires it,

It is.

but on my compiler, a?b:c reduces
to a constant if the arguments are constants.

So you could use something like:

#define CALC_BITS_02(x) ((x) ? 1+CALC_BITS_03((x)>>1) : 0)
#define CALC_BITS_01(x) ((x) ? 1+CALC_BITS_02((x)>>1) : 0)
#define CALC_BITS_NEEDED ((x) ? 1+CALC_BITS_01((x)>>1) : 0)

Typo: you intended (x) after CALC_BITS_NEEDED.

One could also do something like:

#define CALC_BITS_NEEDED1(x) ((x) & 0x1u)
#define CALC_BITS_NEEDED2(x) ((x) & 0x2u ? 1+CALC_BITS_NEEDED1((x) >> 1) \
: CALC_BITS_NEEDED1((x) & 0x1u))
#define CALC_BITS_NEEDED4(x) ((x) & 0xcu ? 2+CALC_BITS_NEEDED2((x) >> 2) \
: CALC_BITS_NEEDED2((x) & 0x3u))
#define CALC_BITS_NEEDED8(x) ((x) & 0xf0u ? 4+CALC_BITS_NEEDED4((x) >> 4) \
: CALC_BITS_NEEDED4((x) & 0xfu))
#define CALC_BITS_NEEDED16(x) ((x) & 0xff00u ? 8+CALC_BITS_NEEDED8((x) >> 8) \
: CALC_BITS_NEEDED8((x) & 0xffu))
#define CALC_BITS_NEEDED32(x) ((x) & 0xffff0000lu ? \
16+CALC_BITS_NEEDED16((x) >> 16) : \
CALC_BITS_NEEDED16((x) & 0xffffu))

or shorten that by:

#define CALC_BITS_NEED4(x) ((x) > 1 ? 2 : (x) & 1)

 

[Martin Wells]

I'm not sure how I'd achieve this, but is there any way I could get
the high bit on it's own? If so, I'd do it in the following steps:

1: Take the original number 1010
2: Take just the high bit 1000
3: Subtract 1 from it 111
4: Shift it once to the left and then add 1 1111
5: Use IMAX_BITS to give 4

Something like:

#define BITS_NEEDED(x) ( IMAX_BITS( (JUST_HIGH_BIT((x)) - 1 << 1) +
1 ) )

So now I just need a formula for JUST_HIGH_BIT

Any ideas?

Martin

 

[Willem]

Martin wrote:
)
) I'm not sure how I'd achieve this, but is there any way I could get
) the high bit on it's own? If so, I'd do it in the following steps:
)
) 1: Take the original number 1010
) 2: Take just the high bit 1000
) 3: Subtract 1 from it 111
) 4: Shift it once to the left and then add 1 1111
) 5: Use IMAX_BITS to give 4
)
) Something like:
)
) #define BITS_NEEDED(x) ( IMAX_BITS( (JUST_HIGH_BIT((x)) - 1 << 1) +
) 1 ) )
)
) So now I just need a formula for JUST_HIGH_BIT

I think that formula would be roughly the same as the formulae that
were posted already to calculate the result you wanted.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Ben Bacarisse]

I'm not sure how I'd achieve this, but is there any way I could get
the high bit on it's own? If so, I'd do it in the following steps:

1: Take the original number 1010
2: Take just the high bit 1000
3: Subtract 1 from it 111
4: Shift it once to the left and then add 1 1111
5: Use IMAX_BITS to give 4

Something like:

#define BITS_NEEDED(x) ( IMAX_BITS( (JUST_HIGH_BIT((x)) - 1 << 1) +
1 ) )

So now I just need a formula for JUST_HIGH_BIT

Any ideas?

I don't know what IMAX_BITS is (does it count 1s?) but steps 1 to 4
can be done by (for max 32-bit unsigned):

x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;

You probably want that as a constant expression, which looks mighty
fiddly to do. I am tempted to ask what the high-level objective is.
In other words, maybe all this can be avoided?

 

[Eric Sosman]

Anyone know a good compile-time constant to tell you how many bits are
needed to store a given value?

For instance:

CALC_BITS_NEEDED(0) == 1
CALC_BITS_NEEDED(1) == 1
CALC_BITS_NEEDED(2) == 2
CALC_BITS_NEEDED(3) == 2
CALC_BITS_NEEDED(4) == 3
CALC_BITS_NEEDED(7) == 3
CALC_BITS_NEEDED(8) == 4

I need it as a compile-time constant coz I'll be using as an array
size. I first though of trying IMAX_BITS but it only works on numbers
where all bits are 1.

Given that the intended use is for an array size, it
seems safe to suppose that the numbers are non-negative
and well within the range of unsigned long long or maybe
even unsigned long. That makes the possibilities easy
to enumerate, as in:

#define CALC_BITS_NEEDED(x) (1 \
+ ((x) > 1) \
+ ((x) > 3) \
+ ((x) > 7) + \
+ ... \
+ ((x) > 0x...FFF) \
)

Use as many terms as you think the numbers might need:
thirty-two, perhaps, for arrays up to four giga-elements.
You might want to incorporate one of the "compile-time
assertion" hacks for a range check, perhaps by rewriting
the initial constant term along these lines:

#define CALC_BITS_NEEDED(x) ( \
sizeof(char[(x) >= 0 && (x) <= 0x...FFF]) \
+ ...

 

[Martin Wells]

You probably want that as a constant expression, which looks mighty
fiddly to do. I am tempted to ask what the high-level objective is.
In other words, maybe all this can be avoided?

I have 42 LED's. Each LED can be green, red, or off. That's three
possible combinations. Doing the following would be out of the
question because I *really* have to go easy on memory consumption:

unsigned data[QUANTITY_LEDS];

Instead, I want to use only two bits per LED. What I'm doing will be
something like:

#define COMBINATIONS 3 /* Green, red or off */

#define BITS_NEEDED_TO_STORE_VALUE(x) /* This is what I'm posting
here looking for */

#define BITS_NEEDED ((unsigned)QUANTITY_LEDS *
BITS_NEEDED_TO_STORE_VALUE(COMBINATIONS - 1))

#define BYTES_NEEDED (BITS_NEEDED / CHAR_BIT + !!(BITS_NEEDED %
CHAR_BIT))

char unsigned data[BYTES_NEEDED];


Yes, I realise it's RIDICULOUSLY portable, but I'm a ridiculously
portable kind of guy

Martin

 

[Martin Wells]

Eric:

I need it as a compile-time constant coz I'll be using as an array
size. I first though of trying IMAX_BITS but it only works on numbers
where all bits are 1.

Given that the intended use is for an array size, it
seems safe to suppose that the numbers are non-negative
and well within the range of unsigned long long or maybe
even unsigned long. That makes the possibilities easy
to enumerate, as in:

#define CALC_BITS_NEEDED(x) (1 \
+ ((x) > 1) \
+ ((x) > 3) \
+ ((x) > 7) + \
+ ... \
+ ((x) > 0x...FFF) \
)

Use as many terms as you think the numbers might need:
thirty-two, perhaps, for arrays up to four giga-elements.
You might want to incorporate one of the "compile-time
assertion" hacks for a range check, perhaps by rewriting
the initial constant term along these lines:

#define CALC_BITS_NEEDED(x) ( \
sizeof(char[(x) >= 0 && (x) <= 0x...FFF]) \
+ ...

I think this is the best option so far. Thanks a lot Eric, you're a
great help.

If anyone else has more ideas though please throw them out there.

Martin

 

[Ben Bacarisse]

You probably want that as a constant expression, which looks mighty
fiddly to do. I am tempted to ask what the high-level objective is.
In other words, maybe all this can be avoided?

I have 42 LED's. Each LED can be green, red, or off. That's three
possible combinations. Doing the following would be out of the
question because I *really* have to go easy on memory consumption:

unsigned data[QUANTITY_LEDS];

Instead, I want to use only two bits per LED. What I'm doing will be
something like:

#define COMBINATIONS 3 /* Green, red or off */

#define BITS_NEEDED_TO_STORE_VALUE(x) /* This is what I'm posting
here looking for */

#define BITS_NEEDED ((unsigned)QUANTITY_LEDS *
BITS_NEEDED_TO_STORE_VALUE(COMBINATIONS - 1))

#define BYTES_NEEDED (BITS_NEEDED / CHAR_BIT + !!(BITS_NEEDED %
CHAR_BIT))

char unsigned data[BYTES_NEEDED];

Ah! Personally, I'd start with BITS_NEEDED_TO_STORE_VALUE and just
set that to 2 with a comment: "ceil(log2(3)) for off/red/green".

But given the number of combinations is quite small, I'd go with Eric
Sosman's nested conditional rather than junk I posted.

 

[Martin Wells]

Ben:

Ah! Personally, I'd start with BITS_NEEDED_TO_STORE_VALUE and just
set that to 2 with a comment: "ceil(log2(3)) for off/red/green".

I know that's an option, but I'm gonna define "COMBINATIONS" in a
different header file, and I want to be able to change COMBINATIONS
without having to change anything else if I decide to add a few more
colours

Martin