Как найти самый левый бит числа в одной строке

Question

Как узнать самый левый и самый правый бит числа в одной строке кода?

Что ж, мы можем пройти по циклу, чтобы определить левую установленную битную комбинацию, но как сделать это в одной строке, чтобы сделать другую нет. чей самый левый / самый правый бит установлен? Например, y = x & ~ (x-1) найдет самый левый бит, но я не понял, как это сделать?

Может кто-нибудь дать код для этого в C ++ и объяснить?

Answer 1

Для самого правого бита есть хорошо известный трюк.

x=x & -x

удалит все установленные биты в x, кроме самого левого. Вы найдете много объяснений, почему это работает в SO (см., Например, этот ответ )

Чтобы найти его индекс, кроме как с помощью встроенных языков программирования, нет никакого способа, кроме как сделать цикл AFAIK. Обратите внимание, что этот цикл можно развернуть, чтобы иметь один вкладыш.

pos = (16*(x&0xffff0000)!=0) + (8*(x&0xff00ff00)!=0) + (4&(x&0xf0f0f0f0)!=0) + (2*(x&0x66666666)!=0)+(x&0xaaaaaaaa)!=0)

x - результат предыдущей операции (т. Е. Установлен только самый правый бит), и он работает путем тестирования, если этот бит находится в верхней половине слова, и в этом случае позиция будет> 16, затем четный байт, четный клев и т. д.

Другим решением является использование математического оператора log2

pos=(int)log2((double)x)

Для самого левого бита, AFAIK, нет способа сделать это на уровне битов, кроме как через циклы. Но можно использовать log2 (), чтобы найти позицию самого левого бита.

Затем, чтобы вернуть int только с этим установленным битом, можно использовать сдвиги вправо.

x = 1 << ((int) log2((double)x))

Это сохранит только самый левый бит в x.

Остерегайтесь предварительно проверить, не является ли x ненулевым.