How do I do log(x) with the preprocessor on windows ?
like:
#define A log(4)/log(2)
and after in my code the array
int b[A]; // A=2 will be computed with the preprocessor ! not in run time
Asked
Active
Viewed 9,914 times
10
Hascoet Julien
- 118
- 1
- 6
-
4And just to be clear, what base do you want `log` to be in? – Cornstalks Dec 20 '14 at 15:43
-
Related: *[Can the C preprocessor perform integer arithmetic?](https://stackoverflow.com/questions/1560357/)* – Peter Mortensen Aug 15 '23 at 13:11
6 Answers
13
Alright, and now for the dirty brute-force preprocessor trickery.
From your question, I assume that what you actually want is not a general logarithm (which isn't even possible in integer arithmetic) but the number of bits needed to represent a given number. If we restrict ourself to 32 bit integers, there is a solution to this, although it's not pretty.
#define IS_REPRESENTIBLE_IN_D_BITS(D, N) \
(((unsigned long) N >= (1UL << (D - 1)) && (unsigned long) N < (1UL << D)) ? D : -1)
#define BITS_TO_REPRESENT(N) \
(N == 0 ? 1 : (31 \
+ IS_REPRESENTIBLE_IN_D_BITS( 1, N) \
+ IS_REPRESENTIBLE_IN_D_BITS( 2, N) \
+ IS_REPRESENTIBLE_IN_D_BITS( 3, N) \
+ IS_REPRESENTIBLE_IN_D_BITS( 4, N) \
+ IS_REPRESENTIBLE_IN_D_BITS( 5, N) \
+ IS_REPRESENTIBLE_IN_D_BITS( 6, N) \
+ IS_REPRESENTIBLE_IN_D_BITS( 7, N) \
+ IS_REPRESENTIBLE_IN_D_BITS( 8, N) \
+ IS_REPRESENTIBLE_IN_D_BITS( 9, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(10, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(11, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(12, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(13, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(14, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(15, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(16, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(17, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(18, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(19, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(20, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(21, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(22, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(23, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(24, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(25, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(26, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(27, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(28, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(29, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(30, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(31, N) \
+ IS_REPRESENTIBLE_IN_D_BITS(32, N) \
) \
)
The idea is that a number n > 0 has a representation using exactly d bits if and only if n ≥ 2d−1 and n < 2d. After treating the n = 0 case specially, we simply brute-force this out for all 32 possible answers.
The helper macro IS_REPRESENTIBLE_IN_D_BITS(D, N) will expand to an expression evaluating to D if N can be represented using exactly D bits and to -1 otherwise. I have defined the macros such that the result is −1 if the answer is “no”. To compensate for the negative summands, I add 31 at the end. If the number cannot be represented in any 1, …, 32 bits then the overall result will be −1 which should help us catch some errors.
The expression BITS_TO_REPRESENT(42) is a valid compile-time constant for use in an array length declaration.
All that said, the additional cost for always making your array 32 elements long seems acceptable for many applications and it saves you quite some trouble. So I would only use such trickery if I really had to.
Update: Just to avoid confusion: This solution does not use the preprocessor to evaluate the “logarithm”. All the preprocessor does is performing a text substitution that you can see if compiling with the -E switch (at least for GCC). Let's have a look at this code:
int
main()
{
int digits[BITS_TO_REPRESENT(42)];
return 0;
}
It will be preprocessed to (be warned):
int
main()
{
int digits[(42 == 0 ? 1 : (31 + (((unsigned long) 42 >= (1UL << (1 - 1)) && (unsigned long) 42 < (1UL << 1)) ? 1 : -1) + (((unsigned long) 42 >= (1UL << (2 - 1)) && (unsigned long) 42 < (1UL << 2)) ? 2 : -1) + (((unsigned long) 42 >= (1UL << (3 - 1)) && (unsigned long) 42 < (1UL << 3)) ? 3 : -1) + (((unsigned long) 42 >= (1UL << (4 - 1)) && (unsigned long) 42 < (1UL << 4)) ? 4 : -1) + (((unsigned long) 42 >= (1UL << (5 - 1)) && (unsigned long) 42 < (1UL << 5)) ? 5 : -1) + (((unsigned long) 42 >= (1UL << (6 - 1)) && (unsigned long) 42 < (1UL << 6)) ? 6 : -1) + (((unsigned long) 42 >= (1UL << (7 - 1)) && (unsigned long) 42 < (1UL << 7)) ? 7 : -1) + (((unsigned long) 42 >= (1UL << (8 - 1)) && (unsigned long) 42 < (1UL << 8)) ? 8 : -1) + (((unsigned long) 42 >= (1UL << (9 - 1)) && (unsigned long) 42 < (1UL << 9)) ? 9 : -1) + (((unsigned long) 42 >= (1UL << (10 - 1)) && (unsigned long) 42 < (1UL << 10)) ? 10 : -1) + (((unsigned long) 42 >= (1UL << (11 - 1)) && (unsigned long) 42 < (1UL << 11)) ? 11 : -1) + (((unsigned long) 42 >= (1UL << (12 - 1)) && (unsigned long) 42 < (1UL << 12)) ? 12 : -1) + (((unsigned long) 42 >= (1UL << (13 - 1)) && (unsigned long) 42 < (1UL << 13)) ? 13 : -1) + (((unsigned long) 42 >= (1UL << (14 - 1)) && (unsigned long) 42 < (1UL << 14)) ? 14 : -1) + (((unsigned long) 42 >= (1UL << (15 - 1)) && (unsigned long) 42 < (1UL << 15)) ? 15 : -1) + (((unsigned long) 42 >= (1UL << (16 - 1)) && (unsigned long) 42 < (1UL << 16)) ? 16 : -1) + (((unsigned long) 42 >= (1UL << (17 - 1)) && (unsigned long) 42 < (1UL << 17)) ? 17 : -1) + (((unsigned long) 42 >= (1UL << (18 - 1)) && (unsigned long) 42 < (1UL << 18)) ? 18 : -1) + (((unsigned long) 42 >= (1UL << (19 - 1)) && (unsigned long) 42 < (1UL << 19)) ? 19 : -1) + (((unsigned long) 42 >= (1UL << (20 - 1)) && (unsigned long) 42 < (1UL << 20)) ? 20 : -1) + (((unsigned long) 42 >= (1UL << (21 - 1)) && (unsigned long) 42 < (1UL << 21)) ? 21 : -1) + (((unsigned long) 42 >= (1UL << (22 - 1)) && (unsigned long) 42 < (1UL << 22)) ? 22 : -1) + (((unsigned long) 42 >= (1UL << (23 - 1)) && (unsigned long) 42 < (1UL << 23)) ? 23 : -1) + (((unsigned long) 42 >= (1UL << (24 - 1)) && (unsigned long) 42 < (1UL << 24)) ? 24 : -1) + (((unsigned long) 42 >= (1UL << (25 - 1)) && (unsigned long) 42 < (1UL << 25)) ? 25 : -1) + (((unsigned long) 42 >= (1UL << (26 - 1)) && (unsigned long) 42 < (1UL << 26)) ? 26 : -1) + (((unsigned long) 42 >= (1UL << (27 - 1)) && (unsigned long) 42 < (1UL << 27)) ? 27 : -1) + (((unsigned long) 42 >= (1UL << (28 - 1)) && (unsigned long) 42 < (1UL << 28)) ? 28 : -1) + (((unsigned long) 42 >= (1UL << (29 - 1)) && (unsigned long) 42 < (1UL << 29)) ? 29 : -1) + (((unsigned long) 42 >= (1UL << (30 - 1)) && (unsigned long) 42 < (1UL << 30)) ? 30 : -1) + (((unsigned long) 42 >= (1UL << (31 - 1)) && (unsigned long) 42 < (1UL << 31)) ? 31 : -1) + (((unsigned long) 42 >= (1UL << (32 - 1)) && (unsigned long) 42 < (1UL << 32)) ? 32 : -1) ) )];
return 0;
}
This looks terrible and if it were evaluated at run-time, it would be quite a number of instructions. However, since all operands are constants (or literals, to be precise) the compiler is able to evaluate this at compile-time. It has to do so, because an array length declaration must be a constant in C 89.
If you are using the macro in other places that are not required to be compile-time constants, it is up to the compiler whether or not it evaluates the expression. However, any reasonable compiler should be expected to perform this rather elementary optimization – known as constant folding – if optimizations are enabled. If in doubt – as always – have a look at the generated assembly code.
For example, let us consider this program.
int
main()
{
return BITS_TO_REPRESENT(42);
}
The expression in a return statement clearly isn't required to be a compile-time constant, so let's look what code GCC will generate. (I'm using the -S switch to stop at the assembly stage.)
Even without any optimizations enabled, I get the following assembly code which shows that the macro expansion was folded into the constant 6.
main:
.LFB0:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
movl $6, %eax # See the constant 6?
popq %rbp
.cfi_def_cfa 7, 8
ret
.cfi_endproc
5gon12eder
- 24,280
- 5
- 45
- 92
-
Alright thanks, but are you sure that everything is done at compile time ? (nice trick by the way i love it =) ) – Hascoet Julien Dec 20 '14 at 17:03
-
@HascoetJulien An array length declaration *must* be evaluated at compile-time. If you are using the macro in an expression that is not required to be a compile-time constant, it's up to the compiler whether or not it evaluates it statically. That said, a compiler would be really stupid if it did not evaluate an expression with all operands constants at compile-time (at least with optimizations enabled). This is known as *constant folding* and one of the more elementary optimizations. If in doubt, as always, have a look at the generated assembly code. – 5gon12eder Dec 20 '14 at 17:13
-
@HascoetJulien You're welcome. I have added an amendment to my answer to explain what I've meant to say in my last comment a bit further. – 5gon12eder Dec 20 '14 at 17:30
-
Mathematically, this answer is equivalent to `floor(log2(n)) + 1` (except when n==0, yields 1). Programmatically, this answer is the number of bits needed to represent a number (as you explain). – Codesmith Jul 22 '21 at 14:49
9
A little bit shorter definition for LOG macro working with integers up to 32 bits could be:
#define LOG_1(n) (((n) >= 2) ? 1 : 0)
#define LOG_2(n) (((n) >= 1<<2) ? (2 + LOG_1((n)>>2)) : LOG_1(n))
#define LOG_4(n) (((n) >= 1<<4) ? (4 + LOG_2((n)>>4)) : LOG_2(n))
#define LOG_8(n) (((n) >= 1<<8) ? (8 + LOG_4((n)>>8)) : LOG_4(n))
#define LOG(n) (((n) >= 1<<16) ? (16 + LOG_8((n)>>16)) : LOG_8(n))
However, before using it, check if you really need it. People often need to use logarithm for values which are a power of 2. For example when implementing bit-arrays or so. While it is difficult to calculate log as a constant expression, it is very easy to define power of 2. So, you may consider to define your constants as:
#define logA 4
#define A (1<<logA)
instead of:
#define A 16
#define logA LOG(A)
Marian
- 7,402
- 2
- 22
- 34
-
`#define BITS_TO_REPRESENT(n) (LOG(n) + !!((n) & ((n) - 1)))` gives this the same use-case as top answer, i think – Dec 03 '17 at 19:43
-
Perfect for my use case! Note, to be precise: Mathematically, this answer is equivalent to `floor(log2(x))`. Programmatically, this answer is the position of the highest bit in the number (0 being the lowest value bit). – Codesmith Jul 22 '21 at 14:31
-
(Ok, technically mathematically, `log2(0)` is -infinity; for this macro, `LOG(0)` yields 0) – Codesmith Jul 22 '21 at 14:52
-
`1<<16` better as `0x10000` to handle 16-bit `int` should `n` get passed run-time code. – chux - Reinstate Monica Apr 24 '23 at 15:44
2
The C preprocessor #define is purely a text substitution mechanism. You will not be able to calculate log values at compile time.
You might be able to with C++ templates, but that is black magic I don't understand, and currently irrelevant.
Or as I mentioned in a comment below, you could build your own pre-pre-processor that evaluates the array size equations before handing the updated code over to the standard C compiler.
Edit
In poking around some more I saw this SO question: Do any C or C++ compilers optimize within define macros?
This question is about evaluating this string of macros:
#include <math.h>
#define ROWS 15
#define COLS 16
#define COEFF 0.15
#define NODES (ROWS*COLS)
#define A_CONSTANT (COEFF*(sqrt(NODES)))
The consensus was that A_CONSTANT can be a compile time constant, depending on how smart the compiler is, and what mathematical functions are defined as intrinsics. It also alluded to GCC being smart enough to figure this out for this case.
So the answer to your question could be found in trying it, and seeing what sort of code your compiler actually produces.
-
1
-
-
And OP specifically talking about preprocessors, he may be confused with how #define works. – Pranit Kothari Dec 20 '14 at 15:42
-
Thanks I know exactly how #define works but I want to make a generic implementation and in have array length that depends on log value and i want static allocation instead of doing malloc. Moreover it is also for loop unroll and other tricky optimization that can be done when arrays a declared with the compiler and no in run time – Hascoet Julien Dec 20 '14 at 15:52
-
@HascoetJulien It would seem that you can't do what you want in C, unless perhaps there is some custom C compiler extension you could write for your specific application - which if the loop unrolling speed up is big enough, might warrant you doing it. – Peter M Dec 20 '14 at 16:00
-
1@HascoetJulien Or build your own pre-pre-processor which evaluates the equations before you throw the source code at the standard C compiler. This would be easier than modifying the compiler. – Peter M Dec 20 '14 at 16:04
2
This answer is inspired by 5gon12eder, but with a simpler first macro. Unlike 5gon12eder's solution, this implementation gives 0 for BITS_TO_REPRESENT(0), which is arguably correct. This BITS_TO_REPRESENT(N) function returns the number of bits to represent an unsigned integer less than or equal to nonnegative integer N; storing a signed number of magnitude N would need one additional bit.
#define NEEDS_BIT(N, B) (((unsigned long)N >> B) > 0)
#define BITS_TO_REPRESENT(N) \
(NEEDS_BIT(N, 0) + NEEDS_BIT(N, 1) + \
NEEDS_BIT(N, 2) + NEEDS_BIT(N, 3) + \
NEEDS_BIT(N, 4) + NEEDS_BIT(N, 5) + \
NEEDS_BIT(N, 6) + NEEDS_BIT(N, 7) + \
NEEDS_BIT(N, 8) + NEEDS_BIT(N, 9) + \
NEEDS_BIT(N, 10) + NEEDS_BIT(N, 11) + \
NEEDS_BIT(N, 12) + NEEDS_BIT(N, 13) + \
NEEDS_BIT(N, 14) + NEEDS_BIT(N, 15) + \
NEEDS_BIT(N, 16) + NEEDS_BIT(N, 17) + \
NEEDS_BIT(N, 18) + NEEDS_BIT(N, 19) + \
NEEDS_BIT(N, 20) + NEEDS_BIT(N, 21) + \
NEEDS_BIT(N, 22) + NEEDS_BIT(N, 23) + \
NEEDS_BIT(N, 24) + NEEDS_BIT(N, 25) + \
NEEDS_BIT(N, 26) + NEEDS_BIT(N, 27) + \
NEEDS_BIT(N, 28) + NEEDS_BIT(N, 29) + \
NEEDS_BIT(N, 30) + NEEDS_BIT(N, 31) \
)
BITS_TO_REPRESENT is almost a base-2 logarithm. Since the default conversion from floating point to an integer is truncation, the integer version of a base-2 logarithm corresponds to the floating-point calculation floor(log(N)/log(2)). BITS_TO_REPRESENT(N) returns one greater than floor(log(N)/log(2)).
For example:
BITS_TO_REPRESENT(7)is3, whereasfloor(log(7)/log(2))is2.BITS_TO_REPRESENT(8)is4, whereasfloor(log(8)/log(2))is3.
Glen Ragan
- 41
- 4
-
Thank you for this answer. This solution is short and simple enough to be generalised for n-bit architectures with a simple script. – wizzwizz4 May 28 '17 at 14:06
0
Best bet, use a c++14 constexpr variable template:
template <unsigned int x>
constexpr enable_if_t<x != 0, int> log2 = 1 + log2<x / 2U>;
template <>
constexpr int log2<1U> = 0;
Jonathan Mee
- 37,899
- 23
- 129
- 288
0
Here is a modified version of the top answer that does the same thing.
#define REPRESENT_IN_X_BITS(n, x)\
(\
( ((1U<<x)-1U) >= (n) ) ? 1 : 0\
)
#define BITS_NEEDED(number)\
(\
number == 1 || number == 0 ? 1 : \
REPRESENT_IN_X_BITS(number, 1) ? 1 :\
REPRESENT_IN_X_BITS(number, 2) ? 2 :\
REPRESENT_IN_X_BITS(number, 3) ? 3 :\
REPRESENT_IN_X_BITS(number, 4) ? 4 :\
REPRESENT_IN_X_BITS(number, 5) ? 5 :\
REPRESENT_IN_X_BITS(number, 6) ? 6 :\
REPRESENT_IN_X_BITS(number, 7) ? 7 :\
REPRESENT_IN_X_BITS(number, 8) ? 8 :\
REPRESENT_IN_X_BITS(number, 9) ? 9 :\
REPRESENT_IN_X_BITS(number, 10) ? 10 :\
REPRESENT_IN_X_BITS(number, 11) ? 11 :\
REPRESENT_IN_X_BITS(number, 12) ? 12 :\
REPRESENT_IN_X_BITS(number, 13) ? 13 :\
REPRESENT_IN_X_BITS(number, 14) ? 14 :\
REPRESENT_IN_X_BITS(number, 15) ? 15 :\
REPRESENT_IN_X_BITS(number, 16) ? 16 :\
REPRESENT_IN_X_BITS(number, 17) ? 17 :\
REPRESENT_IN_X_BITS(number, 18) ? 18 :\
REPRESENT_IN_X_BITS(number, 19) ? 19 :\
REPRESENT_IN_X_BITS(number, 20) ? 20 :\
REPRESENT_IN_X_BITS(number, 21) ? 21 :\
REPRESENT_IN_X_BITS(number, 22) ? 22 :\
REPRESENT_IN_X_BITS(number, 23) ? 23 :\
REPRESENT_IN_X_BITS(number, 24) ? 24 :\
REPRESENT_IN_X_BITS(number, 25) ? 25 :\
REPRESENT_IN_X_BITS(number, 26) ? 26 :\
REPRESENT_IN_X_BITS(number, 27) ? 27 :\
REPRESENT_IN_X_BITS(number, 28) ? 28 :\
REPRESENT_IN_X_BITS(number, 29) ? 29 :\
REPRESENT_IN_X_BITS(number, 30) ? 30 :\
REPRESENT_IN_X_BITS(number, 31) ? 31 : 32\
)
// First we check if the number is zero or one. In either case, we will need
// one bit to represent them.
// Then we check if it can be represented with that number of bits and return
// that exact number if so.
//
// If it could not be represented with 32 bits, it is assumed to be 32
// since we have exhausted all other possibilities.
The helper macro shifts 1 by x, the number of bits we are testing. For example, if we are checking if a number can be represented with two bits, we shift 1 by 2, which is four. Then we subtract by 1. This number is the maximum that can be represented with this number of bits, so the supplied number must be less than or equal to it. We return 1 or 0 for true and false, respectively.
The main macro checks if the number can be represented with that many bits and chains to the next ternary clause if it cannot. If 31 does not work, 32 bits is assumed because all other possibilities are eliminated. In the case of zero, it will return 1 because we always need at least one bit to store something.
This macro is not a replacement for log2. It only tells how many bits are needed.
A common use case would be bit field struct members.
enum {
myenum_0
myenum_1
myenum_2
myenum_opts
};
// Note: Untested
typedef struct {
int i:BITS_NEEDED(myenum_opts-1);
}example;
This allows us to add new members to the enum without having to update the bit field.
Joey L. Q.
- 41
- 1