Установить все биты до заданного старшего бита

Если у меня есть двоичное число, скажем, x = 00010000, я могу установить все биты до самого высокого и только установленного бита, выполнив y = x | (x - 1), что приведет к y = 00011111.

Как я могу добиться того же результата, если установлено несколько битов, например. x = 00010101?


bit-manipulation twos-complement
person Felix Dombek    schedule 13.08.2014    source источник
comment
Задача эквивалентна поиску старшего установленного бита.   -  person Sergey Kalinichenko    schedule 13.08.2014
comment
stackoverflow.com/questions/53161 // stackoverflow.com/questions/671815/ stackoverflow.com/questions/2589096/ ...   -  person phuclv    schedule 13.08.2014

Ответы (1)


arrow_upward
1
arrow_downward

Это найти первую задачу

Нет возможного решения только с побитовыми операциями. Если вы хотите закодировать его обычным способом, подумайте о «бинарном поиске» для более эффективных алгоритмов.

Вот кое-что для начала, но я уверен, что есть более эффективные алгоритмы.

int findfirstset(unsigned int x) {
    x |= (x >>  1);
    x |= (x >>  2);
    x |= (x >>  4);
    x |= (x >>  8);
    x |= (x >> 16);
    return x - (x >> 1);
}

Оттуда вы можете выполнить свою операцию:

y = x | (x - 1)
person Ajk_P    schedule 13.08.2014
comment
Зачем возиться с x - (x >> 1) и y = x | (x - 1)? После x |= (x >> 16); у вас уже есть результат, желаемый OP. - person Apriori; 14.08.2014