Posted on by Kalkicode
Code Bit Logic

Smallest of three integers without comparison operators

In this article, we will explore an interesting problem - finding the smallest of three integers without using comparison operators. Comparison operators like '<', '>', '<=', '>=' are commonly used to compare two values and determine their order. However, we will devise an alternative approach to find the minimum value among three integers without using these comparison operators. We'll achieve this by leveraging bitwise manipulation and arithmetic operations.

Problem Statement

The problem is to develop an algorithm that takes three integers as input and returns the smallest of the three without using any comparison operators (e.g., '<', '>').

Explanation with Example

Consider three integers: 5, 8, and 3. The conventional way of finding the minimum among these integers would be using comparison operators like 'if' statements or 'min' functions. However, we aim to solve this problem using a different approach.

Pseudocode

Before we delve into the algorithm, let's outline the pseudocode for finding the minimum of three integers:

Function minValue(a, b)
    Return b + (((a - b) >> (sizeof(int) * 7)) & (a - b))
    
Function smallest(a, b, c)
    result = minValue(a, minValue(b, c))
    Print "Minimum is : " + result

Algorithm Explanation

  1. The minValue function calculates the minimum of two integers a and b without using comparison operators. It achieves this using bitwise manipulation and arithmetic operations.
  2. The smallest function takes three integers a, b, and c as input and calls the minValue function twice to find the minimum among the three.
  3. The result is then printed on the screen.

Algorithm Execution

Let's execute the algorithm with some example test cases:

  1. smallest(3, -2, -6)

    • The minValue(-2, -6) is called first, which returns -6 as the minimum.
    • Then, minValue(3, -6) is called, and it returns -6 as well.
    • Thus, the overall minimum is -6.
  2. smallest(5, 9, 7)

    • The minValue(9, 7) is called first, which returns 7 as the minimum.
    • Then, minValue(5, 7) is called, and it returns 5 as the overall minimum.
    • Thus, the overall minimum is 5.
  3. smallest(-2, -2, -1)

    • The minValue(-2, -2) is called first, which returns -2 as the minimum.
    • Then, minValue(-2, -1) is called, and it returns -2 as the overall minimum.
    • Thus, the overall minimum is -2.
  4. smallest(12, 3, 4)

    • The minValue(3, 4) is called first, which returns 3 as the minimum.
    • Then, minValue(12, 3) is called, and it returns 3 as the overall minimum.
    • Thus, the overall minimum is 3.

Code Solution

// C program for
// Smallest of three integers without comparison operators
#include <stdio.h>

// Return a minimum value of given two numbers
int minValue(int a, int b)
{
  return b + (((a - b) >> (sizeof(int) *7)) & (a - b));
}
// Handles the request of finding minimum of given three numbers
void smallest(int a, int b, int c)
{
  // Display given value
  printf(" A : %d\n", a);
  printf(" B : %d\n", b);
  printf(" C : %d\n", c);
  int result = minValue(a, minValue(b, c));
  // Display calculated minimum
  printf(" Minimum is : %d\n\n", result);
}
int main()
{
  // Test cases
  smallest(3, -2, -6);
  smallest(5, 9, 7);
  smallest(-2, -2, -1);
  smallest(12, 3, 4);
  return 0;
}

Output

 A : 3
 B : -2
 C : -6
 Minimum is : -6

 A : 5
 B : 9
 C : 7
 Minimum is : 5

 A : -2
 B : -2
 C : -1
 Minimum is : -2

 A : 12
 B : 3
 C : 4
 Minimum is : 3
/*
  Java Program for
  Smallest of three integers without comparison operators
*/
class Comparison
{
  // Return a minimum value of given two numbers
  public int minValue(int a, int b)
  {
    return b + (((a - b) >> (Integer.SIZE-1)) & (a - b));
  }
  // Handles the request of finding minimum of given three numbers
  public void smallest(int a, int b, int c)
  {
    // Display given value
    System.out.print(" A : " + a + "\n");
    System.out.print(" B : " + b + "\n");
    System.out.print(" C : " + c + "\n");
    int result = minValue(a, minValue(b, c));
    // Display calculated minimum
    System.out.print(" Minimum is : " + result + "\n\n");
  }
  public static void main(String[] args)
  {
    Comparison task = new Comparison();
    // Test cases
    task.smallest(3, -2, -6);
    task.smallest(5, 9, 7);
    task.smallest(-2, -2, -1);
    task.smallest(12, 3, 4);
  }
}

