Биты, необходимые для изменения одного числа в другое

Скажем, у меня есть два положительных числа a и b. Сколько бит должно быть инвертировано для преобразования a в b? Я просто хочу подсчет, а не точное положение разных бит.

Предположим, что a = 10 (1010) и b = 8 (1000). В этом случае количество бит, которое должно быть инвертировано, равно 1.

Любой обобщенный алгоритм?

Ответ 1

Решение прост

Шаг 1) Вычислить XOR b
Шаг 2) Подсчитайте количество установленных бит в результатах

Готово!

Ответ 2

int a = 10;
int b = 8;

int c = a ^ b; //xor
int count = 0;
while (c != 0)
{
  if ((c & 1) != 0)
    count++;
  c = c >> 1;
}
return count;

Ответ 3

changeMask = a XOR b
bitsToChange = 0
while changeMask>0
  bitsToChange = bitsToChange + (changeMask AND 1)
  changeMask = changeMask >> 1
loop
return bitsToChange

Ответ 4

Хорошие старомодные бит-операции!

size_t countbits( unsigned int n )
{
   size_t bits = 0;
   while( n )
   {
      bits += n&1;
      n >>= 1;
   }
   return bits;
}

countbits( a ^ b );

Это могло бы работать как на C, так и на С++. Вы можете (только на С++) сделать countbits функцией шаблона.

Ответ 5

Собственно, смиренно опираясь на предыдущий ответ - это может работать лучше для преобразования a в b:

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

вычислить (a XOR b) AND ~ b

подсчитать установленные биты

пост исправлено в соответствии с комментарием. Спасибо!

Ответ 6

abs (popcount (a) - popcount (b)), где popcount подсчитывает биты, установленные в количестве (существует множество различных вариантов)