Skip to main content

Bit Manipulation

Set the Rightmost Unset Bit Solution In C++/Java/Python/JS

Problem Description

Given a non-negative number n. The problem is to set the rightmost unset bit in the binary representation of n.

What is Set/Unset Bit?

What is a Bit?
In binary, every number is made of bits — and each bit can either be 0 or 1. These are the smallest units of data in computers.

For example:
The number 5 in binary is 101 (which means 1×2² + 0×2¹ + 1×2⁰ = 4 + 0 + 1 = 5).
So, the bits from right to left are:

  • 0th bit = 1
  • 1st bit = 0
  • 2nd bit = 1

What is a Set Bit?
A bit is called set if its value is 1.
So in our number 5 (binary 101), the 0th and 2nd bits are set.

What is an Unset Bit?
A bit is called unset (or clear) if its value is 0.
In 5 (101), the 1st bit is unset.

Example

Input: n = 6
Output: 7
Explanation: The binary representation of 6 is 110. After setting right most bit it becomes 111 which is 7.

Input: n = 15
Output: 31
Explanation: The binary representation of 15 is 01111. After setting right most bit it becomes 11111 which is 31.

Constraints

  • 1 <= n <= 10^9
💡
Try it Yourself First
We’ve all seen numbers as digits in base-10, but deep inside the computer, they live as binary bits — just 0s and 1s. Sometimes, a small change like flipping a single 0 to 1 can unlock a new number — today, let’s uncover how to find and set the rightmost 0 in a number’s binary form, step by step

Better Approach

Intuition

We are given a number n, and we’re told to set the rightmost unset bit in its binary form. That means: we need to find the first 0 when looking from the rightmost side (the least significant bit), and we need to flip it to 1, keeping the rest of the bits unchanged. Now, let’s think about how we were taught binary in school: every bit in a number represents a power of two. For example, if n = 6, then its binary is 110 (which means 4 + 2 = 6). Here, the bit positions from right to left are: 0th = 0, 1st = 1, 2nd = 1. So, the 0th bit is the first unset bit, and setting it means making it 1, turning the binary into 111, which is 7. That’s the output.

Now, we may wonder: “How do we know where the first unset bit is?” or “Can we just convert the number to binary and manually check?” While that would work, it's not efficient. Instead, using bitwise operators gives us a faster, cleaner way. We use a small number with only one bit set (called a mask) and check if that bit in n is 0 or 1 using AND.

What is Mask?

A mask is simply a number that helps us focus on specific bits within another number. Think of it like using a stencil when painting — the stencil (mask) allows us to paint only in specific areas and ignore the rest. Similarly, in programming, a bitmask helps us isolate, set, or clear particular bits in a number.

But the mask has to be smartly constructed — it should have a 1 only at the position we care about and 0 everywhere else.

For example, if we want to work with the 3rd bit (from the right), we make a mask like this:
00000100 (which is 4 in decimal) — this has 1 only at the 3rd position and zeroes elsewhere.
This kind of mask helps us target the 3rd bit only, without disturbing others.

What is the Left Shift (<<) Operator?

The Left Shift (<<) operator is how we create such masks or shift bits to the left.

Here’s what happens when we do something like:
1 << 3

Let’s understand this step-by-step:

  • Start with the number 1 → in binary: 00000001
  • Shift it 3 positions to the left → becomes 00001000
  • This is now 8 in decimal.

So, doing 1 << i creates a number where only the i-th bit is 1 and the rest are 0s.
That’s exactly what we want in a mask when we want to work with the i-th bit.

Why use AND Operator?

We create a mask where only the i-th bit is 1, and the rest are 0, using 1 << i.
Then we use bitwise AND (&) with the original number.

If the result is non-zero, it means the bit was 1.
If the result is zero, it means the bit was 0.

Example:
Let’s say our number is 13, and we want to check the 2nd bit (i = 2).

  • Binary of 13: 1101
  • Mask: 1 << 2 = 0100 (which is 4)
  • Now do: 1101 & 0100 = 0100 (which is 4, non-zero)

So, the 2nd bit is set (it's 1).

We try this for every bit starting from the right (bit 0, 1, 2, etc.) until we find a 0. Once we find it, we use OR to turn it into 1 — and OR works beautifully for this because 1 | 0 = 1, and 1 | 1 = 1, so it keeps the bit 1 and doesn’t disturb other bits.

This way, we efficiently and correctly set the rightmost unset bit. A few more doubts might come up: "What if all bits are already 1?" In that case, the loop runs through all 32 bits and doesn’t find any unset bit — so n remains unchanged. Or "Why do we only go up to 32 bits?" Because integers are usually stored in 32 bits, so we don’t need to check beyond that. In short, we scan from right to left, find the first 0, flip it to 1 using OR, and return the result.

Approach

Step 1: Loop through all 32 bit positions
To find the rightmost unset bit, we start checking from the least significant bit (bit position 0) up to the most significant bit (bit position 31).
We use a loop to ensures we don't miss any possible unset bit in the 32-bit representation of the number.

Step 2: Create a bit mask with 1 at position i
To focus on a specific bit position, we create a bitmask with a 1 at that position using left shift:
mask = 1 << i
This creates numbers like 1, 2, 4, 8, 16… which represent binary values like 0001, 0010, 0100, 1000, etc.
Each mask targets exactly one bit in the number.

Step 3: Check if the ith bit is unset (0)
To check if a bit is unset, we use the bitwise AND operation:
n & mask
If the result is 0, it means the bit at position i is not set.
This tells us that this is the rightmost unset bit we are looking for.

Step 4: Set the bit using bitwise OR
Once we find the first unset bit, we use bitwise OR to set it:
n = n | mask
This ensures the bit at position i is now 1.
Other bits remain unchanged because OR with 0 has no effect.

Step 5: Break after setting the first unset bit
Since we are only interested in setting the rightmost unset bit, we break the loop immediately after setting it.
This prevents changing any other unset bits.

Step 6: Return the updated number
After setting the bit, we return the modified number n. This number now has its rightmost 0 bit changed to 1.

Dry Run

Let's do a detailed Dry Run for the given code and input to understand how the function performs bit manipulation:

Input: n = 15

Step 1: Convert number to binary
Let’s convert 15 to its binary form:
15 = 00000000000000000000000000001111
(We are using 32-bit representation for consistency)

Bit positions (0-based from right to left):

Position: 4 3 2 1 0
Binary: 0 1 1 1 1

We can see that all the rightmost bits are 1. The first unset bit (0) appears at position 4.

Step 2: Start looping through all bit positions from 0 to 31
We begin a loop from i = 0 to 31 to find the first bit that is unset.

Iteration i = 0

mask = 1 << 0 = 1
Binary mask = 00000000000000000000000000000001
n & mask = 15 & 1 = 1 → The 0th bit is set, continue loop.

Iteration i = 1

mask = 1 << 1 = 2
Binary mask = 00000000000000000000000000000010
n & mask = 15 & 2 = 2 → The 1st bit is set, continue loop.

Iteration i = 2

mask = 1 << 2 = 4
Binary mask = 00000000000000000000000000000100
n & mask = 15 & 4 = 4 → The 2nd bit is set, continue loop.

Iteration i = 3

mask = 1 << 3 = 8
Binary mask = 00000000000000000000000000001000
n & mask = 15 & 8 = 8 → The 3rd bit is set, continue loop.

Iteration i = 4

mask = 1 << 4 = 16
Binary mask = 00000000000000000000000000010000
n & mask = 15 & 16 = 0 → The 4th bit is unset

Step 3: Set the 4th bit using OR operation
We perform:
n = n | mask = 15 | 16 = 31

Binary:
15 = 00000000000000000000000000001111
mask= 00000000000000000000000000010000
Result = 00000000000000000000000000011111 = 31

So, after setting the rightmost unset bit, n becomes 31.

Step 4: Return the updated number
We return the final value of n = 31

Final Output: 31

Code for All Languages
C++ 
#include <iostream>      // for cin and cout
using namespace std;

class Solution {
public:

    // Function to set the rightmost unset bit in the binary representation of n
    int setBit(int n) {
    
        // Step 1: Loop through all bit positions from 0 to 31
        for (int i = 0; i < 32; i++) {
        
            // Step 2: Create a mask with 1 at position i
            int mask = 1 << i;

            // Step 3: Check if the ith bit is unset (0)
            if ((n & mask) == 0) {
            
                // If unset, set the bit using OR operation
                n = n | mask;

                // Break after setting the first unset bit from right
                break;
            }
        }

        // Step 4: Return the updated number after setting the rightmost unset bit
        return n;
    }
};

// Driver code
int main() {
    int n;

    // Input the number
    cin >> n;

    Solution sol;

    // Call the function to set the rightmost unset bit
    int updatedNumber = sol.setBit(n);

    // Output the result
    cout << updatedNumber;

    return 0;
}

Java 
import java.util.Scanner;    // for Scanner class

class Solution {

    // Function to set the rightmost unset bit in the binary representation of n
    static int setBit(int n) {
    
        // Step 1: Loop through all bit positions from 0 to 31
        for (int i = 0; i < 32; i++) {

            // Step 2: Create a mask with 1 at position i
            int mask = 1 << i;

            // Step 3: Check if the ith bit is unset (0)
            if ((n & mask) == 0) {

                // If unset, set the bit using OR operation
                n = n | mask;

                // Break after setting the first unset bit from right
                break;
            }
        }

        // Step 4: Return the updated number after setting the rightmost unset bit
        return n;
    }
}

// Driver code
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n;

        // Input the number
        n = sc.nextInt();

        Solution sol = new Solution();

        // Call the function to set the rightmost unset bit
        int updatedNumber = sol.setBit(n);

        // Output the result
        System.out.print(updatedNumber);

        sc.close();
    }
}

