Number Complement

https://leetcode.com/problems/number-complementEasy

Условие

Дано положительное целое число num. Необходимо вернуть его дополнение, где каждый бит числа заменен на противоположный (0 становится 1, а 1 становится 0). Дополнение следует учитывать только для значащих битов числа.

Примеры

Input: num = 5

Output: 2

Explanation: 5 в двоичном виде — 101, его дополнение — 010, что равно 2.
Input: num = 1

Output: 0

Explanation: 1 в двоичном виде — 1, его дополнение — 0, что равно 0.

Решение

fun findComplement(num: Int): Int {
    var mask = 0
    var temp = num

    // Создаем маску, которая имеет все единицы в значащих битах числа num
    while (temp != 0) {
        mask = (mask shl 1) or 1
        temp = temp shr 1
    }

    // Применяем XOR, чтобы инвертировать все значащие биты
    return num xor mask
}

Временная сложность

O(1), так как количество битов фиксировано (32 бита для целых чисел), и операция занимает постоянное время.

Пространственная сложность

O(1), так как используется только фиксированное количество дополнительных переменных.