Minimum of three numbers [duplicate]

StackOverflow https://stackoverflow.com/questions/23147634

  •  05-07-2023
  •  | 
  •  

Question

I'm working on algorithm that heavily uses min() function to find the smallest number of three numbers. Program is written in C/C++ language. Temporarily I use

min( number1, min(number2, number3))

But it took about 90% of CPU time. What's the fastest solution of this problem? Maybe any bitwise trick or something?

Was it helpful?

Solution

As long as your compiler is optimizing that's probably as good as you're going to get. 

#include <algorithm>

int test(int i, int j, int k)
{
  return std::min(i, std::min(j, k));
}

compiled with g++ -S -c -O3 test.cpp I get

cmpl    %edi, %esi
movl    %edx, %eax
cmovg   %edi, %esi
cmpl    %edx, %esi
cmovle  %esi, %eax
ret

Perhaps you didn't pass any optimization flags when compiling?

OTHER TIPS

Check this solution if it helps you

quoting below code from above reference

int x;  // we want to find the minimum of x and y
int y;   
int r;  // the result goes here 

r = y ^ ((x ^ y) & -(x < y)); // min(x, y)

One more trick under same heading is

r = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // min(x, y)

You can remove -1 from trick 2. It works only on some systems and is not portable.

You can extend this idea to find minimum of 3 numbers.

static inline int min3(int x, int y, int z)
{
  register int r, d;
  d = x - y;
  r = y + (d & (d >> (sizeof(int) * CHAR_BIT))); /* add -1 if required */
  d = r - z;
  r = z + (d & (d >> (sizeof(int) * CHAR_BIT))); /* add -1 if required */
  return r;
}

If range of your numbers is very less, you can even use some look up, or more efficient but hack.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top