Skip to main content

Bit Manipulation

Number Complement Solution In C++/Java/Python/JS

Problem Description

The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.

For example, The integer 5 is "101" in binary and its complement is
"010" which is the integer 2.

Given an integer num, return its complement.

Example

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Input: num = 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

Constraints

  • 1 <= num <= 2^31
💡
Try it Yourself First
We’ve all flipped switches from on to off — now imagine doing that to every bit in a number’s binary form. In this problem, we’re asked to find what number we get when every 0 becomes 1 and every 1 becomes 0 — its binary complement.

Brute Force Approach

Intuition

Let’s begin by thinking about what a complement really means. In simple terms, if we have a binary number like 101, its complement is just the number we get by flipping every bit: all 1’s become 0, and all 0’s become 1. So 101 becomes 010. This flipping only applies to the part of the number that is actually present — we ignore any leading zeros that would have existed in a fixed-width system like 32 bits. In this problem, we’re focusing only on the active portion of the binary number, meaning the bits from the most significant 1 to the least significant bit.

Now let’s understand the intuition behind how we can actually achieve this. We are given a number in decimal form, like 5. The first step is to convert this into binary, because that’s the only way we can see and manipulate individual bits.

How to Convert Decimal to Binary?

To convert a decimal number to binary, we repeatedly divide the number by 2 and keep track of the remainder at each step. This is because binary is base 2, so we are essentially figuring out which powers of 2 are needed to make up the number.

We follow this logic:

  • Step 1: Divide the number by 2.
  • Step 2: Record the remainder (will always be 0 or 1).
  • Step 3: Update the number to the quotient of that division.
  • Step 4: Repeat until the number becomes 0.
  • Step 5: The binary number is the reverse of the remainders we recorded.

Example: Convert 6 to Binary

We start with the number 6 and keep dividing by 2, noting down the remainder each time:

  • 6 divided by 2 gives quotient 3, remainder 0 → Write down 0
  • 3 divided by 2 gives quotient 1, remainder 1 → Write down 1
  • 1 divided by 2 gives quotient 0, remainder 1 → Write down 1

Now we stop, because the quotient is 0.

We collected the remainders in the order: 0, 1, 1

To get the correct binary number, we reverse the order, so we get: 1, 1, 0

Why Reverse the Remainders?
Here’s the intuition: the first remainder we get corresponds to the least significant bit (the rightmost bit), because it comes from dividing the original number. The later remainders correspond to higher powers of 2. So to build the binary number correctly, we take the remainders from bottom to top, or simply reverse the order we collected them.

Once we have this binary form (say 101), we clearly observe where the 1’s and 0’s are. We now apply the basic idea of a complement: just flip every bit — 1 becomes 0, and 0 becomes 1 — so 101 turns into 010. Now we need to convert this complemented binary back into a decimal number, because the final answer must be in decimal format.

How to Convert Binary to Decimal?

To convert a binary number to decimal, we multiply each digit (bit) by powers of 2 based on its position and then add them all together. This is because binary is a base-2 number system, where each position represents a power of 2, starting from the rightmost digit (which is the least significant bit).

We follow this logic:
Step 1: Start from the rightmost bit (position 0).
Step 2: For each bit, multiply it by 2 raised to its position index.
Step 3: Add all the results together.
Step 4: The final sum is the decimal equivalent of the binary number.

Example: Convert Binary 110 to Decimal

Let’s break the binary number 110 into its digits, from right to left:

  • Rightmost bit: 0 → This is at position 0, so we do 0 × 2⁰ = 0
  • Middle bit: 1 → This is at position 1, so we do 1 × 2¹ = 2
  • Leftmost bit: 1 → This is at position 2, so we do 1 × 2² = 4

Now, we add all the results:
4 + 2 + 0 = 6

Final Answer

So, the binary number 110 is equal to the decimal number 6.

Approach

Step 1: Convert Decimal to Binary
We start by converting the given decimal number into its binary form.

  • Initialize an empty container binaryBits to store the binary digits.
  • Create a temporary variable temp and set it equal to num.
  • Use a loop to extract binary digits. At each step, store temp % 2 into binaryBits. Then divide temp by 2 to move to the next bit.
  • This will store the binary representation in reverse order (from LSB to MSB).

This completes the conversion of the decimal number into binary form, stored in binaryBits.

