Количество битов для преобразования

Решение

Объяснение подхода

Эта задача требует найти количество отличающихся битов между двумя числами. Это известная задача в компьютерной науке и кодировании.

Логика простая:

1. Применяем побитовую операцию XOR (исключающее ИЛИ) для двух чисел — результат будет содержать 1 в позициях, где биты отличаются
2. Подсчитываем количество единиц в результате XOR

Почему XOR работает:

• A XOR B возвращает 1, если биты различаются (0⊕1 = 1, 1⊕0 = 1)
• A XOR B возвращает 0, если биты одинаковые (0⊕0 = 0, 1⊕1 = 0)

Пример расчёта

Дано: A = 29 (двоичное 11101), B = 15 (двоичное 01111)

29    = 11101
15    = 01111
------
XOR   = 10010 (десятичное 18)

Теперь считаем единицы в 10010 — их 2. Ответ: 2 бита.

Реализация (Python)

def hammingDistance(a: int, b: int) -> int:
    """
    Определяет количество битов, которые нужно изменить.
    
    Args:
        a: первое число
        b: второе число
    
    Returns:
        количество отличающихся битов
    """
    xor_result = a ^ b  # XOR даёт 1 где биты отличаются
    count = 0
    
    # Подсчитываем количество единиц в XOR результате
    while xor_result:
        count += xor_result & 1  # Проверяем последний бит
        xor_result >>= 1  # Сдвигаем на 1 бит вправо
    
    return count

Альтернативное решение (более компактное)

def hammingDistance(a: int, b: int) -> int:
    # bin() возвращает строку типа "0b11101"
    # count("1") считает количество символов "1"
    return bin(a ^ b).count("1")

Реализация на Java

class Solution {
    public int hammingDistance(int x, int y) {
        int xor = x ^ y;
        int count = 0;
        
        while (xor != 0) {
            count += xor & 1;
            xor >>= 1;
        }
        
        return count;
    }
}

Реализация на JavaScript

function hammingDistance(x, y) {
    let xor = x ^ y;
    let count = 0;
    
    while (xor) {
        count += xor & 1;
        xor >>= 1;
    }
    
    return count;
}

Анализ сложности

• Временная сложность: O(log(max(a, b))) — количество битов в числе

  • В худшем случае проходим по всем битам большего числа
  • Для компактного решения с count("1") в Python это O(k) где k — количество единиц

• Пространственная сложность: O(1) — используем только несколько переменных

Тестовые случаи

# Пример из задачи
assert hammingDistance(29, 15) == 2

# Дополнительные тесты
assert hammingDistance(0, 0) == 0      # Идентичные числа
assert hammingDistance(1, 4) == 2      # 001 vs 100
assert hammingDistance(7, 4) == 1      # 111 vs 100
assert hammingDistance(2147483647, 2147483646) == 1

Рекомендация для QA

При тестировании функции нужно проверить:

• Граничные значения: 0, отрицательные числа (если язык допускает)
• Идентичные числа: результат должен быть 0
• Степени двойки: 1, 2, 4, 8 и т.д.
• Максимальные значения: для int и long
• Случаи одного бита разницы: например 1 и 2

Решение работает за O(log n) времени и O(1) памяти — оптимально для собеседования.