Найти самый высокий установленный бит

Question

У меня есть 5 различных значений, которые сохраняются как биты, например, 10010. Я получаю значение как Int из базы данных (не могу изменить это), так как 24 означает 11000, я знаю, что я могу получить здесь самый большой бит, используя

if ((decbin($d) & 16) == 16)

но если первым будет 0, мне нужно будет проверить следующий бит, а если это 0, мне придется ...

Так что в конце концов у меня будет блок ifsи если бы было больше битов, блок был бы больше.Есть ли простой способ просто получить «id» (или значение, неважно) старшего бита с 1?

Answer 1

Да. Вычислите основание 2 логарифма числа и floor it:

$highbit = floor(log($d, 2));

Если $highbit, например, равно 5, это означает, что 5-й бит является самым старшим битом, установленным в 1.

Answer 2

Наибольший бит, установленный в целом числе, равен целочисленному логарифму base-2 этого целого числа.

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

Функция log (), безусловно, не самый эффективный способ решения проблемы, но если вы видите язык сценариев, это, вероятно, не будет медленнее (и вполне возможно, быстрее), чем реализация одного из «лучших» алгоритмов в PHP с 2 дюжинами операторов.

Таким образом:

$ самое высокое число бит = (int) (срубы ($ значение, 2));

Answer 3

def hibit(v):
    """ uint v -> highest bit: 0101 -> 0100, 01xxxx -> 010000 """
    # cf http://graphics.stanford.edu/~seander/bithacks.html
    v |= v >> 1
    v |= v >> 2
    v |= v >> 4
    v |= v >> 8
    v |= v >> 16
    return v ^ (v >> 1)

for v in range(0, 9+1) + range(2**31-1, 2**31+2):
    print v, hibit(v)

Answer 4

Интересно ... пришлось немедленно проверить наличие проблем с округлением и не найти ни одного в диапазоне до 1 000 000, хотя мой тестовый код выявил проблемы для менее базовых баз, например 3:

3 ^ 5 = 243, но слово (журнал (243, 3)) дает 4