Output

 A : 3
 B : -2
 C : -6
 Minimum is : -6

 A : 5
 B : 9
 C : 7
 Minimum is : 5

 A : -2
 B : -2
 C : -1
 Minimum is : -2

 A : 12
 B : 3
 C : 4
 Minimum is : 3
// Include header file
#include <iostream>

#include<limits.h>

using namespace std;
/*
  C++ Program for
  Smallest of three integers without comparison operators
*/
class Comparison
{
  public:
    // Return a minimum value of given two numbers
    int minValue(int a, int b)
    {
      return b + (((a - b) >> (sizeof(int) *7)) &(a - b));
    }
  // Handles the request of finding minimum of given three numbers
  void smallest(int a, int b, int c)
  {
    // Display given value
    cout << " A : " << a << "\n";
    cout << " B : " << b << "\n";
    cout << " C : " << c << "\n";
    int result = this->minValue(a, this->minValue(b, c));
    // Display calculated minimum
    cout << " Minimum is : " << result << "\n\n";
  }
};
int main()
{
  Comparison task = Comparison();
  // Test cases
  task.smallest(3, -2, -6);
  task.smallest(5, 9, 7);
  task.smallest(-2, -2, -1);
  task.smallest(12, 3, 4);
  return 0;
}

Output

 A : 3
 B : -2
 C : -6
 Minimum is : -6

 A : 5
 B : 9
 C : 7
 Minimum is : 5

 A : -2
 B : -2
 C : -1
 Minimum is : -2

 A : 12
 B : 3
 C : 4
 Minimum is : 3
// Include namespace system
using System;
/*
  C# Program for
  Smallest of three integers without comparison operators
*/
public class Comparison
{
  // Return a minimum value of given two numbers
  public int minValue(int a, int b)
  {
    return b + (((a - b) >> (sizeof(int) * 7)) & (a - b));
  }
  // Handles the request of finding minimum of given three numbers
  public void smallest(int a, int b, int c)
  {
    // Display given value
    Console.Write(" A : " + a + "\n");
    Console.Write(" B : " + b + "\n");
    Console.Write(" C : " + c + "\n");
    int result = minValue(a, minValue(b, c));
    // Display calculated minimum
    Console.Write(" Minimum is : " + result + "\n\n");
  }
  public static void Main(String[] args)
  {
    Comparison task = new Comparison();
    // Test cases
    task.smallest(3, -2, -6);
    task.smallest(5, 9, 7);
    task.smallest(-2, -2, -1);
    task.smallest(12, 3, 4);
  }
}

Output

 A : 3
 B : -2
 C : -6
 Minimum is : -6

 A : 5
 B : 9
 C : 7
 Minimum is : 5

 A : -2
 B : -2
 C : -1
 Minimum is : -2

 A : 12
 B : 3
 C : 4
 Minimum is : 3
<?php
/*
  Php Program for
  Smallest of three integers without comparison operators
*/
class Comparison
{
  // Return a minimum value of given two numbers
  public  function minValue($a, $b)
  {
    return $b + ((($a - $b) >> (8 * (PHP_INT_SIZE - 1))) & ($a - $b));
  }
  // Handles the request of finding minimum of given three numbers
  public  function smallest($a, $b, $c)
  {
    // Display given value
    echo " A : ". $a ."\n";
    echo " B : ". $b ."\n";
    echo " C : ". $c ."\n";
    $result = $this->minValue($a, $this->minValue($b, $c));
    // Display calculated minimum
    echo " Minimum is : ". $result ."\n\n";
  }
}

function main()
{
  $task = new Comparison();
  // Test cases
  $task->smallest(3, -2, -6);
  $task->smallest(5, 9, 7);
  $task->smallest(-2, -2, -1);
  $task->smallest(12, 3, 4);
}
main();

Output

 A : 3
 B : -2
 C : -6
 Minimum is : -6

 A : 5
 B : 9
 C : 7
 Minimum is : 5

 A : -2
 B : -2
 C : -1
 Minimum is : -2

 A : 12
 B : 3
 C : 4
 Minimum is : 3
