1

Hi I am trying to create a macro that computes the base 2 logarithm of a number in C. The number is supposed to be the size of a table that is #defined also as seen below.

I searched around and found this site that contains an implementation of base2log https://graphics.stanford.edu/~seander/bithacks.html

uint8_t base2log(uint16_t value){

    uint8_t result = 0; // r will be lg(v)

    while (value >>= 1)
    {
        result++;
    }
    return result;
}

My first idea is to now create the macro as:

#define SIZE 256
#define BASE2LOG (base2log(SIZE))

...but this doesn't look like a very elegant solution, because even though BASE2LOG should be defined at compile time it will still need to call a function everytime this appears in the code. I thought of perhaps assigning BASE2LOG in a global variable but I am sure that there must be something more concise and proper than this.

Is there a way to do this?

Thanks for your time.

4
  • 4
    Consider doing it the other way around: #define BASE2LOG 8 and #define SIZE (1 << BASE2LOG).
    – Wintermute
    Mar 26, 2015 at 16:03
  • if you are using gcc, you can still use it with uint8_t base2log(uint16_t value) __attribute__((const)) such that compiler may have a chance to optimize some out.(but not as good as Wintermute's).
    – Jason Hu
    Mar 26, 2015 at 16:08
  • Wouldn't you love to have constexpr ;-). Mar 27, 2015 at 0:59
  • I have to admit Wintermute's idea is pretty smart. I would prefer to use Ulfalizer's solution in my code though because it is more intuitive to just use a macro LOG2(n). Thanks for your help everyone.
    – Satrapes
    Mar 27, 2015 at 10:07

2 Answers 2

2

Here's a pure macro solution that allows the logarithm to be computed at compile time and used where an integer constant expression is expected in C -- e.g., when specifying the length of a (non-variable length) array. Integer constant expression is just standardese for an expression the compiler must be able to evaluate at compile time.

I've seen variants of this in other places (and there's one in Macro to compute number of bits needed to store a number n for example), so I can't take credit. I could write up how it works at least.

// Computes the base 2 logarithm of a 16-bit number. Meant to be used
// at compile time.
#define LOG2(n)   ((n) & 0xFF00 ? 8 + LOG2_8((n) >> 8) : LOG2_8(n))
#define LOG2_8(n) ((n) & 0xF0   ? 4 + LOG2_4((n) >> 4) : LOG2_4(n))
#define LOG2_4(n) ((n) & 0xC    ? 2 + LOG2_2((n) >> 2) : LOG2_2(n))
#define LOG2_2(n) ((n) & 0x2    ? 1 : 0)

The truncated base 2 logarithm of a number is just the index of the highest 1 bit (with 0 being the index of the least significant bit). To find the highest 1 bit, a type of binary search can be used.

In LOG2() (the main macro), we use (n) & 0xFF00 ? ... to test if the high byte contain a 1 bit. If it does, then the index of the highest 1 bit in n is 8 plus the index of the highest 1 bit within the high byte of n. If it doesn't, then the index of the highest 1 bit is just the index of the highest 1 bit within the low byte.

To get the high byte, we do (n) >> 8. The remaining macros only look at the low byte, so there's no need to mask.

The LOG2_8() macro computes the index of the highest 1 bit within a byte. It uses the same logic as above with a halved interval. If the high 4 bits contain a 1 bit, then the index of the highest 1 bit is 4 plus the index of the highest 1 bit within the high 4 bits. Otherwise, it's the index of the highest bit within the low 4 bits.

LOG_4() works exactly the same way.

For the base case, LOG2_2(1) == 0 and LOG2_2(2) == 1. LOG2_2(0) (which is mathematically undefined) happens to become 0 too.

The macro can be generalized to handle larger types in the obvious way. Shifting by a value larger than the width of the type is strictly undefined (not sure how reliable it is in practice across compilers) and needs to be watched out for. One way to make it safe would be to add a cast (this assumes C99+):

#define LOG2(n)    LOG2_64((uint64_t)(n))
#define LOG2_64(n) ... /* as usual. */
...

More straightforward (and slightly spammier) solutions are possible too, e.g.

#define LOG2(n)   \
  ((n) < 2  ? 0 : \
   (n) < 4  ? 1 : \
   (n) < 8  ? 2 : \
   (n) < 16 ? 3 : \
   (n) < 32 ? 4 : \
   (n) < 64 ? 5 : \
   ...

(C99 has //-style comments by the way, in case someone felt like complaining. ;)

2

Yet another solution. This one provides an error if the number exceeds the maximum value.

#define MIN_BITS(n) (1+(n>1)+(n>3)+(n>7)+(n>0x0f)+(n>0x1f)+(n>0x3f)+(n>0x7f)+   \
                    (n>0x0ff)+(n>0x1ff)+(n>0x3ff)+(n>0x7ff)+                    \
                    (n>0xfff)+(n>0x1fff)+(n>0x3fff)+(n>0x7fff)+                \
                    ((n>0xffff)?100:0))
1
  • 1
    Yeah, it was a quick and dirty, full of typos. Sorry! (fixed original)
    – Mr Stinky
    May 23, 2015 at 7:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.