0

I have buckets whose size is exponentially increasing by 2. So, the buckets are: (0-1], (1-2], (2-4], (4-8], (8-16]....

Given a number, how can I efficiently tell which bucket index it falls in? One option I can think of is to use log2(N) and round it up to the next integer. But can a simple mathematical formula be derived that will be faster than using log in C++? This will be called in a very latency sensitive path so even microseconds matter.

RandomQuestion
  • 6,778
  • 17
  • 61
  • 97
  • 4
    Does this answer your question? [Rounding up to next power of 2](https://stackoverflow.com/questions/466204/rounding-up-to-next-power-of-2) – Woodford Apr 06 '21 at 23:42
  • The pattern is pretty obviously logarithmic (as you pointed out). If you're going to do better, I suspect you're going to have to "cheat" by making assumptions or knowing something in advance. Is there any pattern to the input or any assumptions you can make around the ordering or range of input data? ... Or check out that link @Woodford posted because that looks really neat. – Brent Writes Code Apr 06 '21 at 23:43
  • [This](https://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers) answers the question for integers. For floating-point you can read the exponent field of the floating point number, but it won't work in some edge cases. – interjay Apr 06 '21 at 23:50
  • Thanks, These linked questions should help me. – RandomQuestion Apr 06 '21 at 23:52

1 Answers1

1

Just use std::count_lzero - it counts the leading (more significant) zeros before the first 1 bit in the argument, which effectively yields a log2 function for integers. You can expect it to be implemented using the most efficient machine code the platform supports, which in the case of x86s is a dedicated instruction - faster than anything you could write using bit-twiddling hackery.

Tony Delroy
  • 102,968
  • 15
  • 177
  • 252