Hamming Distance

https://leetcode.com/problems/hamming-distance Easy

Условие

Даны два целых числа x и y. Нужно вернуть расстояние Хэмминга между ними. Расстояние Хэмминга — это количество позиций, в которых биты двух чисел отличаются.

Примеры

Input: x = 1, y = 4

Output: 2

Explanation:
1 в двоичном виде: 0001
4 в двоичном виде: 0100
Они отличаются в двух позициях (биты с позиции 1 и 3).

Input: x = 3, y = 1

Output: 1

Решение

fun hammingDistance(x: Int, y: Int): Int {
    var diff = x xor y  // Выполняем XOR между x и y, чтобы получить разницу между битами
    var distance = 0

    // Считаем количество установленных битов (1) в результате XOR
    while (diff != 0) {
        distance += diff and 1  // Увеличиваем расстояние, если младший бит равен 1
        diff = diff shr 1  // Сдвигаем биты вправо
    }

    return distance
}

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

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

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

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