Вопрос интервью: количество битовых свопов, необходимых для преобразования одного целого числа в другое

Question

Мой друг задал этот вопрос в интервью.Я не смог найти решение этой проблемы.Вопрос -

Напишите функцию для вычисления количества битовых свопов, необходимых для преобразования одного целого числа в другое.

Answer 1

Битовая операция, которая может использоваться, чтобы выяснить, какие биты отличаются, является xor.

Каждая 1 в xor будет указывать разный бит между двумя целыми числами.

int getBitSwapCount (int x, int y) {

int count = 0;

for(int z = x^y; z!=0; z = z>> 1)
{
   count += z & 1;
}
return count; 

}

Answer 2

Вопросы для интервью не только о решениях, они также (и это, как правило, даже более важно, чем поиск решения) дают вам возможность показать, как вы будете решать новую проблему, такую ​​как эта. Как бы вы начали это? Есть ли какая-либо дополнительная информация, которую вы хотели бы узнать, чтобы помочь вам решить ее? Существуют ли какие-либо стандартные функции (на любом обычно используемом языке программирования), которые вы хотели бы использовать?

Дайте нам ваш лучший снимок, мы сыграем интервьюера и подскажем, как вы идете ...

Answer 3

XOR значения, а затем подсчитать количество единиц в результате

Answer 4

Возьмите XOR из 2 чисел (скажем, a & b) и сосчитайте количество единиц в a ^ b

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

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

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

Answer 5

Другой подход

найти и двоичную строку и вычислить расстояние Левенштейна путем динамического программирования

Answer 6

Я не вижу ничего особенного в этом вопросе.Перебирая биты обоих целых чисел, объединяя текущие биты с помощью XOR и увеличивая счетчик, если результат не равен нулю, вы получите количество битов, которые отличаются в обоих значениях.