Python 
# Function to set the rightmost unset bit in the binary representation of n
class Solution:
    def setBit(self, n):
    
        # Step 1: Loop through all bit positions from 0 to 31
        for i in range(32):

            # Step 2: Create a mask with 1 at position i
            mask = 1 << i

            # Step 3: Check if the ith bit is unset (0)
            if (n & mask) == 0:

                # If unset, set the bit using OR operation
                n = n | mask

                # Break after setting the first unset bit from right
                break

        # Step 4: Return the updated number after setting the rightmost unset bit
        return n

# Driver code
if __name__ == "__main__":
    # Input the number
    n = int(input())

    sol = Solution()

    # Call the function to set the rightmost unset bit
    updatedNumber = sol.setBit(n)

    # Output the result
    print(updatedNumber)

Javascript 
class Solution {
  
    // Function to set the rightmost unset bit in the binary representation of n
    setBit(n) {
      
        // Step 1: Loop through all bit positions from 0 to 31
        for (let i = 0; i < 32; i++) {

            // Step 2: Create a mask with 1 at position i
            const mask = 1 << i;

            // Step 3: Check if the ith bit is unset (0)
            if ((n & mask) === 0) {

                // If unset, set the bit using OR operation
                n = n | mask;

                // Break after setting the first unset bit from right
                break;
            }
        }

        // Step 4: Return the updated number after setting the rightmost unset bit
        return n;
    }
}

// Driver code
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.question('', function(line) {
    const n = parseInt(line.trim());

    const sol = new Solution();

    // Call the function to set the rightmost unset bit
    const updatedNumber = sol.setBit(n);

    // Output the result
    console.log(updatedNumber);

    rl.close();
});

Time Complexity: O(1)

Loop Operation: O(1)
The loop iterates from 0 to 31, which means it runs at most 32 times. Since 32 is a constant and does not depend on the input value n, the loop runs in constant time.

Bit Mask Creation: O(1)
Each iteration creates a mask using a left shift operation:
mask = 1 << i
This shift operation takes constant time regardless of the value of i.

Bitwise AND Operation: O(1)
The check (n & mask) == 0 uses bitwise AND, which is a constant-time operation.

Bitwise OR Operation: O(1)
Setting the bit using n = n | mask is also a constant-time operation.

Final Time Complexity: O(1)
All operations inside the loop are constant time, and the loop itself runs a fixed number of times (32). Therefore, the overall time complexity is constant time, O(1).

Space Complexity: O(1)