/*
  Node Js Program for
  Smallest of three integers without comparison operators
*/
class Comparison
{
  // Return a minimum value of given two numbers
  minValue(a, b)
  {
    return b + (((a - b) >> (31)) & (a - b));
  }
  // Handles the request of finding minimum of given three numbers
  smallest(a, b, c)
  {
    // Display given value
    process.stdout.write(" A : " + a + "\n");
    process.stdout.write(" B : " + b + "\n");
    process.stdout.write(" C : " + c + "\n");
    var result = this.minValue(a, this.minValue(b, c));
    // Display calculated minimum
    process.stdout.write(" Minimum is : " + result + "\n\n");
  }
}

function main()
{
  var task = new Comparison();
  // Test cases
  task.smallest(3, -2, -6);
  task.smallest(5, 9, 7);
  task.smallest(-2, -2, -1);
  task.smallest(12, 3, 4);
}
main();

Output

 A : 3
 B : -2
 C : -6
 Minimum is : -6

 A : 5
 B : 9
 C : 7
 Minimum is : 5

 A : -2
 B : -2
 C : -1
 Minimum is : -2

 A : 12
 B : 3
 C : 4
 Minimum is : 3
import sys
#   Python 3 Program for
#   Smallest of three integers without comparison operators

class Comparison :
  #  Return a minimum value of given two numbers
  def minValue(self, a, b) :
    return b + (((a - b) >> (sys.getsizeof(int()) - 1)) & (a - b))
  
  #  Handles the request of finding minimum of given three numbers
  def smallest(self, a, b, c) :
    #  Display given value
    print(" A : ", a )
    print(" B : ", b )
    print(" C : ", c )
    result = self.minValue(a, self.minValue(b, c))
    #  Display calculated minimum
    print(" Minimum is : ", result ,"\n")
  

def main() :
  task = Comparison()
  #  Test cases
  task.smallest(3, -2, -6)
  task.smallest(5, 9, 7)
  task.smallest(-2, -2, -1)
  task.smallest(12, 3, 4)

if __name__ == "__main__": main()

Output

 A :  3
 B :  -2
 C :  -6
 Minimum is :  -6

 A :  5
 B :  9
 C :  7
 Minimum is :  5

 A :  -2
 B :  -2
 C :  -1
 Minimum is :  -2

 A :  12
 B :  3
 C :  4
 Minimum is :  3
#   Ruby Program for
#   Smallest of three integers without comparison operators

class Comparison 
  #  Return a minimum value of given two numbers
  def minValue(a, b) 
    return b + (((a - b) >> ( (1.size) * 8 - 1)) & (a - b))
  end

  #  Handles the request of finding minimum of given three numbers
  def smallest(a, b, c) 
    #  Display given value
    print(" A : ", a ,"\n")
    print(" B : ", b ,"\n")
    print(" C : ", c ,"\n")
    result = self.minValue(a, self.minValue(b, c))
    #  Display calculated minimum
    print(" Minimum is : ", result ,"\n\n")
  end

end

def main() 
  task = Comparison.new()
  #  Test cases
  task.smallest(3, -2, -6)
  task.smallest(5, 9, 7)
  task.smallest(-2, -2, -1)
  task.smallest(12, 3, 4)
end

main()

Output

 A : 3
 B : -2
 C : -6
 Minimum is : -6

 A : 5
 B : 9
 C : 7
 Minimum is : 5

 A : -2
 B : -2
 C : -1
 Minimum is : -2

 A : 12
 B : 3
 C : 4
 Minimum is : 3

/*
  Scala Program for
  Smallest of three integers without comparison operators
*/
class Comparison
{
  // Return a minimum value of given two numbers
  def minValue(a: Int, b: Int): Int = {
    return b + (((a - b) >> (Integer.SIZE - 1)) & (a - b));
  }
  // Handles the request of finding minimum of given three numbers
  def smallest(a: Int, b: Int, c: Int): Unit = {
    // Display given value
    print(" A : " + a + "\n");
    print(" B : " + b + "\n");
    print(" C : " + c + "\n");
    var result: Int = this.minValue(a, this.minValue(b, c));
    // Display calculated minimum
    print(" Minimum is : " + result + "\n\n");
  }
}
object Main
{
  def main(args: Array[String]): Unit = {
    var task: Comparison = new Comparison();
    // Test cases
    task.smallest(3, -2, -6);
    task.smallest(5, 9, 7);
    task.smallest(-2, -2, -1);
    task.smallest(12, 3, 4);
  }
}

Output

 A : 3
 B : -2
 C : -6
 Minimum is : -6

 A : 5
 B : 9
 C : 7
 Minimum is : 5

 A : -2
 B : -2
 C : -1
 Minimum is : -2

 A : 12
 B : 3
 C : 4
 Minimum is : 3