Step 2: Take the Complement of Each Bit
Now we flip all bits in the binary representation.

  • Traverse through each bit stored in binaryBits.
  • If a bit is 0, change it to 1.
  • If a bit is 1, change it to 0.

This flips all the bits to form the complement in binary format.

Step 3: Convert Complemented Binary Back to Decimal
Next, we convert the complemented binary number back to decimal form.

  • Initialize complement = 0 and power = 1 to represent the value of 2^i at each position.
  • Traverse through the complemented binaryBits. Multiply each bit with the corresponding power. Add the result to complement. Update power by multiplying it with 2 for the next bit position.

This gives us the decimal equivalent of the complemented binary.

Step 4: Return the Final Complement
After reconstructing the complemented binary into a decimal number, return complement as the final result.

Dry Run

Let’s do a detailed Dry Run for the given input to understand how the function calculates the complement of a number using brute-force:

Input: num = 5

Step 1: Convert decimal to binary

We begin by converting the decimal number 5 into binary form.
We initialize:

  • temp = 5
  • binaryBits = []

Now we repeatedly divide temp by 2 and store the remainder:

First iteration:

  • temp = 5
  • 5 % 2 = 1 → push 1 to binaryBits → binaryBits = [1]
  • temp = 5 / 2 = 2

Second iteration:

  • temp = 2
  • 2 % 2 = 0 → push 0 to binaryBits → binaryBits = [1, 0]
  • temp = 2 / 2 = 1

Third iteration:

  • temp = 1
  • 1 % 2 = 1 → push 1 to binaryBits → binaryBits = [1, 0, 1]
  • temp = 1 / 2 = 0 → loop ends

Final binaryBits = [1, 0, 1]
Note: The binary representation is stored in reverse order, so this corresponds to binary 101

Step 2: Take the complement (flip all bits)

We now flip all the bits in binaryBits:

  • Index 0: binaryBits[0] = 1 → flip to 0 → binaryBits = [0, 0, 1]
  • Index 1: binaryBits[1] = 0 → flip to 1 → binaryBits = [0, 1, 1]
  • Index 2: binaryBits[2] = 1 → flip to 0 → binaryBits = [0, 1, 0]

Final complemented binaryBits = [0, 1, 0]
This is binary 010 (still stored in reverse order)

Step 3: Convert complemented binary to decimal

We now convert [0, 1, 0] back to decimal using powers of 2.

We initialize:

  • complement = 0
  • power = 1

Loop through the bits:

Index 0:

  • binaryBits[0] = 0
  • complement += 0 × 1 = 0 → complement = 0
  • power *= 2 → power = 2

Index 1:

  • binaryBits[1] = 1
  • complement += 1 × 2 = 2 → complement = 2
  • power *= 2 → power = 4

Index 2:

  • binaryBits[2] = 0
  • complement += 0 × 4 = 0 → complement = 2
  • power *= 2 → power = 8

Final complement = 2

Final Output

We print the final complement value:

Output: 2

Code for All Languages
C++ 
#include <iostream>      // for cin and cout
#include <vector>        // for using vector to store binary digits
using namespace std;

class Solution {
public:
    // Function to find the complement of an integer using brute-force approach
    int findComplement(int num) {

        // Step 1: Convert decimal to binary (store bits in a vector)
        vector<int> binaryBits;

        int temp = num;
        while (temp > 0) {
            // Store the remainder (0 or 1) as the next bit
            binaryBits.push_back(temp % 2);
            temp = temp / 2;
        }

        // Step 2: Take the complement (flip all bits)
        for (int i = 0; i < binaryBits.size(); i++) {
            // Flip 0 to 1 and 1 to 0
            if (binaryBits[i] == 0) {
                binaryBits[i] = 1;
            } else {
                binaryBits[i] = 0;
            }
        }

        // Step 3: Convert the complemented binary back to decimal
        int complement = 0;
        long power = 1;

        for (int i = 0; i < binaryBits.size(); i++) {
            // Add each bit multiplied by its corresponding power of 2
            complement += binaryBits[i] * power;
            power *= 2;
        }

        // Return the decimal equivalent of the complement
        return complement;
    }
};

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

    // Input the number whose complement is to be found
    cin >> num;

    Solution sol;

    // Call the function and print the result
    cout << sol.findComplement(num);

    return 0;
}

Java 
import java.util.*; // For Scanner and ArrayList