Auxiliary Space Complexity: O(1)
This refers to the extra space used internally during the computation, excluding input and output. In this program:

  • Only a few fixed-size integer variables are used, such as i, mask, and n (which is updated in-place).
  • There are no arrays, dynamic memory allocations, or recursive calls.
  • Hence, the auxiliary space required is constant, i.e., O(1).

Total Space Complexity: O(1)
This includes both auxiliary space and space for input/output handling. In this program:

  • The input variable n is a fixed-size integer.
  • The program uses a constant number of fixed-size variables overall.
  • Therefore, the total space complexity is constant, i.e., O(1).
When we manually try to find and set the rightmost 0 bit, it feels like searching in the dark — checking each bit one by one like brute force. But what if there’s a shortcut that lets us directly flip just that bit using a smart trick with addition and OR? Let’s uncover that elegant idea.

Optimal Approach

Intuition

Now that we’ve understood the manual way to find and set the rightmost unset bit, let’s see if there’s a quicker and smarter trick — something that doesn’t need loops or repeated checks. Here’s where bit manipulation magic comes in.

Imagine we are given a number n, and we want to set the rightmost unset (0) bit in its binary representation — meaning, we want to turn the first 0 we see from the right side into a 1, while keeping all other bits the same. But how do we find where that 0 is without scanning every bit one by one? That’s where the idea of adding 1 to the number comes into play. Think back to how we learned decimal addition in school — when we add 1 to a number like 239, the units place increases by 1, but if it’s a 9, it carries over. Something similar happens in binary. For example, if n = 1011 (binary for 11), adding 1 gives us 1100 (binary for 12). Notice what happened: the rightmost 0 turned into 1, and all bits to the right became 0. This is always true — adding 1 flips the rightmost 0 to 1, and resets all 1s after it to 0.

Now comes the real trick — how do we combine this new number with the original one to preserve everything else and only turn that rightmost 0 into 1? This is where the bitwise OR operation comes in. Bitwise OR works by comparing corresponding bits: if either of the bits is 1, the result is 1. So, if we do n | (n + 1), we are saying: “keep all the bits that are already 1, and if (n + 1) has turned a 0 into a 1, then turn that into 1 too.” In effect, it ensures that the rightmost 0 becomes 1, and everything else stays the same. For instance, with n = 1011, n + 1 = 1100, and n | (n + 1) = 1111. Now that 0 at the 2⁰ position (counting from right) has been set. Learners often ask: what if the number already has all bits set — like n = 111 (binary for 7)? Then n + 1 = 1000, and n | (n + 1) = 111 | 1000 = 1111, which simply adds a new 1 to the next left bit — exactly what we want.

Approach

Step 1: Use Bitwise OR with (n + 1)
To set the rightmost 0 bit in a number, a known trick is to use:
result = n | (n + 1)
This works because (n + 1) flips the rightmost 0 to 1 and turns all bits to the right of it to 0.
When we do a bitwise OR with the original number n, that flipped 0 gets set to 1, and all the bits on the right remain unchanged.

Step 2: Return the Result
Store the final result in a variable (say, result) and return it as the output.

Dry Run

Let’s do a detailed Dry Run for the given code with input: n = 15

Step 1: Understand the Goal
We want to set the rightmost unset (0) bit in the binary representation of the number n.
This is done using the expression:
result = n | (n + 1)

Step 2: Input and Initial State
Input: n = 15
We now convert 15 to binary:
15 = 00001111

Let’s look at the bit positions (0-based from right to left):
Position: 7 6 5 4 3 2 1 0
Binary: 0 0 0 0 1 1 1 1

Here, the rightmost unset (0) bit is at position 4 (counting from the right, 0-based index).
We aim to set this bit to 1 while keeping other bits unchanged.

Step 3: Perform n + 1
n = 15, so n + 1 = 16
Let’s convert 16 to binary:
16 = 00010000

Bit positions:
Position: 7 6 5 4 3 2 1 0
Binary: 0 0 0 1 0 0 0 0

Step 4: Perform Bitwise OR Operation
We now compute:
result = n | (n + 1)
= 00001111 | 00010000
= 00011111

