Fastest way to determine if an integer is between two integers (inclusive) with known sets of values

by

There’s an old trick to do this with only one comparison/branch. Whether it’ll really improve speed may be open to question, and even if it does, it’s probably too little to notice or care about, but when you’re only starting with two comparisons, the chances of a huge improvement are pretty remote. The code looks like:

// use a < for an inclusive lower bound and exclusive upper bound
// use <= for an inclusive lower bound and inclusive upper bound
// alternatively, if the upper bound is inclusive and you can pre-calculate
//  upper-lower, simply add + 1 to upper-lower and use the < operator.
    if ((unsigned)(number-lower) <= (upper-lower))
        in_range(number);

With a typical, modern computer (i.e., anything using twos complement), the conversion to unsigned is really a nop — just a change in how the same bits are viewed.

Note that in a typical case, you can pre-compute upper-lower outside a (presumed) loop, so that doesn’t normally contribute any significant time. Along with reducing the number of branch instructions, this also (generally) improves branch prediction. In this case, the same branch is taken whether the number is below the bottom end or above the top end of the range.

As to how this works, the basic idea is pretty simple: a negative number, when viewed as an unsigned number, will be larger than anything that started out as a positive number.

In practice this method translates number and the interval to the point of origin and checks if number is in the interval [0, D], where D = upper - lower. If number below lower bound: negative, and if above upper bound: larger than D.

More Related Contents:

  1. Fastest way to get the integer part of sqrt(n)?
  2. How to find out the date of the first day of week from the week number in C++
  3. Which yields faster code?
  4. How approximation search works
  5. How to overload std::swap()
  6. Why is my program slow when looping over exactly 8192 elements?
  7. Why does C++ compilation take so long?
  8. What is the efficient way to count set bits at a position or lower?
  9. How can I write a power function myself?
  10. Increasing accuracy of solution of transcendental equation
  11. Efficient way of storing Huffman tree
  12. How do exceptions work (behind the scenes) in c++
  13. Does a C++11 range-based for loop condition get evaluated every cycle?
  14. linux perf: how to interpret and find hotspots
  15. Performance of dynamic_cast?
  16. how do I make a portable isnan/isinf function
  17. Is there a 128 bit integer in C++?
  18. What is the Fastest Method for High Performance Sequential File I/O in C++?
  19. C++ cout printing slowly
  20. Confusion between C++ and OpenGL matrix order (row-major vs column-major)
  21. Fastest way to get a positive modulo in C/C++
  22. Do c++ templates make programs slow?
  23. shared_ptr: horrible speed
  24. OpenSouce C/C++ Math expression parser Library [closed]
  25. Simple for() loop benchmark takes the same time with any loop bound
  26. self made pow() c++
  27. New (std::nothrow) vs. New within a try/catch block
  28. C++ most efficient way to convert string to int (faster than atoi)
  29. Finding square root without using sqrt function?
  30. Is there any advantage to using pow(x,2) instead of x*x, with x double?

Leave a Comment