class Solution {
    // Function to find the complement of an integer using brute-force approach
    public int findComplement(int num) {
        
        // Step 1: Convert decimal to binary (store bits in an ArrayList)
        ArrayList<Integer> binaryBits = new ArrayList<>();
        
        int temp = num;
        while (temp > 0) {
            // Store the remainder (0 or 1) as the next bit
            binaryBits.add(temp % 2);
            temp = temp / 2;
        }
        
        // Step 2: Take the complement (flip all bits)
        for (int i = 0; i < binaryBits.size(); i++) {
            // Flip 0 to 1 and 1 to 0
            if (binaryBits.get(i) == 0) {
                binaryBits.set(i, 1);
            } else {
                binaryBits.set(i, 0);
            }
        }

        // Step 3: Convert the complemented binary back to decimal
        int complement = 0;
        int power = 1;

        for (int i = 0; i < binaryBits.size(); i++) {
            // Add each bit multiplied by its corresponding power of 2
            complement += binaryBits.get(i) * power;
            power *= 2;
        }

        // Return the decimal equivalent of the complement
        return complement;
    }
}

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

        // Input the number whose complement is to be found
        int num = sc.nextInt();

        Solution sol = new Solution();

        // Call the function and print the result
        System.out.println(sol.findComplement(num));
    }
}

Python 
class Solution:
    # Function to find the complement of an integer using brute-force approach
    def findComplement(self, num: int) -> int:

        # Step 1: Convert decimal to binary (store bits in a list)
        binaryBits = []

        temp = num
        while temp > 0:
            # Store the remainder (0 or 1) as the next bit
            binaryBits.append(temp % 2)
            temp = temp // 2

        # Step 2: Take the complement (flip all bits)
        for i in range(len(binaryBits)):
            # Flip 0 to 1 and 1 to 0
            if binaryBits[i] == 0:
                binaryBits[i] = 1
            else:
                binaryBits[i] = 0

        # Step 3: Convert the complemented binary back to decimal
        complement = 0
        power = 1

        for i in range(len(binaryBits)):
            # Add each bit multiplied by its corresponding power of 2
            complement += binaryBits[i] * power
            power *= 2

        # Return the decimal equivalent of the complement
        return complement


# Driver code
if __name__ == "__main__":
    # Input the number whose complement is to be found
    num = int(input())

    sol = Solution()

    # Call the function and print the result
    print(sol.findComplement(num))

Javascript 
/**
 * @param {number} num
 * @return {number}
 */
var findComplement = function(num) {
    // Step 1: Convert decimal to binary (store bits in an array)
    let binaryBits = [];

    let temp = num;
    while (temp > 0) {
        // Store the remainder (0 or 1) as the next bit
        binaryBits.push(temp % 2);
        temp = Math.floor(temp / 2);
    }

    // Step 2: Take the complement (flip all bits)
    for (let i = 0; i < binaryBits.length; i++) {
        // Flip 0 to 1 and 1 to 0
        if (binaryBits[i] === 0) {
            binaryBits[i] = 1;
        } else {
            binaryBits[i] = 0;
        }
    }

    // Step 3: Convert the complemented binary back to decimal
    let complement = 0;
    let power = 1;

    for (let i = 0; i < binaryBits.length; i++) {
        // Add each bit multiplied by its corresponding power of 2
        complement += binaryBits[i] * power;
        power *= 2;
    }

    // Return the decimal equivalent of the complement
    return complement;
};

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

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

// Read input
rl.question('', function(num) {
    num = parseInt(num);

    // Call the function and print the result
    console.log(findComplement(num));

    rl.close();
});

Time Complexity: O(log(n))

Converting Decimal to Binary: O(log n)
We repeatedly divide the number by 2 and store the remainder (0 or 1) in a list.
This runs until the number becomes 0. The number of iterations depends on how many bits are required to represent the number.
For a number n, the number of bits is log₂(n).

Flipping All Bits: O(log n)
We iterate through the list of bits once and flip each bit from 0 to 1 or 1 to 0.
Since the number of bits is log₂(n), we perform that many operations.

Converting Binary Back to Decimal: O(log n)
We again iterate through the list of bits and for each bit, multiply by the corresponding power of 2 and accumulate the result.
Each operation (multiplication and addition) is constant time, and we do this for log₂(n) bits.

