Bit Position of a Number at Compile Time

Question

I am implementing Fixed Point math on an embedded system using C.

For readability, I state the denominator as a power of 2:

#define Fixed_Point_Base 4096U

However, when I'm converting to and from the Fixed Point math, I need the shift quantity:

#define Fixed_Point_Bit_Position 12U

To make maintenance easier and the code more robust, I would like to have a #define for the bit position (number of shifts) in terms of the Fixed_Point_Base number:

#define Fixed_Point_Bit_Position(x) {/*...*/}

The only method I know involves logarithms and division, and I really don't want to use logarithms or division in an embedded system:

bit count = ln(4096) / ln(2)

I'm looking for a preprocessor macro or compile time solution that returns the bit position of a power of 2.

My web search has returned examples in code, but not as compile-time / preprocessor solution.

FYI, I'm using IAR Embedded Workbench with an ARM7TDMI processor.
Edit 1: I'm using MISRA C 2004 guidelines with Parasoft Static Analysis and Coverity Static Analysis tools. Answers must pass these constraints.

The other way around (define `Fixed_Point_Bit_Position`, use `Fixed_Point_Base(x)` to get the denominator) would be trivial. Can't you do that? — , Feb 27 '14 at 16:56
That is not as readable, `Fixed_Point_Base(12)` is not as readable as 4096U. — Thomas Matthews, Feb 27 '14 at 17:00

score 0 · Accepted Answer · edited May 23 '17 at 11:44

0

Your question is highly related my an old question of mine:

Is there any way to compute the width of an integer type at compile-time?

for which the accepted answer solves your problem:

https://stackoverflow.com/a/4589384/379897

In particular, use:

#define Fixed_Point_Bit_Position(x) IMAX_BITS((x)-1)

where IMAX_BITS is one of the macros from that answer.

edited May 23 '17 at 11:44

Community

1
1

answered Feb 27 '14 at 17:01

R.. GitHub STOP HELPING ICE

208,859
35
376
711

score 0 · Answer 2 · answered Feb 27 '14 at 17:02

0

You could do the reverse of what you're currently doing by defining the bit-precision and determining the Fixed_Point_Base from there like this:

#define PRECISIONS_IN_BITS ( 12 )
#define FIXED_POINT_BASE   ( 1 << PRECISION_IN_BITS )

This way you can maintain only one number.

answered Feb 27 '14 at 17:02

Paul Buckley

1

Nice answer, however, my compiler and static analysis tools require testing of the expression `(1 << PRECISION_IN_BITS)` to verify that the expression does not overflow the number of bits in the word. Which is why we use decimal numbers instead of a shift expression. – Thomas Matthews Feb 27 '14 at 17:07
But the literal 1 has type int, and that is guaranteed to be at least 16 bits, so it is *compile time* guaranteed not to overflow. I cannot see why static analysis would complain - this is an entirely conventional idiom. However I would suggest `((unsigned)(1u << PRECISION_IN_BITS))` and define `PRECISION_IN_BITS` as `12u`. – Clifford Feb 27 '14 at 19:17

Alex Celeste · Answer 3 · 2014-05-01T02:19:25.693

Brute force works for this!

Simple (well, "simple") solution that produces a C-level constant expression (can be used for compile-time constants such as array sizes):

#define Fixed_Point_Base 4096U

#define FPB_BITSET(X, K) (((Fixed_Point_Base >> (X) & 1) == 1) ? (X) : (K))
#define MAX_FP_BIT_32 FPB_BITSET(31, FPB_BITSET(30, FPB_BITSET(29, FPB_BITSET(28, FPB_BITSET(27, FPB_BITSET(26, FPB_BITSET(25, FPB_BITSET(24, \
                      FPB_BITSET(23, FPB_BITSET(22, FPB_BITSET(21, FPB_BITSET(20, FPB_BITSET(19, FPB_BITSET(18, FPB_BITSET(17, FPB_BITSET(16, \
                      FPB_BITSET(15, FPB_BITSET(14, FPB_BITSET(13, FPB_BITSET(12, FPB_BITSET(11, FPB_BITSET(10, FPB_BITSET(9, FPB_BITSET(8, \
                      FPB_BITSET(7, FPB_BITSET(6, FPB_BITSET(5, FPB_BITSET(4, FPB_BITSET(3, FPB_BITSET(2, FPB_BITSET(1, FPB_BITSET(0, -1 \
                      ))))))))))))))))))))))))))))))))
const unsigned int Fixed_Point_Bit_Position = MAX_FP_BIT_32;

Limited to 32-bit for the sake of my pasting finger: expanding it is trivial. Seemingly a little-known fact that the ternary operator is a constant expression.

Preprocessor-only version (if you need to token-paste the result or something):

#define FPB_BITSET(X) (((Fixed_Point_Base >> (X) & 1) == 1) * (X))

#if FPB_BITSET(31)
#  define Fixed_Point_Bit_Position 31
#elif FPB_BITSET(30)
#  define Fixed_Point_Bit_Position 30
#elif FPB_BITSET(29)
#  define Fixed_Point_Bit_Position 29
#elif //etc...

Bit Position of a Number at Compile Time

3 Answers3