Условие

Допустим, у нас есть целое число n. Его дополнением (комплементом) называется число, полученное путем замены всех битов 0 на 1 и всех битов 1 на 0 в его двоичном представлении. Например, для числа 5 (двоичное представление 101) комплемент будет 010, что соответствует десятичному числу 2. Требуется написать функцию, которая принимает целое число n и возвращает его комплемент.

Примеры

Input: n = 5 Output: 2 Explanation: Двоичное представление числа 5 — "101". Его комплемент — "010", что соответствует числу 2 в десятичной системе.

Input: n = 7 Output: 0 Explanation: Двоичное представление числа 7 — "111". Его комплемент — "000", что соответствует числу 0 в десятичной системе.

Input: n = 10 Output: 5 Explanation: Двоичное представление числа 10 — "1010". Его комплемент — "0101", что соответствует числу 5 в десятичной системе.

Решение

fun bitwiseComplement(n: Int): Int {
    // Если число равно 0, его комплемент — 1
    if (n == 0) return 1

    // Создаем маску с такими же битами, как у n, все из которых равны 1
    var mask = 0
    var temp = n
    while (temp > 0) {
        mask = (mask shl 1) or 1
        temp = temp shr 1
    }

    // Комплемент числа путем применения XOR с маской
    return n xor mask
}

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

O(log n), где n — входное число. Это связано с количеством битов в числе n, поскольку мы проходим по каждому биту один раз.

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

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