Final Time Complexity: O(log n)
All three steps depend linearly on the number of bits required to represent the number, which is log₂(n). There are no nested loops, recursion, or data structures that scale beyond this.

Space Complexity: O(log(n))

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

  • A vector named binaryBits is used to store the binary representation of the number.
  • For a number num, the number of binary digits required is log₂(num).
  • Therefore, the vector will store log₂(num) bits.
  • Additionally, a few fixed-size variables are used: temp, complement, power, and i (all integers).

Hence, the auxiliary space is O(log n) due to the vector used for binary storage.

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

  • Input variable num and loop counter i are fixed-size integers.
  • Output is directly printed using cout, with no extra storage.
  • However, the vector binaryBits holds log₂(num) binary digits during the entire computation.
  • This contributes to the overall space usage.

Therefore, the total space required is O(log n).

In the brute-force method, we flipped bits manually by converting to binary and back — a bit clunky and slow. But what if we could flip all bits at once using a clever bitmask trick and a single XOR?

Optimal Approach

Intuition

In the brute-force approach, we first converted the number to its binary form, flipped each bit manually (changing 0 to 1 and 1 to 0), and then converted the result back to decimal. While this works fine for small numbers, it's not very efficient or elegant — especially since we’re dealing with extra steps like string conversions and manual flipping. That makes us ask: Can we flip all bits of a number directly without going through its binary string? The answer lies in using a bitmask — a number that has all bits set to 1 and is the same length as our given number in binary.

Let’s take an example where num = 5. In binary, 5 is written as 101. What we want is to flip each bit of this number. So 1 becomes 0 and 0 becomes 1, which turns 101 into 010, and that is 2 in decimal. Now, a clever trick to flip all bits at once is to use the XOR operator with a number that has all bits set to 1 — that means a mask like 111. Why does this work? Because XOR flips bits when they are different: 1 XOR 1 = 0, and 0 XOR 1 = 1. So when we do 5 XOR 7, we get 2. This works perfectly!

Now you might wonder, how do we get this mask automatically for any number — not just for 5? Here’s how: we start with mask = 0 and make a temporary copy of the number, say temp = num.

What is Mask and Left Shift (<<) Operator?

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.

We now want to build a number that has the same number of bits as num, but all of them should be 1. So we run a loop: in every step, we left-shift the mask (which moves bits to the left, just like adding a new digit), and then we OR it with 1 to add a 1 at the rightmost position. We keep doing this as long as temp > 0, and in each step we divide temp by 2 to reduce its bit length. When temp becomes 0, the mask is fully built and contains all 1s in the positions where num had bits. This mask is now ready to XOR with num and flip all its bits perfectly

A question might be: What if num is already all 1s like 7 (111)? Then its complement becomes 000, which is 0, and yes, that’s completely valid.

Approach

Step 1: Create a Bitmask with All Bits Set to 1
We start by creating a bitmask that has the same number of bits as the original number.

  • Initialize mask = 0 and set a temporary variable temp = num.
  • Use a loop to shift the mask to the left by 1 and set the least significant bit to 1 in each iteration.
  • At the same time, divide temp by 2 in each step to count how many bits num has. This will generate a bitmask with all bits set to 1 for the length of the number.
    For example, if num is 5 (101), mask becomes 7 (111).

This completes the construction of the bitmask.

Step 2: XOR the Number with the Bitmask
Now we use XOR to flip all the bits of the original number. Apply the XOR operation between num and mask using: complement = num ^ mask
This flips all bits of num, effectively computing its binary complement.

Step 3: Return the Final Complement
The result from the XOR operation is already in decimal form. Return complement as the final output. This is the required number whose binary is the flipped version of the binary of num.

Dry Run

Let’s do a detailed Dry Run for the given input to understand how the function calculates the complement of a number using bitmask and XOR approach:

Input: num = 5

Step 1: Create a mask with all bits set to 1 (same length as num)

We initialize:

  • mask = 0
  • temp = 5

Let’s track how the loop builds the mask:

First iteration:

  • temp = 5 > 0 → loop continues
  • mask = (0 << 1) | 1 = 0 | 1 = 1
  • temp = 5 >> 1 = 2

Second iteration:

  • temp = 2 > 0 → loop continues
  • mask = (1 << 1) | 1 = 2 | 1 = 3
  • temp = 2 >> 1 = 1

