Используя побитовую обработку, чтобы сказать, может ли целое число без знака быть выражено в форме 2^n-1
Протестировать, если целое число без знака имеет форму 2^n-1 мы используем:
x&(x+1)
Чему это, как предполагается, равняется? Таким образом,
x&(x+1) == ?
3 ответа
В дополнение к существующим ответам, вот краткое объяснение того, почему числа x не имеют формы 0b00000 (ноль) или 0b0111..11 (набор всех младших цифр, это все числа 2 ^ n-1 для n> 0) не имеют свойства x & (x + 1) == 0 .
Для числа x вида 0b ???? 1000..00 , x + 1 имеет те же цифры, что и x за исключением младшего значащего бита, поэтому x & (x + 1) имеет хотя бы один установленный бит, бит, который был отображен как установленный в x . В качестве более короткого пояснения:
x 0b????1000..00
x+1 0b????1000..01
x&(x+1) 0b????10000000
Для числа x вида 0b ???? 10111..11 :
x 0b????10111..11
x+1 0b????110000000
x&(x+1) 0b????10000..00
В заключение, если x не является ни нулем, ни записывается в двоичном формате с установленными младшими цифрами, тогда x & (x + 1) не равно нулю.
Ноль. Если X равно 2^N-1, то это непрерывная строка из 1 в двоичном исчислении. Еще одно большее число - это 1, за которой следует строка нулей той же длины, что и X, поэтому у этих двух чисел нет общих битов 1 в любом месте, поэтому И двух чисел равно нулю.
Число вида 2 ^ n-1 будет иметь все биты до n-го бита. Например, 2 ^ 3-1 (7) это:
0b0111
Если мы добавим к этому единицу, мы получим 8:
0b1000
Затем, выполняя побитовое и, мы видим, что получаем ноль, потому что в обоих числах бит не установлен. Если мы начнем с числа не вида 2 ^ n + 1 , то результат будет отличным от нуля.