Let’s verify bit by bit:

  • 0 | 0 = 0
  • 0 | 0 = 0
  • 0 | 0 = 0
  • 0 | 1 = 1 ← bit at position 4 gets set
  • 1 | 0 = 1
  • 1 | 0 = 1
  • 1 | 0 = 1
  • 1 | 0 = 1

So, the final binary result is: 00011111, which is 31

Step 5: Final Output
updatedNumber = 31

Hence, for input n = 15, the number with the rightmost 0-bit set becomes 31.

Code for All Languages
C++ 
#include <iostream>      // for cin and cout
using namespace std;

class Solution {
public:

    // Function to set the rightmost unset bit in the binary representation of n
    int setBit(int n) {
    
        // Step 1: OR with (n + 1) sets the rightmost 0 bit
        int result = n | (n + 1);
        
        return result;
    }
};

// Driver code
int main() {
    int n;

    // Input the number
    cin >> n;

    Solution sol;

    // Call the function to set the rightmost unset bit
    int updatedNumber = sol.setBit(n);

    // Output the result
    cout << updatedNumber;

    return 0;
}

Java 
import java.util.Scanner;    // for Scanner class

class Solution {

    // Function to set the rightmost unset bit in the binary representation of n
    static int setBit(int n) {
    
        // Step 1: OR with (n + 1) sets the rightmost 0 bit
        int result = n | (n + 1);
        return result;
    }
}

// Driver code
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n;

        // Input the number
        n = sc.nextInt();

        Solution sol = new Solution();

        // Call the function to set the rightmost unset bit
        int updatedNumber = sol.setBit(n);

        // Output the result
        System.out.print(updatedNumber);

        sc.close();
    }
}

Python 
# Function to set the rightmost unset bit in the binary representation of n
class Solution:
    def setBit(self, n):
    
        # Step 1: OR with (n + 1) sets the rightmost 0 bit
        result = n | (n + 1)
        
        return result

# Driver code
if __name__ == "__main__":
    # Input the number
    n = int(input())

    sol = Solution()

    # Call the function to set the rightmost unset bit
    updatedNumber = sol.setBit(n)

    # Output the result
    print(updatedNumber)

Javascript 
class Solution {
  
    // Function to set the rightmost unset bit in the binary representation of n
    setBit(n) {
      
        // Step 1: OR with (n + 1) sets the rightmost 0 bit
        let result = n | (n + 1);
      
        return result;
    }
}

// Driver code
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.question('', function(line) {
    const n = parseInt(line.trim());

    const sol = new Solution();

    // Call the function to set the rightmost unset bit
    const updatedNumber = sol.setBit(n);

    // Output the result
    console.log(updatedNumber);

    rl.close();
});

Time Complexity: O(1)

Bit Manipulation Operation: O(1)
The core logic involves a single bitwise OR operation: n | (n + 1). This is a basic bitwise operator, and all bitwise operations execute in constant time irrespective of the actual integer value. No loops or recursive calls are involved. Hence, this is performed in O(1) time.

Final Time Complexity: O(1)
All operations in the program are done in constant time.
There are no loops, no recursion, and no size-dependent operations.
Therefore, the overall time complexity is O(1).

Space Complexity: O(1)

Auxiliary Space Complexity: O(1)
This refers to the extra space used internally during the computation, excluding the input and output. In this program:

  • Few fixed-size variables are declared: n and result.
  • Both are simple integer variables. No arrays, objects, strings, or dynamic memory allocations are used.
  • Hence, the auxiliary space required is constant, i.e., O(1).

Total Space Complexity: O(1)
This includes both the auxiliary space and space used for input/output handling. In this program:

  • The input variable n is a fixed-size integer.
  • No additional memory is allocated for storing the output.
  • The entire program operates using a constant number of fixed-size variables.
  • Therefore, the total space required remains constant and is O(1).

Similar Problems

Kth Bit is Set or Not

Given two positive integer n and k, check if the kth index bit of n is set or not.
Note: A bit is called set if it is 1. 

Get, Set, Clear ith Bit

Given a 32 bit unsigned integer num and an integer i. Perform following operations on the number - 

1. Get i-th bit
2. Set i-th bit
3. Clear i-th bit