Find the Position of the Rightmost Set Bit

Problem Statement

Given a positive integer n, find the position of the rightmost set bit in its binary representation. The rightmost set bit is the first 1 bit in the binary representation of the number when traversed from right to left (starting from position 1). Return the position of this bit.

If the number is 0 (which has no set bits), return -1 to indicate that there are no set bits.

Examples

Example 1:

Input: n = 18
Output: 2

Explanation: The binary representation of 18 is 10010. The rightmost set bit is at position 2 (counting starts from 1).

Example 2:

Input: n = 0
Output: -1

Explanation: The binary representation of 0 is 0. It has no set bits, so the output is -1.

Example 3:

Input: n = 7
Output: 1

Explanation: The binary representation of 7 is 111. The rightmost set bits is at position 1.

Different Approaches

1️⃣ Iterative Approach

The problem requires identifying the position of the rightmost set bit (1) in the binary representation of a number. In binary, the rightmost set bit is unique because it represents the lowest power of 2 present in the number. If we isolate this bit, we can determine its position directly.

Approach:

1. Convert the number to its binary representation.
2. Check each bit starting from the least significant bit (LSB).
3. Return the position of the first set bit encountered.

Code:

#include <iostream>
using namespace std;

int findRightmostSetBitPosition(int n) {
    if (n == 0) return -1; // No set bit in 0
    
    int position = 1; // Start position from 1
    while ((n & 1) == 0) { // Check if the LSB is 0
        n >>= 1;           // Right shift the number
        position++;
    }
    return position;
}

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

Complexity Analysis:

• Time Complexity: O(log n)
  • We iterate over the bits of n, right-shifting at each step.
• Space Complexity: O(1)

2️⃣ Bit Manipulation

Intuition:

Every number in binary has a mix of 1s and 0s. The rightmost set bit is the lowest bit position (from right, 1-indexed) where 1 appears.

To isolate the rightmost set bit, there's a beautiful bitwise trick:

n & -n

This expression isolates the lowest set bit in binary form — i.e., it gives a number with only the rightmost 1-bit set.

Bit manipulation provides an elegant and efficient solution to finding the rightmost set bit. The key lies in realizing that subtracting 1 from a binary number with a rightmost set bit changes that rightmost 1 to 0 and all the 0's to the right of it to 1. This operation allows us to isolate the rightmost set bit.

number n, 18 = Binary 0000 0000 0001 0010

Complement of n = -n = 18 = Binary 1111 1111 1110 1110

Doing bitwise AND to n & -n = 0000 0000 0000 0010

Approach:

1. Check if n == 0 → return -1 (no set bits).
2. Use n & -n to isolate the rightmost set bit.
3. Take log2 of the result and add 1 to get 1-based position.

Code:

#include <iostream>

int findRightmostSetBitPosition(int n) {
    // If n is 0, there is no set bit
    if (n == 0) {
        return -1; // indicating no set bit found
    }

    // Calculate the two's complement and perform bitwise AND
    int rightmostSetBitPosition = n & -n;

    // Find the position of the rightmost set bit
    return __builtin_ctz(rightmostSetBitPosition) + 1; // Adjusting to 1-based index
}

int main() {
    int n = 18;
    int position = findRightmostSetBitPosition(n);

    if (position != -1) {
        std::cout << "The position of the rightmost set bit in " << n << " is: " << position << std::endl;
    } else {
        std::cout << "No set bit found in " << n << std::endl;
    }

    return 0;
}

Explanation:

1. Function findRightmostSetBitPosition:
   • Checks if n is zero. If it is, there is no set bit, and the function returns -1.
   • Calculates the two's complement of n and performs a bitwise AND operation with n. This operation isolates set bit in n and stores the result in the variable rightmostSetBitPosition.
2. Returning the Position:
   • The __builtin_ctz function is used to count the trailing zeroes in the binary representation of rightmostSetBitPosition. This count corresponds to the position of the rightmost set bit.
   • The position is adjusted to 1-based index and returned.

Complexity Analysis:

• Time Complexity: O(1)
  • Bitwise ops and log2 are constant time.
• Space Complexity:O(1)
  • No extra space used.