Skip to main content

Find 1s complement of an Integer

The problem involves finding the one's complement of a given integer. The one's complement of an integer is obtained by changing all the 1s to 0s and all the 0s to 1s in its binary representation. In this article, we will explore the concept of finding the one's complement of an integer and using bitwise operations.

Calculate one's complement of a number

Problem Statement and Description

Given an integer num, the goal is to find its one's complement. To do this, we need to invert each bit in the binary representation of the integer. This means that every 0 should be changed to 1, and every 1 should be changed to 0.

Example

Consider the following examples to understand the concept:

  • For the number 9 (binary 1001): The one's complement is 0110, which is 6 in decimal.

  • For the number 50 (binary 110010): The one's complement is 001101, which is 13 in decimal.

  • For the number 32 (binary 100000): The one's complement is 011111, which is 31 in decimal.

Idea to Solve the Problem

The idea to solve the problem involves the following steps:

  1. If the given number num is negative, simply apply the bitwise NOT operation (~num) to find the one's complement.

  2. If the given number num is positive, calculate the one's complement using bitwise operations.

Standard Pseudocode

function onesComplement(num):
    if num is negative:
        Print "Number :", num
        Print "1s Complement :", ~num
    else:
        total_bits = log2(num) + 1
        ones = ((1 << total_bits) - 1) XOR num
        Print "Number :", num
        Print "1s Complement :", ones

Algorithm Explanation

  1. Check if the given number num is negative. If it is negative, apply the bitwise NOT operation (~num) to find the one's complement and print the result.

  2. If the given number num is positive, calculate the total number of bits in the binary representation of num using total_bits = log2(num) + 1.

  3. Calculate the one's complement of the positive number by performing a bitwise XOR operation between the integer obtained by performing bitwise OR operations on 1 << total_bits and num. This effectively flips all the bits to find the one's complement.

  4. Print the original number and its corresponding one's complement.

Code Solution

Time Complexity

The time complexity of the algorithm depends on the number of bits in the binary representation of the given number. The most significant factor is the calculation of the total number of bits, which is O(log(num)).





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment