Find the position of the rightmost set bit

Given a number n, find the position of the rightmost set bit (the first bit set to 1 from the right side). The position is considered starting from 1 (i.e., the rightmost bit is at position 1, the second rightmost is at position 2, and so on).

Input/Output Examples

plaintext
Example 1:
Input:
n = 18
Output:
2
Explanation: The binary representation of 18 is 10010, and the rightmost set bit is at position 2.

Example 2:
Input:
n = 12
Output:
3
Explanation: The binary representation of 12 is 1100, and the rightmost set bit is at position 3.

Example 3:
Input:
n = 0
Output:
0
Explanation: There are no set bits in 0, so the output is 0.

Approach to Find the Position of Rightmost Set Bit

  1. Binary Representation:
    • The rightmost set bit is the first occurrence of 1 in the binary representation of the number when counted from the right side.
  2. Use a Bitwise Trick:
    • The expression n & -n isolates the rightmost set bit of n. This expression works because in two's complement representation, -n is the bitwise complement of n plus one.
    • To find the position, count how many bits you need to shift n & -n to the right until it becomes 1.
  3. Edge Case:
    • If n is 0, there are no set bits, so the position is 0.

C++ Program to Find the Position of Rightmost Set Bit

cpp
#include <iostream>
using namespace std;

// Function to find the position of rightmost set bit
int findRightmostSetBit(int n) {
    if (n == 0) return 0;

    // Isolate the rightmost set bit and calculate its position
    return (n & -n) ? __builtin_ffs(n) : 0;
}

int main() {
    int n = 18;
    cout << "Position of rightmost set bit: " << findRightmostSetBit(n) << endl;
    return 0;
}

Java Program to Find the Position of Rightmost Set Bit

java
public class RightmostSetBit {

    // Function to find the position of rightmost set bit
    public static int findRightmostSetBit(int n) {
        if (n == 0) return 0;

        // Isolate the rightmost set bit and find its position
        return (int) (Math.log(n & -n) / Math.log(2)) + 1;
    }

    public static void main(String[] args) {
        int n = 18;
        System.out.println("Position of rightmost set bit: " + findRightmostSetBit(n));
    }
}

Python Program to Find the Position of Rightmost Set Bit

python
# Function to find the position of rightmost set bit
def find_rightmost_set_bit(n):
    if n == 0:
        return 0

    # Isolate the rightmost set bit and calculate its position
    return (n & -n).bit_length()

# Example usage
if __name__ == "__main__":
    n = 18
    print("Position of rightmost set bit:", find_rightmost_set_bit(n))
  • Time Complexity: O(1) because bitwise operations like n & -n and finding the position of the set bit (using bit_length or similar) take constant time.
  • Space Complexity: O(1) since only a few variables are used, independent of the input size.

DSA

1552

359

Related Articles