Vultr DocsLatest Content

Complement of Base 10 Integer

Updated on 15 May, 2025
Complement of Base 10 Integer header image

Problem Statement

In computer science, the complement of an integer is obtained by altering every bit in its binary representation: every 0 becomes a 1 and every 1 becomes a 0. For any given integer n, this task involves computing its binary complement. Binary representation converts numbers into a base-2 format, which consists solely of zeros (0) and ones (1). After inverting each bit of this representation, the new binary sequence represents the complement of the original number. This process of "flipping" bits is fundamental in various algorithms and systems for adjusting signals or data values.

Examples

Example 1

Input:

n = 5

Output:

2

Explanation:

5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.

Example 2

Input:

n = 7

Output:

0

Explanation:

7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.

Example 3

Input:

n = 10

Output:

5

Explanation:

10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.

Constraints

  • 0 <= n < 109

Approach and Intuition

  1. Convert the integer n into its binary representation.
    1. For example, if n is 5, its binary equivalent is "101".
  2. Flip every bit of this representation.
    1. Flipping "101" results in "010", by changing each 0 to 1 and each 1 to 0.
  3. Convert this new binary string back into an integer to obtain the complement.
    1. Thus, "010" converts back to the integer 2.

  • Here’s why this problem adheres to a straightforward approach because converting between integers and their binary formats is directly supported in many programming languages, making the flipping process merely a matter of syntax and minimum computation.

  • By examining the problem constraints where 0 <= n < 10^9, one can infer:

    • Even large integers are manageable within computational limits since binary strings remain relatively short (about 30 bits given the maximum constraint).
    • All values of n are non-negative, simplifying the case handling as there’s no need to deal with negative number specifics in binary (like two’s complement).

From this approach, the task of computing the complement of a number can be efficiently automated using simple computational tools or programming functions, allowing handling of a wide range of integers up to nearly a billion, with fast and accurate results.

Solutions

  • Java
  • Python
java 
class Solution {
  public int complement(int value) {
    if (value == 0) return 1;
    int mask = value;
    mask |= (mask >> 1);
    mask |= (mask >> 2);
    mask |= (mask >> 4);
    mask |= (mask >> 8);
    mask |= (mask >> 16);
    return mask ^ value;
  }
}

The Java solution provided calculates the complement of a base-10 integer. First, ensure that if the input integer is zero, the function immediately returns one. Construct a mask starting with the value itself, progressively or-ing this mask by right-shifting itself by 1, 2, 4, 8, and 16 places. This technique expands the highest set bit to all lower positions, thus creating a mask that covers all bits of the value. Finally, apply an XOR operation between the original value and the mask to produce the complement. This method effectively inverts each bit of the input integer within its active length.

python 
class Solution:
    def complement(self, num: int) -> int:
        if num == 0:
            return 1
        mask = num
        mask |= (mask >> 1)
        mask |= (mask >> 2)
        mask |= (mask >> 4)
        mask |= (mask >> 8)
        mask |= (mask >> 16)
        return mask ^ num

This solution implements a method for finding the complement of a base 10 integer in Python. The complement is determined by negating each bit of the number's binary representation. Consider the function complement(self, num: int) -> int in the given Python class:

Start by handling the special case for zero (0), since its complement in binary (1's complement) leads to all bits turned to 1, returning an integer 1.

Using a variable mask, initiate it to the value of num. Subsequently, adjust mask to cover all bits of num up to the most significant 1-bit. This is done by right-shifting mask progressively by 1, 2, 4, 8, then 16 bits, each time performing an OR operation, ensuring that all bits following the highest bit of the initial number are set to 1.

Finally, use the XOR operation between the mask and the original number num. This operation will flip all bits of num up to the most significant 1-bit, effectively generating the complement.

This procedure effectively calculates the bitwise complement of a given integer where all bits are inverted, taking into account the real bit-length of the number. To summarize the steps briefly:

  1. Special case for zero where the function returns 1.
  2. Initially set mask to num.
  3. Expand mask to cover all bits up to the highest significant bit using right-shift and OR operations.
  4. Obtain the complement by XOR-ing mask with num.

This algorithm allows for the bitwise complement to be derived directly and efficiently.

Comments

No comments yet.