/*
  Swift 4 Program for
  Smallest of three integers without comparison operators
*/
class Comparison
{
  // Return a minimum value of given two numbers
  func minValue(_ a: Int, _ b: Int)->Int
  {
    return b + (((a - b) >> (4 * MemoryLayout.size(ofValue:1) - 1)) & (a - b));
  }
  // Handles the request of finding minimum of given three numbers
  func smallest(_ a: Int, _ b: Int, _ c: Int)
  {
    // Display given value
    print(" A : ", a );
    print(" B : ", b );
    print(" C : ", c );
    let result: Int = self.minValue(a, self.minValue(b, c));
    // Display calculated minimum
    print(" Minimum is : ", result ,"\n");
  }
}
func main()
{
  let task: Comparison = Comparison();
  // Test cases
  task.smallest(3, -2, -6);
  task.smallest(5, 9, 7);
  task.smallest(-2, -2, -1);
  task.smallest(12, 3, 4);
}
main();

Output

 A :  3
 B :  -2
 C :  -6
 Minimum is :  -6

 A :  5
 B :  9
 C :  7
 Minimum is :  5

 A :  -2
 B :  -2
 C :  -1
 Minimum is :  -2

 A :  12
 B :  3
 C :  4
 Minimum is :  3
/*
  Kotlin Program for
  Smallest of three integers without comparison operators
*/
class Comparison
{
  // Return a minimum value of given two numbers
  fun minValue(a: Int, b: Int): Int
  {
    return b + (((a - b) shr (Integer.SIZE - 1)) and (a - b));
  }
  // Handles the request of finding minimum of given three numbers
  fun smallest(a: Int, b: Int, c: Int): Unit
  {
    // Display given value
    print(" A : " + a + "\n");
    print(" B : " + b + "\n");
    print(" C : " + c + "\n");
    var result: Int = this.minValue(a, this.minValue(b, c));
    // Display calculated minimum
    print(" Minimum is : " + result + "\n\n");
  }
}
fun main(args: Array < String > ): Unit
{
  var task: Comparison = Comparison();
  // Test cases
  task.smallest(3, -2, -6);
  task.smallest(5, 9, 7);
  task.smallest(-2, -2, -1);
  task.smallest(12, 3, 4);
}

Output

 A : 3
 B : -2
 C : -6
 Minimum is : -6

 A : 5
 B : 9
 C : 7
 Minimum is : 5

 A : -2
 B : -2
 C : -1
 Minimum is : -2

 A : 12
 B : 3
 C : 4
 Minimum is : 3
package main
import "fmt"
import "unsafe"
/*
  Go Program for
  Smallest of three integers without comparison operators
*/
type Comparison struct {}
func getComparison() * Comparison {
  var me *Comparison = &Comparison {}
  return me
}
// Return a minimum value of given two numbers
func(this Comparison) minValue(a, b int) int {
  return b + (((a - b) >> (unsafe.Sizeof(1) - 1)) & (a - b))
}
// Handles the request of finding minimum of given three numbers
func(this Comparison) smallest(a, b, c int) {
  // Display given value
  fmt.Print(" A : ", a, "\n")
  fmt.Print(" B : ", b, "\n")
  fmt.Print(" C : ", c, "\n")
  var result int = this.minValue(a, this.minValue(b, c))
  // Display calculated minimum
  fmt.Println(" Minimum is : ", result)
}
func main() {
  var task * Comparison = getComparison()
  // Test cases
  task.smallest(3, -2, -6)
  task.smallest(5, 9, 7)
  task.smallest(-2, -2, -1)
  task.smallest(12, 3, 4)
}

Output

 A : 3
 B : -2
 C : -6
 Minimum is : -6
 A : 5
 B : 9
 C : 7
 Minimum is : 5
 A : -2
 B : -2
 C : -1
 Minimum is : -2
 A : 12
 B : 3
 C : 4
 Minimum is : 3

Time Complexity

The time complexity of this algorithm is O(1) for each test case, as it involves only a few arithmetic and bitwise operations, which execute in constant time.

Finally

In this article, we tackled the problem of finding the smallest of three integers without using comparison operators. We introduced an alternative approach based on bitwise manipulation and arithmetic operations. The algorithm proved to be efficient and easy to implement. By using this method, we can obtain the minimum value among three integers without relying on conventional comparison operators, providing a unique and practical solution to the problem.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment