Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

bitwise

Find the position of rightmost different bit of two numbers

Ravi

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:

  1. Find the bitwise XOR of x and y. Here, the different bits of x and y become set in x ^ y. If the numbers are identical, then the XOR will be zero, and there will be no different bit.
  2. 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 1
        int andOp = num & (num - 1);
        // Step 2
        int xorOp = num ^ andOp;
        // Step 3
        return 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 x and y.
  • 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.

RELATED TAGS

bitwise
RELATED COURSES

View all Courses

Keep Exploring