Number Complement

🏠 ⬅️ ➡️

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 1:

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.

Example 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 < 231

Note: This question is the same as 1009: https://leetcode.com/problems/complement-of-base-10-integer/

Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: num, complement

    ! Example 1
    num = 5
    write (*, '(A, I0)') 'Complement of ', num, ' is ', complement(num)

    ! Example 2
    num = 1
    write (*, '(A, I0)') 'Complement of ', num, ' is ', complement(num)

contains

    function complement(num) result(res)
        implicit none
        integer, intent(in) :: num
        integer :: res

        res = btest(num, 0_8)
    end function complement

end program main
❌ Compiled
❌ Executed
❌ Correct 
!include(header.f90)

program complement
    implicit none

    integer :: num, complement

    ! Test case 1:
    num = 5
    complement = get_complement(num)
    write (*,*) "Complement of ", num, " is ", complement

    ! Test case 2:
    num = 1
    complement = get_complement(num)
    write (*,*) "Complement of ", num, " is ", complement

contains

    function get_complement(num) result(complement)
        implicit none
        integer, intent(in) :: num
        integer :: complement

        ! Convert the integer to binary
        integer :: binary_num(32)
        binary_num = 0
        do i = 1, 32
            binary_num(i) = mod(num, 2)
            num = num / 2
        end do

        ! Flip all the 0's to 1's and all the 1's to 0's
        do i = 1, 32
            if (binary_num(i) == 0) then
                binary_num(i) = 1
            else
                binary_num(i) = 0
            end if
        end do

        ! Convert the binary array back to an integer
        complement = 0
        do i = 1, 32
            complement = complement * 2 + binary_num(i)
        end do
    end function get_complement
end program complement

!include(footer.f90)
🌐 Data from online sources 
def find_complement(num: int) -> int:
    bit_length = 0
    mask = num
    while mask > 0:
        mask >>= 1
        bit_length += 1
    all_ones = (1 << bit_length) - 1

    return num ^ all_ones

First, we calculate the number of bits in the binary representation of the input integer num. We do this by consecutively right-shifting the number (bitwise operation) and counting the iterations until the number becomes 0. This gives us the length of the binary representation.

Once we have the length, we create a bitmask of the same length with all bits set to 1 (for example, if the length is 3, the bitmask would be 111 in binary). To get the complement of the input integer, we then XOR (^ operator) the number with this all-1 mask. The XOR operation returns 1 when the input bits are different and 0 when they are the same, so if we have a 0 in the input, we will get 1 and vice versa. This way, we get the complement of the original number.

Finally, we return the resulting number, which is the complement of the input integer num.

🌐 Data from online sources 
int findComplement(int num) {
    int bitLength = 0;
    int mask = num;
    while (mask > 0) {
        mask >>= 1;
        bitLength++;
    }
    int allOnes = (1 << bitLength) - 1;

    return num ^ allOnes;
}

First, we calculate the number of bits in the binary representation of the input integer num. We do this by consecutively right-shifting the number (bitwise operation) and counting the iterations until the number becomes 0. This gives us the length of the binary representation.

Once we have the length, we create a bitmask of the same length with all bits set to 1 (for example, if the length is 3, the bitmask would be 111 in binary). To get the complement of the input integer, we then XOR (^ operator) the number with this all-1 mask. The XOR operation returns 1 when the input bits are different and 0 when they are the same, so if we have a 0 in the input, we will get 1 and vice versa. This way, we get the complement of the original number.

Finally, we return the resulting number, which is the complement of the input integer num.