Расстояние между двумя двоичными строками

Question

Есть ли способ эффективно найти (побитовые операции) расстояние (не Hamming Distance!) Двух 8-битных двоичных строк?

У каждого байта гарантированно установлен только один бит.

Как:

a=0 0 0 0 0 0 0 1 
b=0 0 0 1 0 0 0 0 

    0 0 0 1 0 0 0 1 -> distance = 3 
      ^^^^^ 
------ 
a=0 0 0 0 0 1 0 0 
b=0 1 0 0 0 0 0 0 

    0 1 0 0 0 1 0 0 -> distance = 3 
     ^^^^^ 
------ 
a=0 1 0 0 0 0 0 0 
b=0 0 0 0 0 0 1 0 

    0 1 0 0 0 0 1 0 -> distance = 4 
     ^^^^^^^ 

я мог бы работать с чем-то вроде логарифмов, но это не очень эффективно

Answer 1

«Эффективные» может означать разные вещи здесь: например, асимптотические против производительности при известном диапазоне входы; время и пространство; и т. д.

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

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

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

Альтернатива 1. Поместите все расстояния в матрицу поиска. O (1), а O (n^2) - сложность пространства.

Вариант 2. Иметь таблицу поиска для логарифмов, и возвращает журнал разности (а) - журнал (б), где а> = Ь. O (1), сложность времени O (n). (Обратите внимание, что я предполагаю, что dist (a, a) = 0, который является побочным из того, что вы описали выше.)

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

Answer 2

Вы можете использовать операцию OR (логическое суммирование), а затем найти максимальное количество нулей, которое идет один за другим. Надеюсь, я получу ваш вопрос правильно.