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

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

Пример работы:

Для числа 29 (в двоичной форме 11101):
- На первой итерации, v не имеет значимого бита в диапазоне, определяемом 0xFFFF0000, поэтому ничего не происходит.
- На второй итерации, v не имеет значимого бита в диапазоне, определяемом 0xFF00, поэтому ничего не происходит.
- На третьей итерации, v имеет значимый бит в диапазоне, определяемом 0xF0, поэтому v сдвигается вправо на 4 бита и к результату r добавляется 4.
- На четвертой итерации, v имеет значимый бит в диапазоне, определяемом 0xC, поэтому v сдвигается вправо на 2 бита и к результату r добавляется 2.
- На пятой итерации, v не имеет значимого бита в диапазоне, определяемом 0x2, поэтому ничего не происходит.

Таким образом, для числа 29 (двоичный 11101) результат будет 4.

www.tgoop.com/the_algorithms/4821

4.3K viewsJul 19, 2024 at 12:00

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

Пример работы:

Для числа 29 (в двоичной форме 11101):
- На первой итерации, v не имеет значимого бита в диапазоне, определяемом 0xFFFF0000, поэтому ничего не происходит.
- На второй итерации, v не имеет значимого бита в диапазоне, определяемом 0xFF00, поэтому ничего не происходит.
- На третьей итерации, v имеет значимый бит в диапазоне, определяемом 0xF0, поэтому v сдвигается вправо на 4 бита и к результату r добавляется 4.
- На четвертой итерации, v имеет значимый бит в диапазоне, определяемом 0xC, поэтому v сдвигается вправо на 2 бита и к результату r добавляется 2.
- На пятой итерации, v не имеет значимого бита в диапазоне, определяемом 0x2, поэтому ничего не происходит.

Таким образом, для числа 29 (двоичный 11101) результат будет 4.

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