1009. Complement of Base 10 Integer

leetcode easy

#bit-manipulation#csharp#easy#leetcode#math#search

Task

Дополнение целого числа - это целое число, которое получается, если перевернуть все 0 в 1 и все 1 в 0 в его двоичном представлении. Например, целое число 5 - это "101" в двоичном представлении, а его дополнение - "010", то есть целое число 2. Если задано целое число n, верните его дополнение.

Пример:

Input: n = 5

Output: 2

C# solution

matched/original

public class Solution {
    public int FindComplement(int num) {
        int length = (int)Math.Log(num, 2) + 1;
        int mask = (1 << length) - 1;
        return num ^ mask;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int FindComplement(int num) {
        int length = (int)Math.Log(num, 2) + 1;
        int mask = (1 << length) - 1;
        return num ^ mask;
    }
}

Java solution

matched/original

public class Solution {
    public int findComplement(int num) {
        int length = Integer.toBinaryString(num).length();
        int mask = (1 << length) - 1;
        return num ^ mask;
    }
}

Go solution

matched/original

func findComplement(num int) int {
    length := 0
    for i := num; i > 0; i >>= 1 {
        length++
    }
    mask := (1 << length) - 1
    return num ^ mask
}

Explanation

Algorithm

Определение длины двоичного представления:

Найдите длину двоичного представления числа n.

Создание маски:

Создайте маску, которая состоит из всех единиц и имеет ту же длину, что и двоичное представление числа n.

Вычисление дополнения:

Примените побитовую операцию XOR между числом n и маской, чтобы получить дополнение числа.

😎