Получить длину битов, используемых в int

Если у вас есть двоичное число 10110, как я могу заставить его возвращать 11111? например, новое двоичное число, которое устанавливает все биты в 1 после первого 1, есть несколько аналогичных примеров, перечисленных ниже:

101 должен возвращать 111 (длина 3 бита) 011 должен возвращать 11 (длина 2 бита) 11100 должен возвращать 11111 (длина 5 битов) 101010101 должен возвращать 111111111 (длина 9 битов)

Как это можно получить самым простым способом в Java? Я мог бы придумать несколько методов, но они не очень "красивы".


java binary int bit-manipulation
person sigvardsen    schedule 23.05.2010    source источник
comment
Все это здесь: graphics.stanford.edu/~seander/bithacks.html   -  person President James K. Polk    schedule 23.05.2010

Ответы (4)


arrow_upward
7
arrow_downward

Вы можете использовать этот код:

int setBits (int value)
{
    value |= (value >> 1);
    value |= (value >> 2);
    value |= (value >> 4);
    value |= (value >> 8);
    value |= (value >> 16);
    return value;
}

Идея состоит в том, что крайняя левая единица будет скопирована во все позиции справа.

РЕДАКТИРОВАТЬ: Также отлично работает с отрицательным value. Если вы замените int на long, добавьте один дополнительный оператор |=: value |= (value >> 32). Как правило, последний сдвиг должен быть степенью двойки, которая составляет не менее половины размера value в битах.

person doublep    schedule 23.05.2010
comment
Что особенно приятно в этом алгоритме, так это то, что он повторно использует предыдущие операции. Наивно я бы просто сделал 32 смены. - person Johannes Schaub - litb; 23.05.2010
comment
Если вы посмотрите на реализацию Integer#highestOneBit() в JDK, вы увидите тот же алгоритм, хотя последний шаг предназначен для доставки только одного бита, что требует отмены, зафиксированной в ответе hleinone. - person seh; 23.05.2010

arrow_upward
12
arrow_downward

Моя попытка: Integer.highestOneBit(b) * 2 - 1< /а>

person hleinone    schedule 23.05.2010
comment
Для полноты: java. sun.com/j2se/1.5.0/docs/api/java/lang/ - person Eric; 23.05.2010
comment
Хммм.. Похоже, я не могу опубликовать ссылку. SO не любит скобки. - person Eric; 23.05.2010
comment
Вау, я понятия не имел, что в Java есть эта функция ... здесь это определенно самое элегантное. - person Amadan; 23.05.2010

arrow_upward
6
arrow_downward

Не проверял, но что-то вроде этого должно быть в порядке:

long setBits(long number) {
  long n = 1;
  while (n <= number) n <<= 1;
  return n - 1;
}
person Amadan    schedule 23.05.2010
comment
Это не сработает, если number отрицательное. Это будет быстро, если number обычно мало, но медленно, если number примерно равномерно распределено по всему диапазону. - person doublep; 23.05.2010
comment
Правда о минусах, я об этом не подумал. И в среднем было бы быстрее, если бы я начал с другого конца. Но 63 итерации (максимум) не так уж и медленны; а ответ вылетел из головы. Очевидно, раствор глейнона выдувает его из воды... :) - person Amadan; 23.05.2010

arrow_upward
0
arrow_downward

Не самый эффективный, но самый простой,

    int i = (1 << (int)(Math.log(n)/Math.log(2)+1)) - 1;

Он будет работать для первых 31 бит int и первых 63 бит для long.

person ZZ Coder    schedule 23.05.2010