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

Question

Допустим, у меня есть значение этого битового поля: 10101001

Как мне проверить, отличается ли какое-либо другое значение от любых n бит. Без учета позиции?

Пример:

10101001
10101011 --> 1 bit different 

10101001
10111001 --> 1 bit different

10101001
01101001 --> 2 bits different

10101001
00101011 --> 2 bits different

Мне нужно сделать много сравнений, так что я в первую очередь ищу производительность, но любую намек очень приветствуется.

Answer 1

Возьмите XOR в двух полях и подсчитайте совокупность результатов.

Answer 2

если вы XOR 2 значения вместе, вы останетесь только с битами, которые отличаются.

Вам нужно только посчитать биты, которые все еще равны 1, и у вас есть ответ

в с:

 unsigned char val1=12;
 unsigned char val2=123;
 unsigned char xored = val1 ^ val2;
 int i;
 int numBits=0;
 for(i=0; i<8; i++)
 {
      if(xored&1) numBits++;
      xored>>=1;
 }

хотя, возможно, есть более быстрые способы подсчета битов в байте (например, вы можете использовать таблицу поиска для 256 значений)

Answer 3

Точно так же, как и все остальные, используйте XOR для определения различий, а затем используйте один из этих алгоритмов для подсчета .

Answer 4

Получает разницу в битах между значениями и подсчитывает три бита за раз:

public static int BitDifference(int a, int b) {
   int cnt = 0, bits = a ^ b;
   while (bits != 0) {
      cnt += (0xE994 >> ((bits & 7) << 1)) & 3;
      bits >>= 3;
   }
   return cnt;
}

Answer 5

В Java:

Integer.bitCount(a ^ b)

Answer 6

XOR чисел, тогда проблема становится вопросом подсчета 1 с в результате.

Answer 7

Сравнение выполняется с XOR, как уже отвечали другие.

подсчет может быть выполнен несколькими способами:

• сдвиг влево и сложение.
• поиск в таблице.
• логических формул, которые вы можете найти с помощью карт Карно .