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?

Était-ce utile?

La 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?

Autres conseils

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.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top