C Program to Find Position of Rightmost Set Bit

In C, you can find the position of the rightmost set bit using pos = (x & -x) to isolate it and then count its position with a loop or bit operations; for example, use int pos = 1; while (!(x & 1)) { x >>= 1; pos++; }.

Examples

Input18

Output2

Input12

Output3

Input0

Output0

How to Think About It

To find the rightmost set bit position, think of the binary form of the number. The rightmost set bit is the first '1' from the right side. We can check each bit from right to left by shifting the number right until we find a '1'. The count of shifts plus one gives the position.

Algorithm

1

Get the input number.

2

If the number is zero, return 0 because no bits are set.

3

Initialize position counter to 1.

4

Check if the rightmost bit is set (1). If yes, return position.

5

If not, right shift the number by 1 and increment position.

6

Repeat until a set bit is found.

Code

c

#include <stdio.h>

int rightmostSetBitPos(int x) {
    if (x == 0) return 0;
    int pos = 1;
    while ((x & 1) == 0) {
        x >>= 1;
        pos++;
    }
    return pos;
}

int main() {
    int num = 18;
    printf("Position of rightmost set bit in %d is %d\n", num, rightmostSetBitPos(num));
    return 0;
}

Output

Position of rightmost set bit in 18 is 2

Dry Run

Let's trace input 18 through the code to find the rightmost set bit position.

1

Initial value

x = 18 (binary 10010), pos = 1

2

Check rightmost bit

x & 1 = 0 (bit is not set), shift x right by 1

3

After shift

x = 9 (binary 1001), pos = 2

4

Check rightmost bit again

x & 1 = 1 (bit is set), return pos = 2

x (decimal)	x (binary)	x & 1	pos
18	10010	0	1
9	1001	1	2

Why This Works

Step 1: Check if number is zero

If the number is zero, it has no set bits, so return 0 immediately.

Step 2: Use bitwise AND to check rightmost bit

The expression x & 1 checks if the rightmost bit is set (1) or not (0).

Step 3: Shift right until set bit found

If the rightmost bit is not set, shift the number right by one bit and increase position count until a set bit is found.

Alternative Approaches

Using x & (-x) and log2

c

#include <stdio.h>
#include <math.h>

int rightmostSetBitPos(int x) {
    if (x == 0) return 0;
    int isolated = x & (-x);
    int pos = (int)(log2(isolated)) + 1;
    return pos;
}

int main() {
    int num = 18;
    printf("Position of rightmost set bit in %d is %d\n", num, rightmostSetBitPos(num));
    return 0;
}

This method uses math functions and isolates the rightmost set bit directly, but requires <math.h> and floating-point operations.

Using built-in GCC function __builtin_ffs

c

#include <stdio.h>

int main() {
    int num = 18;
    int pos = __builtin_ffs(num); // returns 1-based position or 0 if none
    printf("Position of rightmost set bit in %d is %d\n", num, pos);
    return 0;
}

This is the simplest and fastest method but is GCC-specific and not portable to all compilers.

Complexity: O(log n) time, O(1) space

Time Complexity

The loop runs at most the number of bits in the integer (usually 32 or 64), so it is O(log n) where n is the input number.

Space Complexity

The program uses a fixed number of variables and no extra memory proportional to input size, so O(1).

Which Approach is Fastest?

Using the built-in function __builtin_ffs is fastest and simplest but not portable; the bitwise loop is portable and clear; the log2 method is elegant but uses floating-point math.

Approach	Time	Space	Best For
Bitwise loop	O(log n)	O(1)	Portability and clarity
x & (-x) with log2	O(1) with math call	O(1)	Mathematical elegance, less portable
__builtin_ffs	O(1)	O(1)	Fastest, GCC-specific