Fast integer logarithm for a special case

Question

I have integer values ​​from 32-8191 that I want to display on a roughly logarithmic scale. If I used base 2, I could just count the initial zero bits and map them to 8 slots, but that's too cool; I need 32 slots (and more would be better, but I need them to match the bits in a 32-bit value), which goes to the base of about 1.18-1.20 for the logarithm. Does anyone have some tricks for calculating this value or a reasonable approximation very quickly?

My intuition is to split the range into 2 or 3 subranges with conditional expressions and use a small lookup table for each, but I wonder if there is any trick I could do with count-leading-zeros, and then clarify the result, especially since the results do not have to be accurate, but roughly logarithmic.

Answer 1

Why not use the next two bits different from the leading bit. First you can split the number into 8 bits, and the next two bits - divide each bit into four. In this case, you can use a very fast switch operation.

Change If you think using a logarithm is a viable solution. Here is the general algorithm:

Let a be the base of the logarithm, and the range (b_min, b_max) = (32,8191) . You can find the base using the formula:

 log(b_max/b_min) / log(a) = 32 bin 

which give you a~1.1892026 . If you use this as a logarithm base, you can map the range (b_min, b_max) to (log_a(b_min), log_a(b_max)) = (20.0004,52.0004) .

Now all you have to do is subtract the whole element 20.0004 to get the range (0,32) . It ensures that all elements are logarithmically homogeneous. Done

Note. Or the item may fall out of range due to a numerical error. You must calculate it to get the exact value.

Note2: log_a (b) = log (b) / log (a)

Answer 2

Table search is one of the options, this table is not so big. If the 8K table is too large and you have the initial zeros command, you can use the table lookup in the first few bits.

 nbits = 32 - count_leading_zeros(v) # number of bits in number highbits = v >> (nbits - 4) # top 4 bits. Top bit is always a 1. log_base_2 = nbits + table[highbits & 0x7] 

The table you are filling with some approximation log_2

 table[i] = approx(log_2(1 + i/8.0)) 

If you want to stay in integer arithmetic, multiply the last line by a convenient factor.

Answer 3

Answer. I just founded in IEEE 754 floating point:

 ((union { float v; uint32_t r; }){ x }.r >> 21 & 127) - 16 

It maps 32-8192 to 0-31 roughly logarithmically (same as hwlau's answer).

Improved version (cut useless bitwise and):

 ((union { float v; uint32_t r; }){ x }.r >> 21) - 528