Реализация функции, определяющей количество битов, которые необходимо изменить, чтобы из целого числа А получить целое число B

  • , Задачки
  • 2 минуты

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

Наши тесты для вас:
— Тест на знание сленга веб-разработчиков.
— Кто вы во вселенной Звёздных Войн?
— А вы точно программист?