Find the position of rightmost different bit of two numbers
Problem statement
Given two numbers, x and y, find the position of the rightmost different bit of the two numbers.
Example 1:
- Input:
x=11,y=9 - Output: 2
11 - 1011
9 - 1001
The second rightmost bit is different, hence, the answer is 2.
Solution
We’ll use bitwise XOR and find the position of the rightmost set bit.
The steps involved in the solution are as follows:
- Find the bitwise XOR of
xandy. Here, the different bits ofxandybecome set in x ^ y. If the numbers are identical, then the XOR will be zero, and there will be no different bit. - Find the position of the rightmost set bit of the result of step 1. Refer to How to find the position of the rightmost set bit of an integer? for the implementation.
Example of the algorithm:
- 11 - 1011
- 9 - 1001
- 11 ^ 9 - 0110
The position of the rightmost set of bits is 2.
Code example
Let’s look at the code below:
public class Main {static int findOnlySetBitPos(int n){return (int)((Math.log10(n)) / Math.log10(2)) + 1;}static int positionOfRightmostSetBit(int num){if((num & 1) != 0) return 1;// Step 1int andOp = num & (num - 1);// Step 2int xorOp = num ^ andOp;// Step 3return findOnlySetBitPos(xorOp);}public static void main(String[] args) {int x = 11;int y = 9;int xorOp = x ^ y;if(xorOp == 0)System.out.println("The numbers are same");else{int pos = positionOfRightmostSetBit(xorOp);System.out.println("The position of the rightmost different bit of " + x + " and " + y + " is " + pos);}}}
Code explanation
- Lines 3-4:
findOnlySetBitPos()is defined that returns the position of the only set bit. - Lines 7-16:
positionOfRightmostSetBit()method is defined that implements the solution above to return the position of the rightmost set bit. - Line 19: We define
x. - Line 20: We define
y. - Line 21: We compute Bitwise XOR of
xandy. - Lines 22 to 23: If the Bitwise XOR is zero, then the numbers are the same.
- Lines 24 to 27: If the Bitwise XOR is not zero, then we find the position of the rightmost set bit of the bitwise xor.
TRENDING TOPICS
