Как определить количество похожих бит?

Question

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

10111000
10111011

184 и 187 требуют смещения в два, потому что отличаются только два младших разряда.

10111011
11111011

187 и 251 требуют смещения в семь, поскольку седьмой младший бит отличается.

Моей первой идеей было скомпоновать числа вместе, затем сдвигать бит вправо, пока число не станет равным нулю. Я чувствую, что есть лучшее побитовое решение для этого, которое не включает петли, но я не сделал достаточно собственных битов, чтобы придумать это.

Решение должно работать для любых 64 битов, так как мои номера хранятся как UInt64. Это написано на C #, но решение, скорее всего, не зависит от языка.

---

11101101
11010101

Требуется смещение 6 бит. Я пытаюсь найти, сколько похожих битов я могу снять с верха.

Answer 1

#include <stdio.h>
#include <stdlib.h>

#define TO_L(s) (strtol((s), NULL, 16))

int tsb(unsigned long xa, unsigned long xb) {
  unsigned long v = xa ^ xb;
  static const unsigned long b[] = {
    0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000L, 0xFFFFffff00000000L
  };
  static const unsigned int S[]  = { 1, 2, 4, 8, 16, 32 };
  unsigned int r = 0;

#define STEP(i)   \
  if(v & b[i]) {  \
    int t = S[i]; \
    v >>= t;      \
    r  |= t;      \
  }
  STEP(5)
  STEP(4)
  STEP(3)
  STEP(2)
  STEP(1)
  STEP(0)
  return r;
}

int main(int ac, char **av) {
  return printf("%d\n", tsb(TO_L(av[1]), TO_L(av[2]))), 0;
}

Я думаю, что это реализует ваш алгоритм, и это очень быстро, всего за 6 шагов.Посмотрите на это отличный источник хищнического хака

Answer 2

Похоже, вы уже заметили главный трюк;r = x XOR y, затем найдите старший бит в r.Существует множество способов решить эту проблему здесь .Самый быстрый делает это в O (n) операциях, разбивая r пополам и проверяя, равна ли верхняя часть нулю.Если вы делаете это с фиксированным числом битов (вы сказали 64), разверните циклы, чтобы получить серию тестов:

pos = 0
r = x XOR y
if r>>32 == 0 :
   r = r & 2^32-1
else
   pos += 32
   r = r>>32
if r>>16 == 0 :
   r = r & 2^16-1
else
   pos += 16
   r = r>16
... etc

Answer 3

Предположим, сначала вы должны сделать это для 8-битных чисел.самый быстрый способ - это 256-байтовая таблица поиска с предварительно скомпилированными значениями:

static unsigned char highest_bit_num_LUT[256] = {0, 1, 2, 2, 3, etc }; // precomputed

unsigned diff = (unsigned)a ^ (unsigned)b; // sure you need XOR and not MINUS?
unsigned highest_bit_num = highest_bit_num_LUT[diff & 0xff];

, теперь расширяющая ее для большего числа битов:

static unsigned char highest_bit_num_LUT[256] = {0, 1, 2, 2, 3, etc }; // precomputed
unsigned diff = (unsigned)a ^ (unsigned)b; // sure you need XOR and not MINUS?
unsigned highest_bit_num = 0;
for (int i = 7; i >= 0; i--)    
    if (diff >> ( i*8) ){ // found most significant non-zero byte
        highest_bit_num = i*8 + highest_bit_num_LUT[diff >> (i*8)];
        break;
    }

, поэтому теперь у нас есть максимум 8 итераций.

РЕДАКТИРОВАТЬ: было бы быстрее использовать идею DigitalRoss для первых 3 итераций, а затем использовать LUT.

Answer 4

Вы можете написать цикл O (log (n)), чтобы довольно легко найти старший установленный бит:

int findHighestSetBit(unsigned long long x) {
    int rv = 0;
    if (x == 0)
        return -1;  // no set bits
    for (int shift = 32; shift > 0; shift >>= 1) {
        if (x >> shift) {
            rv += shift;
            x >>= shift;
        }
    }
    return rv+1; // number least significant bit as '1' rather than '0'
}

если это слишком медленно, вы можете вручную развернуть цикл 5 раз.

Answer 5

Что-то вроде

floor( log(184 ^ 187) / log(2) ) + 1

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

Иногда (хорошо закодированный) цикл выполняется быстрее, чем без цикла , особенно если у вас не более 64 итераций и часто меньше.

<ч /> Более эффективная версия моего кода:

Предварительные вычисления

double Ilog2 = 1 / log(2);

и каждый раз, когда вам это нужно

floor( log(184 ^ 187) * ILog2 ) + 1