Find Leftmost and Rightmost Set Bit of a Number

Introduction

Let's discuss a well-known and frequently requested interview question today, namely, “Determine the number's leftmost and rightmost set bits.”

Rightmost Set Bit Position

Approach:

Take a number, with the exception of the initial '1' from right to left, which has all bits reversed.

Note: The negation (~ ) of the given number plus 1 (i.e., N + 1) is the complement of two.

(For instance, given No. 12 [1100], its complement of 2 would be 4 [0100])

Bitwise and (&) with the original number yields the desired result only. [0100]

The number you obtained in Step 2 multiplied by log2 gives you (position - 1).

To obtain the desired position, add 1. (i.e. position of the rightmost set bit).

(= In this instance, 3 is returned)

As a result, (N & (N - 1)) always outputs a binary number with the rightmost set bit set to 1.

Implementation: Let's look at how it is done 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));
    }
}

Output

Enter the number 12
RightMost set bit position: 3

Place of the Leftmost Set Bit

Approach:

By simply right shifting the given number "N" until it is greater than 0, we may determine the location of the leftmost set bit. To discover the location of the leftmost set bit, we also increase the position variable.

Implementation: Let's look at how it is done 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));
}
}

Output

Enter the number
5
Leftmost set bit position:3

Bit Manipulation

Bit manipulation refers to the manipulation of individual bits in a binary representation of data. This is often used in programming for various purposes, such as improving performance, reducing memory usage, or implementing certain algorithms.

Some common operations used in bit manipulation include bitwise AND (&), bitwise OR (|), bitwise XOR (^), left shift (<<), right shift (>>), and complement (~).

Bit manipulation can be used to perform various tasks, such as checking if a bit is set or not, setting or clearing a bit, counting the number of set bits in a number (also known as the Hamming weight), finding the position of the leftmost or rightmost set bit, and more.

For example, to check if the i-th bit of a number num is set or not, you can use the following code:

if num & (1 << i):
    # i-th bit is set
else:
    # i-th bit is not set

In this code, (1 << i) creates a mask with a 1 in the i-th bit position, and the & operator performs a bitwise AND between num and the mask. If the result is non-zero, then the i-th bit is set.

Overall, bit manipulation is a powerful tool in programming that can be used to perform various tasks efficiently and elegantly.

Complexities

1. Time Complexity: O(log2(N)), where “N” is the number that will be used to calculate log2(N &  N) + 1.
2. Space Complexity: O(1) because no additional space was used.

Rightmost set bit's position using the operator

Follow below steps:

1. Check m XOR with the bits starting with the rightmost bit by setting its initial value to 1.
2. Left shift m one by one until we find the first set bit,
3. As the first set bit gives a number when we perform the a & operation on m.

Implementation of Code in C++

// C++ program to find the first
// rightmost set bit using XOR operator
#include <bits/stdc++.h>
using namespace std;
// function to find the rightmost set bit
int PositionRightmostSetbit(int n)
{
    if (n == 0)
        return 0;
    // Position variable initialize with 1
    // m variable is used to check the set bit
    int position = 1;
    int m = 1;
 
    while (!(n & m)) {
        // left shift
        m = m << 1;
        position++;
    }
    return position;
}
// Driver Code
int main()
{
    int n = 18;
    // function call
    cout << PositionRightmostSetbit(n);
    return 0;
}

Output

 2

Complexity of time: O(log2N), traversing all of N's bits, with a maximum of logN bits.

Space for Services: O(1)

Conclusion

In conclusion, the concept of bit manipulation is an important tool in computer science that allows programmers to perform various operations on individual bits in binary representations of data. It is used to improve program performance, reduce memory usage, or implement certain algorithms.

Finding the leftmost and rightmost set bit of a number can be done using bit manipulation operations. The leftmost set bit can be found by taking the logarithm base 2 of the number to get its binary length, subtracting 1 from the length to get the position of the leftmost set bit, and using a mask with a 1 in the leftmost bit position to isolate the leftmost set bit. The rightmost set bit can be found by using a bitwise AND operator with the number and its two's complement to isolate the rightmost set bit, and taking the logarithm base 2 of the isolated bit to get its position.

Both of these operations have a time complexity of O(log n) and do not require any extra space. Bit manipulation is a powerful tool that can be used to perform various tasks efficiently and elegantly.