Find out to what extent the 2 ranges include the number? (In C)

Question

As in whether he falls into 2 ^ 3 - 2 ^ 4, 2 ^ 4 - 2 ^ 5, etc. The returned number will be the EXPONENT itself (minus the offset).

How can this be done extremely quickly and efficiently, as much as possible? This function will be called a lot in a program that TRUE depends on speed. This is my current code, but it is too inefficient because it uses a for loop.

static inline size_t getIndex(size_t numOfBytes) { int i = 3; for (; i < 32; i++) { if (numOfBytes < (1 << i)) return i - OFFSET; } return (NUM_OF_BUCKETS - 1); } 

Thank you very much!

Answer 1

What you need is just log ₂ (n), as far as I can tell.

It might be worth cheating and using some built-in assembly if your target architecture (s) have instructions that can do this. See Wikipedia entry on finding the first set for a discussion and information on hardware support.

Answer 2

One way to do this is to find the highest order bit that is set to 1. I am trying to think if this is effective, though, since you still have to do n checks in the worst case.

Maybe you can use the binary search style if you check if it is more than 2 ^ 16, if so, check if it is more than 2 ^ 24 (if there are 32 bits), and if not, then check, 2 ^ 20 and etc. This will be a log check (n), but I'm not sure about the effectiveness of bit checking and full int comparison.

You can get some primary data.

Answer 3

There is a particularly efficient algorithm using the Bruijn sequences described in Sean Eron Anderson, excellent Twiddling Hacks Bit :

 uint32_t v; // find the log base 2 of 32-bit v int r; // result goes here static const int MultiplyDeBruijnBitPosition[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; v |= v >> 1; // first round down to one less than a power of 2 v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27]; 

It works in 13 operations without branching!

Answer 4

Basically you are trying to calculate: floor(log2(x))

Take the logarithm to base 2, then take the word.

The most portable way to do this in C is to use the logf() function, which finds the log in the e database and then configures: log2(x) == logf(x) / logf(2.0)

See the answer here: How to write a database (2) in c / C ++

If you just pass the resulting float value to int , you evaluate floor() at the same time.

But if this is available to you and you can use it, there is a very fast way to calculate log2() floating point numbers: logbf()

On the man page:

  The inte- ger constant FLT_RADIX, defined in <float.h>, indicates the radix used for the system floating-point representation. If FLT_RADIX is 2, logb(x) is equal to floor(log2(x)), except that it is probably faster. 

http://linux.die.net/man/3/logb

If you think about how floating point numbers are stored, you understand that the value of floor(log2(x)) is part of the number, and if you just extract that value, you're done. A bit biasing and bit-masking, and subtract the bias from the exponent (or technically the “value”), and there you have it. The fastest way to calculate floor(log2(x)) for any float x value.

http://en.wikipedia.org/wiki/Single_precision

But in fact, logbf() converts the result to a float before passing it and handles the errors. If you write your own function to extract the exponent as an integer, it will be a little faster, and the integer will be what you want anyway. If you want to write your own function, you need to use C union to access the bits inside the float; When you try to play with pointers, you will get warnings or errors related to the "type", at least on the GCC. I will give details on how to do this, if you ask. I wrote this code before as an inline function.

If you only have a small range of numbers to test, you can overlay numbers on an integer, and then use the lookup table.

Answer 5

You can use floating point representation:

 double n_bytes = numOfBytes 

Taking exponent bits should give you the result, since floating numbers are represented as:

 (-1)^SX (1. + M) X 2^E 

Where: S - Sign M - Mantissa E - Exponent

To create a mask and a shift, you will need to read about the exact bit pattern of the floating-point type used.

Floating point CPU support does most of the work for you.

An even better way is to use the built-in function:

 double frexp (double x, int * exp ); 

Floating point

Answer 6

This usually happens on any machine with a hardware floating point module:

 ((union { float val; uint32_t repr; }){ x }.repr >> 23) - 0x7f 

The only assumptions he makes are that the floating point corresponds to IEEE and an integer and consistent floating point number, both of which are true mainly in all real-world systems (of course, all modern ones).

Edit: When I used this in the past, I did not need it for large numbers. Eric points out that this will give the wrong result for ints that don't fit in a float. Here is a fixed version (albeit possibly slow) that corrects and maintains values ​​up to 52 bits (in particular, all 32-bit positive integer inputs):

 ((union { double val; uint64_t repr; }){ x }.repr >> 52) - 0x3ff 

Also note that I assume that x is a positive (not just non-negative, but also non-zero) number. If x negative, you get a dummy result, and if x is 0, you get a big negative result (approximating negative infinity as a logarithm).

Answer 7

 #include <Limits.h> // For CHAR_BIT. #include <math.h> // For frexp. #include <stdio.h> // For printing results, as a demonstration. // These routines assume 0 < x. /* This requires GCC (or any other compiler that supplies __builtin_clz). It should perform well on any machine with a count-leading-zeroes instruction or something similar. */ static int log2A(unsigned int x) { return sizeof x * CHAR_BIT - 1 - __builtin_clz(x); } /* This requires that a double be able to exactly represent any unsigned int. (This is true for 32-bit integers and 64-bit IEEE 754 floating-point.) It might perform well on some machines and poorly on others. */ static int log2B(unsigned int x) { int exponent; frexp(x, &exponent); return exponent - 1; } int main(void) { // Demonstrate the routines. for (unsigned int x = 1; x; x <<= 1) printf("0x%08x: log2A -> %2d, log2B -> %2d.\n", x, log2A(x), log2B(x)); return 0; }