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

Question

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

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

Какой-нибудь обобщенный алгоритм?

Answer 1

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

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

Готово!

Answer 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;

Answer 3

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

Answer 4

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

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

countbits( a ^ b );

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

Answer 5

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

Answer 6

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

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

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

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

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