Нахождение длины общего префикса в двух байтах

Question

Учитывая два байта, как мне найти длину общих бит в начале двух байтов.

Например:

9 == 00001001
6 == 00000110

Common prefix is 0000, length 4

Я работаю в C #,поэтому, пожалуйста, придерживайтесь только операций на C #.

Приложение: этот фрагмент кода будет выполняться тысячи раз и должен быть очень быстрым.

Answer 1

byte x = 9;
byte y = 6;

while ( x != y )
{
    x >>= 1;
    y >>= 1;
}

Как правило, удаляйте бит справа от каждого числа, пока они не станут равными. Когда они становятся равными, их биты тоже равны.

Вы можете легко отслеживать длину префикса, введя другую переменную. Я оставлю это тебе.

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

У вас есть только 2^8 * 2^8 = 2^16 возможностей (на самом деле 2^15, потому что x = 6 и y = 9 совпадают с x = 9 и y = 6). Если вы можете позволить себе начальное время и память, предварительное вычисление должно быть самым быстрым в конце.

Edit:

У вас есть решение, которое, по крайней мере, лучше для предварительного вычисления и, возможно, быстрее в целом: найдите самый левый 1 бит в x ^ y. Используя это, создайте таблицу Pre, где Pre[i] = position of leftmost 1 bit in i. Для этой таблицы вам нужно всего 2 ^ 8 байт.

Answer 2

РЕДАКТИРОВАТЬ: Благодаря комментариям я обнаружил, что я неправильно понял проблему. (Ниже исправлена ​​версия).

С таблицей поиска:

readonly static int[] bytePrefix = new int[] {
    8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
    3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};

И используйте его, XORing два байта:

bytePrefix[9 ^ 6]

Я полагаю, что это настолько быстро, насколько это возможно, это всего лишь одна операция XOR и поиск в массиве (вы также можете изменить его на 2 поиска в массиве, но он будет использовать 256 раз больше памяти и, вероятно, будет медленнее, побитнее это действительно быстро).

Answer 3

Сначала получите двоичную разницу между байтами, используя оператор xor. Затем вы просто сдвигаете биты вправо, пока разница не станет равной нулю:

byte b1 = 6;
byte b2 = 9;

int length = 8;
for (int diff = b1 ^ b2; diff != 0; length--) diff >>= 1;

Это даст вам минимум вычислений в цикле, так что это будет довольно быстро.

Answer 4

Это можно переформулировать как более простую проблему с известным быстрым решением:

• Найти самый левый истинный бит в X ^ Y.

Некоторый код (по-видимому, код не может сразу следовать за маркированным списком?!?)

 int findCommonPrefix(long x, long y, out long common)
 {
    int prefixPlace = 0;
    int testPlace = 32;
    long w, mismatch = x ^ y;
    do {
       w = mismatch >> testPlace;
       if (w != 0) { prefixPlace |= testPlace; mismatch = w; }
       testPlace >>= 1;
    } while (testPlace != 0);
    common = x >> prefixPlace;
    return 64 - prefixPlace;
 }

Для поиска общего префикса в 64-битном коде требуется всего 6 итераций, для байтовой версии потребуется всего 3 итерации.Разверните петлю для еще большей скорости.

Answer 5

Если вы находитесь в ограниченном пространстве (что, очевидно, не так, если вы используете C #, но просто в целом) и не можете позволить себе справочную таблицу:

byte test = byte1 ^ byte2;
int length = 0;
if ((test & 0x80) == 0)
{
    if ((test & 0x40) == 0)
    {
        if ((test & 0x20) == 0)
        {
            if ((test & 0x10) == 0)
            {
                // I think you get the idea by now.
                // Repeat for the lower nibble.
            }
            else
                length = 3;
        }
        else
            length = 2;
    }
    else
        length = 1;
}

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

Answer 6

Вот один без таблицы или цикла:

len =  (a^b) ? (7 - (int)Math.Log( a^b, 2)) : 8;

Объяснение:

log ₂ X - это степень, до которой число 2 должно быть поднято дополучить значение X. Так как каждый бит в двоичном числе представляет следующую степень 2, вы можете использовать этот факт для нахождения наибольшего набора бит (считая от 0):

2**0   = 1 = 0b0001;  log2(1) = 0
2**1   = 2 = 0b0010;  log2(2) = 1
2**1.6 =~3 = 0b0011;  log2(3) =~1.6; (int)log2(3) = 1
2**2   = 4 = 0b0100;  log2(4) = 2
...
2**3   = 8 = 0b1000;  log2(8) = 3

Таким образом, код работает повзяв a XOR b, который устанавливает только разные биты.Если результат не равен нулю, мы используем log2, чтобы найти самый высокий установленный бит.7 меньше результата дает число начальных нулей = количество общих битов.Существует особый случай, когда a XOR b == 0: log2 (0) равен -Infinity, так что это не сработает, но мы знаем, что все биты должны совпадать, поэтому ответ равен 8.

Answer 7

Другой подход, использующий эксклюзив или (xor):

public int GetCommonPrefixLength(byte a, byte b)
{
    int c = a ^ b;
    int len = -1;
    while ((++len < 8) && ((c & 0x80) == 0))
        c = c << 1;
    return len;
}

Answer 8

Вот процедурный способ:

int r = 8;
while (a != b)
{
    a >>= 1;
    b >>= 1;
    r -= 1;
}

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

int[] lookupTable;

void createLookupTable()
{
    lookupTable = new int[256];
    for (int a = 0; a <= 255; ++a)
    {
        int n = 8;
        byte b = (byte)a;
        while (b > 0) {
            b >>= 1;
            n -= 1;
        }
        lookupTable[a] = n;
    }
}

int commonPrefix(byte a, byte b)
{
    return lookupTable[a ^ b];
}

А для развлечения вот способ сделать это сLINQ:

int r = 8 - Enumerable.Range(0, 9).Where(n => a >> n == b >> n).First();

Answer 9

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

/* Assumes table[16] is defined similarly to the table[256] in earlier examples */
unsigned int find_mismatch(unsigned char a, unsigned char b)
{
  unsigned char mismatch;
  mismatch = a^b;
  if (mismatch & 0xF0)
    return table[mismatch >> 4];
  else
    return table[mismatch]+4;
}

Дополнительные инструкции, включая ветвь, но поскольку таблица теперь занимает всего 16 байтов, для полного заполнения потребуется всего один или два пропуска кэша.Другой подход, использующий всего три поиска по 16-байтовой таблице и пятибайтовой таблице, но без разветвления:

unsigned char table2[5] = {0,0,0,0,0xFF};

unsigned int find_mismatch(unsigned char a, unsigned char b)
{
  unsigned char mismatch,temp2;
  mismatch = a^b;
  temp2 = table[mismatch >> 4];
  return temp2 + (table2[temp2] & table[mismatch & 15]);
}

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

Answer 10

int i;
for (i=0;i<sizeof(byte);i++)
    if (a >> sizeof(byte)-i != b >> sizeof(byte)-i) break;