Compute the minimum or maximum of two integers without branching

In this blog post, I will teach you how to write a C/C++ program to compute the minimum or maximum of two integers without branching. After reading this detailed guide post I believe you can write an efficient program to compute the minimum or maximum of two integers without branching.

I have already written the C program to find the largest of two given numbers, But here you will learn how to find the maximum of two numbers without using the if-else and ternary operators.

🤔I believe now you are thinking about how you can find the largest and smallest number.

Answer if your question is so simple, you can find the minimum (min) or maximum (max) number without the branching with the help of a bitwise operator.

Let’s see the problem statements for this question.

Problem Statement: Given two integers, find their minimum and maximum without using branching.

Disclaimer: Try to solve the problem yourself first otherwise it would be not worth solving this problem.

 

Using XOR and comparison operator:

Let’s assume ‘a’ and ‘b’ are two integer numbers and “result” is another integer variable that contains the result of the computation. So to compute the minimum number we have to write the below expression.

Expression for Minimum:

result = b ^ ((a ^ b) & -(a < b)); // min(a, b)

In above expression,if a < b, then -( a < b) become -1, so it behave like below expression

result = b ^ ((a ^ b) & ~0);

result =  b ^ a ^ b; // b^b is zero

result = a ^ 0; // oring with 0 does not effect

result = a; //minimum number

 

Expression for Maximum:

result = a ^ ((a ^ b) & -(a < b)); // max(a, b)

In above expression,if a > b, then -( a < b) become 0, so it behave like below expression

result = a ^ ((a ^ b) & -(0));

result = a ^ 0; // oring with 0 does not effect

result = a; //Maximum number

 

C program to compute the minimum or maximum of two integers without branching:

/*
C program to Compute the minimum
or maximum of two integers without
branching.
*/
#include<stdio.h>

//Function to find minimum of x and y
int findMin(int x, int y)
{
    return y ^ ((x ^ y) & -(x < y));
}

//Function to find maximum of x and y
int findMax(int x, int y)
{
    return x ^ ((x ^ y) & -(x < y));
}


int main()
{
    int x = 15;
    int y = 6;
    printf("Minimum of %d and %d is ", x, y);
    //find minimum
    const int min = findMin(x,y);
    printf("%d\n\n", min);

    printf("Maximum of %d and %d is ", x, y);
    //find maximum
    const int max = findMax(x,y);
    printf("%d\n\n", max);

    return 0;
}

Output:

Minimum of 15 and 6 is 6
Maximum of 15 and 6 is 15

 

C++ program to compute the minimum or maximum of two integers without branching:

/*
C program to Compute the minimum
or maximum of two integers without
branching.
*/
#include<iostream>
using std::cout;
using std::endl;

//Function to find minimum of x and y
int findMin(int x, int y)
{
    return y ^ ((x ^ y) & -(x < y));
}

//Function to find maximum of x and y
int findMax(int x, int y)
{
    return x ^ ((x ^ y) & -(x < y));
}


int main()
{
    int x = 15;
    int y = 6;
    cout<<"Minimum of "<<x<<" and "<<y<<" is ";
    //find minimum
    const int minValue = findMin(x,y);
    cout<<minValue<<endl;

    //find maximum
    cout<<"Maximum of "<<x <<" and "<<y<<" is ";
    const int maxValue = findMax(x,y);
    cout<<maxValue<<endl;

    return 0;
}

Output:

Minimum of 15 and 6 is 6
Maximum of 15 and 6 is 15

 

Recommended Post