Table of contents

Introduction-

Position of Rightmost Set Bit

2.1.

Approach1

2.2.

Implementation-

2.3.

Output:

2.4.

Time and Space Complexity-

2.5.

Approach2

2.6.

Output:

Position of Leftmost Set Bit

3.1.

Approach

3.2.

Implementation-

3.3.

Output:

Frequently Asked Questions-

Key Takeaways-

Last Updated: Mar 27, 2024

Find the leftmost and rightmost set bit of a number

Author Raksha jain

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction-

Today, let’s learn about a famous and commonly asked Interview Problem, i.e,. Find the leftmost and rightmost set bit of a number.

Problem Statement: Find the position of the first set bit (i.e. 1) from

right to left and
Left to right

in binary representation of an Integer.

Example:

Input : Number = 17

Output:

Leftmost set bit : 5th position

Rightmost set bit: 1st position

(as the Binary representation of 17 is: 010001)

Let's get started and learn the approach to solve this problem.

Position of Rightmost Set Bit

Approach1

Take two’s complement of the given number as all bits are reverted except the first ‘1’ from right to left.
Note: 2’s complement is negation (~) of the given number + 1 (i.e. ~ N + 1)

(Example: Given No : 12 [1100] => Its 2’s complement would be 4 [0100])

Do a Bitwise and(&) with original number => returns the required one only [0100]
Take log2 of the number got in Step2 and you’ll get (position - 1).
Add 1 to get the desired position (i.e. position of the rightmost set bit).

(=> 3 gets returned in this case)

So, (N & ~ ( N - 1 )) always returns the binary number containing the rightmost set bit as 1.

Implementation-

Let’s have a look at its implementation in Java -

import java.util.*;
public class Main {
  
    // Find rightmost set bit position
    public static int rightmostSetBit(int n){
        return (int)((Math.log10(n & - n)) / Math.log10(2)) + 1;
    }
 
    // Main function
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        System.out.println("Enter the number");
        int n = s.nextInt();
        System.out.println("RightMost set bit position: " + rightmostSetBit(n));
    }
}

You can also try this code with Online Java Compiler

Run Code

Output:

Enter the number 12
RightMost set bit position: 3

Time and Space Complexity-

Time Complexity: O(log2(N)) where “N” is the given number for calculating log2(N & ~ N) + 1.

Space Complexity: O(1) as no extra space has been used.

Approach2

Using Xor and & operator

Initialize m (mask bit) as 1 and check its XOR with the bits starting from the rightmost bit. Leftshift m by 1 till we find the first set bit. The first set bit gives the number = answer of a & operation with m.

Implementation-

Let’s have a look at its implementation in Java -

import java.util.*;

// Finding rightmost set bit using XOR operator
public class Main {

// Find rightmost set bit position
public static int rightmostSetBit(int n){
// Position variable initialized with 1 
int position = 1;

// m variable is used to check the set bit
int m = 1;

while ((n & m) == 0) {

// Perform left shift
m = m << 1;
position++;
}
return position;
}

// Main Code
public static void main(String[] args){
Scanner s = new Scanner(System.in);
      System.out.println("Enter the number");
      int n = s.nextInt();
      System.out.println("RightMost set bit position: " + rightmostSetBit(n));
}
}

You can also try this code with Online Java Compiler

Run Code

Output:

Enter the number 12
RightMost set bit position: 3

Position of Leftmost Set Bit

Approach

For finding the position of the leftmost set bit, we simply right shift the given number “N” till that number is > 0. Alongside, we increment the position variable to find the position of the leftmost set bit.

Implementation-

Let’s have a look at its implementation in Java -

import java.util.*;
public class Main {

    public static int leftmostSetBit(int n){
    
        // Initializing the position bit to 1
        int pos = 0;
        while (n > 0) {
            n = n >> 1;
            pos++;
        }
        return pos;
    }


// Main Code
public static void main(String[] args){
    Scanner s = new Scanner(System.in);
        System.out.println("Enter the number");
        int n = s.nextInt();
        System.out.println("Leftmost set bit position:" + leftmostSetBit(n));
}
}

You can also try this code with Online Java Compiler

Run Code

Output:

Enter the number 12
RightMost set bit position: 4

Check out this problem - First And Last Occurrences Of X

Frequently Asked Questions-

What is a set bit?
The binary representation of a number consists of 0 and 1. Here, 1 is known as set bit.
What is the left shift operator?
The left shift operator is a logical bitwise operator that operates on two positive integral operands and shifts the bits to the left by the number of positions specified by its second operand.
What is the right shift operator?
The right shift operator is a logical bitwise operator that operates on two positive integral operands and shifts the bits to the right by the number of positions specified by its second operand.
What is a mask bit?
A mask defines which bits you want to keep, and which bits you want to clear. So, masking is the act of applying a mask to a value.

Also Read - Strong number in c

Key Takeaways-

In this blog, we learned various approaches to find the leftmost and rightmost set bit of a number Problem.

Finding the leftmost and rightmost set bit of a number Problem is a standard easy problem.
RIghtmost set bit can be easily found using 2’s complement i.e. via (N & ~ (N - 1)) or using the XOR operator where “N” is the given number.
Leftmost set bit can be easily found by simply right shifting the given number “N” till that number is > 0. Alongside, we increment the position variable to find the position of the leftmost set bit.

Check out more blogs on different dp problems like LCS, Friends Pairing Problem to read more about these topics in detail. And if you liked this blog, share it with your friends!

Practice a variety of on Coding Ninjas Studio platform where you can find questions asked in all big-tech giants.