Алгоритмы и структуры данных

Нахождение логарифма по основанию 2 от N-битного числа за O(lg(N)) операций. Метод для процессоров с медленными ветвлениями

Пример работы:
Для числа 19 (в двоичной форме 10011):
- В первой проверке, (v > 0xFFFF) вернет false, так как 19 меньше 0xFFFF (65535), r останется 0.
- Во второй проверке, (v > 0xFF) также вернет false, так как 19 меньше 0xFF (255), r останется 0.
- В третьей проверке, (v > 0xF) вернет true, так как 19 больше 0xF (15), r станет 4 и v сдвинется на 4 вправо, что даст 1 (двоичный 1).
- Далее, (v > 0x3) вернет false, shift останется 0.
- Последняя операция r |= (v >> 1) прибавит 0 к r.

Таким образом, для числа 19 результат будет 4, так как наибольший бит установлен на позиции 4.

www.tgoop.com/the_algorithms/4824

4.3K viewsJul 24, 2024 at 11:35

Нахождение логарифма по основанию 2 от N-битного числа за O(lg(N)) операций. Метод для процессоров с медленными ветвлениями

Пример работы:
Для числа 19 (в двоичной форме 10011):
- В первой проверке, (v > 0xFFFF) вернет false, так как 19 меньше 0xFFFF (65535), r останется 0.
- Во второй проверке, (v > 0xFF) также вернет false, так как 19 меньше 0xFF (255), r останется 0.
- В третьей проверке, (v > 0xF) вернет true, так как 19 больше 0xF (15), r станет 4 и v сдвинется на 4 вправо, что даст 1 (двоичный 1).
- Далее, (v > 0x3) вернет false, shift останется 0.
- Последняя операция r |= (v >> 1) прибавит 0 к r.

Таким образом, для числа 19 результат будет 4, так как наибольший бит установлен на позиции 4.

BY Алгоритмы и структуры данных