log2 [SOLVED]

Projects Programming
1

I'm trying to find a cheap way of calculating log2. To be more precise, I want to identify the bit position of 0B10000000, 0B01000000,... 0B00000001.

When I say 'cheap', I'd rather not use log(x)/log(2) and need it to be #define'd in a macro, so the usual shift loops don't necessarily work. I've tried Google but can't seem to phrase the query that produces results.

The purpose is to #define a BUFFER_LENGTH of 8, 16, 32, 64, 128 or 256 bytes, using 3, 4, 5, 6, 7 or 8 later in a shift operation that will divide the sum of the contents of the buffer by the number of elements in the buffer. All of this needs to be performed by the pre-processor. Right now I have this

#define	BUFFER_LENGTH	32
#ifndef BUFFER_LENGTH
    #define BUFFER_LENGTH 256
#endif
#if     BUFFER_LENGTH == 8
    #define BUFFER_INDEX    3
#elif   BUFFER_LENGTH == 16
    #define BUFFER_INDEX    4
#elif   BUFFER_LENGTH == 32
    #define BUFFER_INDEX    5
#elif   BUFFER_LENGTH == 64
    #define BUFFER_INDEX    6
#elif   BUFFER_LENGTH == 128
    #define BUFFER_INDEX    7
#else
    #define BUFFER_INDEX    8
#endif

but, as usual, I'm convinced there's a better way. Any ideas?

2

Why don't you go the opposite way and just define BUFFER_INDEX, then it's easy to create BUFFER_LENGTH through a bit shifting that the processor will do for you?

const byte BUFFER_INDEX  =  5;
const size_t BUFFER_LENGTH = 1 << BUFFER_INDEX;
3

Built-in Count leading zeros Function ?: int __builtin_ctz (unsigned int x) ?

4

Brilliant. It works. K++

I was thinking it might be more intuitive to define the length of the buffer.

5

@ard_newbie, brilliant also. K++

For info ctz is count trailing zeros, clz is count leading zeros.

6

DKWatson:
@ard_newbie, brilliant also. K++

For info ctz is count trailing zeros, clz is count leading zeros.

Indeed +1 for that answer as that would meet your need for being more intuitive to define the length of the buffer.

const size_t bufLength = 32;
const byte bufIndex = __builtin_ctz(bufLength);

void setup() {
  Serial.begin(115200);
  Serial.print(bufIndex);
}

void loop() {}

Note that if you want a a larger buffer then __builtin_ctzl() will work on an unsigned long

(I prefer const to #define as they carry a type which helps the compiler make better decisions)

7

Problem with const is that I need the value to set the length of an array.

8

DKWatson:
Problem with const is that I need the value to set the length of an array.

not sure why this is a problem?

const byte BUFFER_INDEX  =  5;
const size_t BUFFER_LENGTH = 1 << BUFFER_INDEX;
uint8_t buffer[BUFFER_LENGTH];

or

const size_t bufLength = 32;
const byte bufIndex = __builtin_ctz(bufLength);
uint8_t buffer[bufLength];

will work

9

I prefer @J-M-L's original suggestion because the '__builtin_ctz' technique won't give the desired result if you specify a BUFFER_LENGTH value that's not a power of 2.

10

@gfvalvo I appreciate that and it does have merit. It force the buffer to be of a prescribed length which needs to be a power of 2. The index created by the value is later used also as the FIFO buffer pointer so there is automatic rollover. So, like everything else, fast, good, cheap - pick two.