Шон Андерсон опубликовал немного вертел хаки , содержащие алгоритм Эрика Коула , чтобы найти А.Н. -разрядного целочисленного в операций с умножения и поиска.N v O ( lg ( N ) )
Алгоритм опирается на «магическое» число из последовательности де Брюина. Кто-нибудь может объяснить основные математические свойства последовательности, используемой здесь?
uint32_t v; // find the log base 2 of 32-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
v |= v >> 1; // first round down to one less than a power of 2
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];
nt.number-theory
comp-number-theory
Юрий Байда
источник
источник
Ответы:
Прежде всего обратите внимание, что этот алгоритм вычисляет только , и, поскольку код написан, он работает только для которые вписываются в битное слово.v 32⌈log2v⌉ v 32
Последовательность сдвигов и или-s, которая появляется первой, имеет функцию распространения первого 1 бита до самого младшего бита. Численно это дает вам .2 ⌈ log 2 v ⌉ - 1v 2⌈log2v⌉−1
Интересная часть - трюк де Брейна, который взят из этой статьи Лейзерсона, Прокопа и Рэндалла (по-видимому, профессора MIT проводят время, занимаясь немного хаки :)). Что вам нужно знать о последовательностях де Брюина, так это то, что они представляют все возможные последовательности заданной длины таким образом, чтобы это было как можно более сжато. Точно, последовательность де Брейна над алфавитом является двоичной строкой длиной такой, что каждая двоичная строка длины появляется ровно один раз в виде непрерывной подстроки (допускается перенос). Причина, по которой это полезно, состоит в том, что если у вас есть число , битовое представление которого представляет собой последовательность де Брюина (дополненнуюs 2 k k X k k 2 i X i i < k{0,1} s 2k k X k нулями), то старшие битов однозначно идентифицируют (до тех пор, пока ).k 2iX i i<k
источник
Некоторые комментарии (не совсем ответ). Давайте классифицируем 32-битные целые числа следующим образом:c
Тип X: (в виде двоичной строки) является последовательностью Де Брейна (для всех вращений биты [27,31] различны). Пример:c
Тип Y: биты [27,31] из различны для . Это то, что Leiserson et al. использование. Примеры:я = 0 , 1 , . , , , 312i⋅c i=0,1,...,31
Тип Z: биты [27,31] из различны для . Это то, что нам нужно в исходном вопросе. Примеры:я = 0 , 1 , . , , , 31(2i+1−1)⋅c i=0,1,...,31
Некоторые наблюдения, основанные на быстрых экспериментах (надеюсь, я понял это правильно):
Есть 65536 целых чисел типа X.
Есть 4096 целых чисел типа X + Y. Это именно те целые числа типа X, которые начинаются с последовательности '0000 ...'
Есть 256 целых чисел типа X + Y + Z. Это именно те целые числа типа X, которые начинаются с последовательности «0000011111 ...»
Все целые числа типа Y также имеют тип X.
Однако есть также 768 целых чисел типа Z, которые не относятся ни к типу X, ни к типу Y. Они начинаются с '1000011111 ...', '0111100000 ...' или '1111100000 ...'
источник
Эта особая константа представляет собой последовательность де Брюина с двоичным алфавитом, но с дополнительным свойством. Я назову это «Свойством Марка Дикинсона», поскольку оригинальный алгоритм может быть реализован без этих специальных последовательностей БД. Добавив 2 дополнительные операции, мы можем использовать любую обычную последовательность БД. Операция: v ^ = (v >> 1); // clr все биты, кроме MSB, установленного после каскадного или сдвига.
Если вы надеялись на изящную математическую формулу для их описания или теорему для их создания или что-то подобное, я думаю, что это потребовало бы глубокого понимания теории чисел и, возможно, других областей, которые выходят за рамки моих навыков. Если бы я мог сделать дикое предположение, я бы поспорил, что они могут быть произведены клеточными автоматами. Это не ответ почему? на строгой основе, но попытка интуитивно понять, почему он работает и почему он работает правильно, так что вы можете использовать его с уверенностью.
источник