Third iteration:

  • temp = 1 > 0 → loop continues
  • mask = (3 << 1) | 1 = 6 | 1 = 7
  • temp = 1 >> 1 = 0 → loop ends

Final mask = 7

Explanation:
Binary of 5 = 101 → 3 bits
We constructed a mask with 3 bits set: mask = 111 (which is 7 in decimal)

Step 2: XOR num with mask

We calculate:

  • complement = num ^ mask
  • complement = 5 ^ 7
  • Binary:
    101 (5)
    ^ 111 (7)
    = 010 → 2

So, complement = 2

Step 3: Return the result
The function returns the decimal equivalent of the complement.

Output: 2

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

class Solution {
public:
    // Function to find the complement of an integer using XOR approach
    int findComplement(int num) {

        // Step 1: Create a mask with all bits set to 1 of the same length as num
        int mask = 0;
        int temp = num;

        while (temp > 0) {
            mask = (mask << 1) | 1;
            temp = temp >> 1;
        }

        // Step 2: XOR the number with the mask to flip all bits
        int complement = num ^ mask;

        // Return the decimal equivalent of the complement
        return complement;
    }
};

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

    // Input the number whose complement is to be found
    cin >> num;

    Solution sol;

    // Call the function and print the result
    cout << sol.findComplement(num);

    return 0;
}

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

class Solution {

    // Function to find the complement of an integer using XOR approach
    public int findComplement(int num) {

        // Step 1: Create a mask with all bits set to 1 of the same length as num
        int mask = 0;
        int temp = num;

        while (temp > 0) {
            mask = (mask << 1) | 1;
            temp = temp >> 1;
        }

        // Step 2: XOR the number with the mask to flip all bits
        int complement = num ^ mask;

        // Return the decimal equivalent of the complement
        return complement;
    }
}


class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();

        Solution sol = new Solution();
        System.out.println(sol.findComplement(num));
    }
}

Python 
class Solution:
    # Function to find the complement of an integer using XOR approach
    def findComplement(self, num: int) -> int:

        # Step 1: Create a mask with all bits set to 1 of the same length as num
        mask = 0
        temp = num

        while temp > 0:
            mask = (mask << 1) | 1
            temp = temp >> 1

        # Step 2: XOR the number with the mask to flip all bits
        complement = num ^ mask

        # Return the decimal equivalent of the complement
        return complement


# Driver code
if __name__ == "__main__":
    # Input the number whose complement is to be found
    num = int(input())

    sol = Solution()

    # Call the function and print the result
    print(sol.findComplement(num))

Javascript 
/**
 * @param {number} num
 * @return {number}
 */
var findComplement = function(num) {
    // Step 1: Create a mask with all bits set to 1 of the same length as num
    let mask = 0;
    let temp = num;

    while (temp > 0) {
        mask = (mask << 1) | 1;
        temp = temp >> 1;
    }

    // Step 2: XOR the number with the mask to flip all bits
    let complement = num ^ mask;

    // Return the decimal equivalent of the complement
    return complement;
};

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

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

// Read input
rl.question('', function(num) {
    num = parseInt(num);

    // Call the function and print the result
    console.log(findComplement(num));

    rl.close();
});

Time Complexity: O(1)

Bit Mask Generation Loop: O(log(n))
The while loop runs as long as temp > 0. In each iteration, temp is right-shifted by 1, effectively halving it.
This loop runs approximately log₂(num) times (where num is the input integer).
Hence, the loop for generating the mask takes O(log N) time.

Bitwise XOR Operation: O(1)
After the mask is ready, the XOR operation num ^ mask is performed.
This is a constant-time bit manipulation operation, irrespective of the number's size in bits.
So, this step is O(1).

Final Time Complexity: O(log(n))
The only non-constant-time part is the loop used to generate the bitmask.
All other operations run in constant time.
Therefore, the total time complexity of the program is O(logn), where n is the input number.

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:

  • A few fixed-size variables are used: mask, temp, complement, and loop control variables.
  • All of them are simple integer variables.
  • No arrays, strings, dynamic containers, or memory allocations are used.
    Hence, the auxiliary space remains constant, i.e., O(1).

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

  • The input variable num and output variable are of fixed size.
  • Output is handled directly using cout without storing any additional data.
  • No additional space is used beyond a few integer variables.
    Thus, the total space required is 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. 

Set the Rightmost Unset Bit

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