На первый взгляд кажется, что задача сложная, но фактически она очень проста. Чтобы решить ее, задайте себе вопрос: «Как узнать, какие биты в двух числах различаются?». Ответ прост — с помощью операции XOR.

Каждая единица результирующего числа соответствует биту, который не совпадает в числах A и B. Поэтому расчет количества несовпадающих битов в числах А и В сводится к подсчету число единиц в числе A XOR B:

int bitSwapRequired(int a, int b) {
    int count = 0;
    for (int c = a ^ b; c != 0; c = c >> 1) {
        count += c & 1;
    }
    return count;
}

Этот код хорош, но можно сделать его еще лучше. Вместо многократного сдвига для проверки значащего бита достаточно будет инвертировать младший ненулевой разряд и подсчитывать, сколько раз понадобится проделать эту операцию, пока число не станет равным нулю. Операция c = c & ( c — 1) очищает младший ненулевой бит числа c.

Приведенный далее код реализует данный метод:

public static int bitSwapRequired(int a, int b) {
    int count = 0;
    for (int c = a ^ b; c != 0; c = c & (c - 1)) {
        count++;
    }
    return count;
}

Это одна из типичных задач на работу с битами, которые любят давать на собеседовании. Если вы никогда с ними не сталкивались, вам будет сложно сразу решить задачу, поэтому запомните использованные здесь трюки.

_{Разбор взят из перевода книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.
Если он вам понравился, то рекомендуем купить книгу «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию».}

Хинт для программистов: если зарегистрируетесь на соревнования Huawei Cup, то бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.

Перейти к регистрации