Hello guys, you might have heard about this popular coding interview problem, How to find minimum of two number without using branching or conditional statement e.g. if-else block or library method e.g. Math.min(x, y) is a popular programming puzzle. If nothing is said about solving this problem, then it as simple as using relational operator "<" or ">" e.g.
if(a < b){
return a;
}
or
if( a> b){
return b;
}
or, by using ternary operator in Java
int smaller = a < b ? a: b
or, by using Math.min() method
int min = Math.min(a, b);
but, if that's the case, then it was probably not asked in programming interview. It is basically used to test your knowledge of bitwise operators e.g. left shift (<<), right shift(>>) and right shift without sign(>>>), but if you are creative enough and can solve this program by using arithmetic operator then perfect. Key thing to solve this problem is knowing the fact that integers are signed in Java, which means positive numbers has 0 at their MSB (most significant bit) and negative numbers has 1 at their MSB. It would be more clear by looking at binary representation of 2 and -2 in Java, which is as following
2 in binary is : 10
-2 in binary is : 11111111111111111111111111111110
Since, I have used Integer.toBinaryString(), it is not showing leading zero, by converting 10 to complete 32-bit value (size of int primitive is 32 bits in Java), it would be like 0000000000000000000000000000010. Now if you remember how right shift operator works (>>), you will know that by shifting an int value by 31 bits, a positive number will be equal to zero and a negative number will be -1, which is equal to their sign bit. You can test this by executing following Java code
int two = 2;
int minusTwo = -2;
int twoAfterShift = 2 >> 31;
int minusTwoAfterShift = -2 >> 31;
System.out.printf("Before right-shift %d, after 31 bit right shift: %d %n", two, twoAfterShift );
System.out.printf("Before right-shift %d, after 31 bit right shift: %d %n", minusTwo, minusTwoAfterShift );
Output:
Before right-shift 2, after 31 bit right shift: 0
Before right-shift -2, after 31 bit right shift: -1
Now by using this two properties, we can solve this problem? Did you get the idea?
In this tuotrial , we will write a Java program to find smaller of two integer numbers without any branching or using any library function.
Here is one possible solution to the original problem:
public int BitwiseMin(int a, int b)
{
a -= b;
a &= a >> (sizeof(int) * 8 - 1);
return a + b;
}
This solution works unless a − b is less than int.MinValue, in which
case it underfl ows. To prevent an underfl ow you can work with long
values as follows:
public int BitwiseMin(int a, int b)
{
long a_ = a; long b_ = b;
a_ -= b_;
a_ &= a_ >> (sizeof(long) *8 - 1);
return (int)(a_ + b_);
}
Another solution of this problem is by using XOR bitwise operator in Java
If we know that
INT_MIN <= (x - y) <= INT_MAX
, then we can use the following, which are faster because (x - y) only needs to be evaluated once.
Minimum of x and y will be
y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1)))
This method shifts the subtraction of x and y by 31 (if size of integer is 32). If (x-y) is smaller than 0, then (x -y)>>31 will be 1. If (x-y) is greater than or equal to 0, then (x -y)>>31 will be 0.
So if x >= y, we get minimum as y + (x-y)&0 which is y.
If x < y, we get minimum as y + (x-y)&1 which is x.
Similarly, to find the maximum use
x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))
Now Can you find larger of two numbers without using branching by following technique show here, after trying you can see the solution here.
The problem is similar to fi nding the minimum of two integers without
branching.
public int BitwiseMax(int a, int b)
{
long a_ = a; long b_ = b;
a_ -= b_;
a_ &= (~a_) >> (sizeof(long)*8-1);
return (int)(a_ + b_);
}
Java Program to find Smaller of Two Numbers without Branching
import java.util.Arrays;
import java.util.BitSet;
/**
*
*
* @author
*/
public class Testing {
public static void main(String args[]) {
System.out.printf("Minimum between 23 and 25 is %d %n", minimum(23, 25));
System.out.printf("Minimum between 233 and 215 is %d %n", minimum(233, 215));
System.out.printf("Minimum between 0 and 1 is %d %n", minimum(0, 1));
System.out.printf("Minimum between 0 and -1 is %d %n", minimum(0, -1));
System.out.printf("Minimum between -1 and 1 is %d %n", minimum(1, -1));
System.out.printf("Minimum between -23 and -25 is %d %n", minimum(-23, -25));
System.out.printf("Minimum between Integer.MAX and Integer.MIN is %d %n", minimum(Integer.MAX_VALUE, Integer.MIN_VALUE));
// Now calling method which accepts long
System.out.printf("Minimum between Integer.MAX and Integer.MIN is %d %n", smaller(Integer.MAX_VALUE, Integer.MIN_VALUE));
}
private static int minimum(int a, int b) {
a -= b;
a &= a >> (32 * 16 - 1);
return a + b;
}
private static long smaller(long a, long b) {
a -= b;
a &= a >> (32 * 16 - 1);
return a + b;
}
}
Output
Minimum between 23 and 25 is 23
Minimum between 233 and 215 is 215
Minimum between 0 and 1 is 0
Minimum between 0 and -1 is -1
Minimum between -1 and 1 is -1
Minimum between -23 and -25 is -25
Minimum between Integer.MAX and Integer.MIN is 2147483647
Minimum between Integer.MAX and Integer.MIN is -2147483648
That's all about how to find smaller of two numbers without branching in Java.
Further Learning
Thanks for reading this article so far. If you find this article useful then please share with your friends and colleagues.
if(a < b){
return a;
}
or
if( a> b){
return b;
}
or, by using ternary operator in Java
int smaller = a < b ? a: b
or, by using Math.min() method
int min = Math.min(a, b);
but, if that's the case, then it was probably not asked in programming interview. It is basically used to test your knowledge of bitwise operators e.g. left shift (<<), right shift(>>) and right shift without sign(>>>), but if you are creative enough and can solve this program by using arithmetic operator then perfect. Key thing to solve this problem is knowing the fact that integers are signed in Java, which means positive numbers has 0 at their MSB (most significant bit) and negative numbers has 1 at their MSB. It would be more clear by looking at binary representation of 2 and -2 in Java, which is as following
2 in binary is : 10
-2 in binary is : 11111111111111111111111111111110
Since, I have used Integer.toBinaryString(), it is not showing leading zero, by converting 10 to complete 32-bit value (size of int primitive is 32 bits in Java), it would be like 0000000000000000000000000000010. Now if you remember how right shift operator works (>>), you will know that by shifting an int value by 31 bits, a positive number will be equal to zero and a negative number will be -1, which is equal to their sign bit. You can test this by executing following Java code
int two = 2;
int minusTwo = -2;
int twoAfterShift = 2 >> 31;
int minusTwoAfterShift = -2 >> 31;
System.out.printf("Before right-shift %d, after 31 bit right shift: %d %n", two, twoAfterShift );
System.out.printf("Before right-shift %d, after 31 bit right shift: %d %n", minusTwo, minusTwoAfterShift );
Output:
Before right-shift 2, after 31 bit right shift: 0
Before right-shift -2, after 31 bit right shift: -1
Now by using this two properties, we can solve this problem? Did you get the idea?
In this tuotrial , we will write a Java program to find smaller of two integer numbers without any branching or using any library function.
Here is one possible solution to the original problem:
public int BitwiseMin(int a, int b)
{
a -= b;
a &= a >> (sizeof(int) * 8 - 1);
return a + b;
}
This solution works unless a − b is less than int.MinValue, in which
case it underfl ows. To prevent an underfl ow you can work with long
values as follows:
public int BitwiseMin(int a, int b)
{
long a_ = a; long b_ = b;
a_ -= b_;
a_ &= a_ >> (sizeof(long) *8 - 1);
return (int)(a_ + b_);
}
Another solution of this problem is by using XOR bitwise operator in Java
If we know that
INT_MIN <= (x - y) <= INT_MAX
, then we can use the following, which are faster because (x - y) only needs to be evaluated once.
Minimum of x and y will be
y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1)))
This method shifts the subtraction of x and y by 31 (if size of integer is 32). If (x-y) is smaller than 0, then (x -y)>>31 will be 1. If (x-y) is greater than or equal to 0, then (x -y)>>31 will be 0.
So if x >= y, we get minimum as y + (x-y)&0 which is y.
If x < y, we get minimum as y + (x-y)&1 which is x.
Similarly, to find the maximum use
x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))
Now Can you find larger of two numbers without using branching by following technique show here, after trying you can see the solution here.
The problem is similar to fi nding the minimum of two integers without
branching.
public int BitwiseMax(int a, int b)
{
long a_ = a; long b_ = b;
a_ -= b_;
a_ &= (~a_) >> (sizeof(long)*8-1);
return (int)(a_ + b_);
}
Java Program to find Smaller of Two Numbers without Branching
import java.util.Arrays;
import java.util.BitSet;
/**
*
*
* @author
*/
public class Testing {
public static void main(String args[]) {
System.out.printf("Minimum between 23 and 25 is %d %n", minimum(23, 25));
System.out.printf("Minimum between 233 and 215 is %d %n", minimum(233, 215));
System.out.printf("Minimum between 0 and 1 is %d %n", minimum(0, 1));
System.out.printf("Minimum between 0 and -1 is %d %n", minimum(0, -1));
System.out.printf("Minimum between -1 and 1 is %d %n", minimum(1, -1));
System.out.printf("Minimum between -23 and -25 is %d %n", minimum(-23, -25));
System.out.printf("Minimum between Integer.MAX and Integer.MIN is %d %n", minimum(Integer.MAX_VALUE, Integer.MIN_VALUE));
// Now calling method which accepts long
System.out.printf("Minimum between Integer.MAX and Integer.MIN is %d %n", smaller(Integer.MAX_VALUE, Integer.MIN_VALUE));
}
private static int minimum(int a, int b) {
a -= b;
a &= a >> (32 * 16 - 1);
return a + b;
}
private static long smaller(long a, long b) {
a -= b;
a &= a >> (32 * 16 - 1);
return a + b;
}
}
Output
Minimum between 23 and 25 is 23
Minimum between 233 and 215 is 215
Minimum between 0 and 1 is 0
Minimum between 0 and -1 is -1
Minimum between -1 and 1 is -1
Minimum between -23 and -25 is -25
Minimum between Integer.MAX and Integer.MIN is 2147483647
Minimum between Integer.MAX and Integer.MIN is -2147483648
That's all about how to find smaller of two numbers without branching in Java.
Further Learning
Thanks for reading this article so far. If you find this article useful then please share with your friends and colleagues.
Posts
