Одна строка для проверки, имеет ли целое число форму 2 ^ 1-2 ^ j, используя побитовые операторы

Question

Я хочу, чтобы однострочный код проверял, имеет ли данное целое число форму 2 ⁱ - 2 ^j или НЕ. (используя побитовые операторы)

Answer 1

Как говорит АндрейT, ответ можно найти в Восторг Хакера :

Используйте следующую формулу, чтобы отключить самую правую непрерывную строку из 1 бита (например, 01011000⇒ 01000000):

((x | (x – 1)) + 1) & x

Это можно использовать, чтобы увидеть, имеет ли неотрицательное целое число форму 2 ^j - 2 ^k для некоторых j ≥ k ≥ 0;примените формулу с последующим 0-тестом результата.

(обсуждала, стоит ли публиковать это, так как это домашнее задание, но, как уже упоминал AndreyT, и это легко Googlable, думаю, этоболее полезно цитировать непосредственно: я позволю спрашивающему разобраться с этическими последствиями принятия помощи в выполнении домашней работы, и я ожидаю, что, если от этого зависит его ответ, он сам напишет объяснение того, как она работает)

Answer 2

Подсказка или два:

Другие отметили, что вы ищете число, состоящее из последовательности единиц, за которой следует строка из нулей.

Если вы перевернете все биты в этом, вы получите строку 0, за которой следует строка 1. Если вы увеличите это значение, все единичные биты станут нулями, а ровно на один бит выше этих единиц станут единичными.

Если вы и эти два последних вместе, вы получите ноль.

Answer 3

Давайте посмотрим на это на мгновение. Если i = j, то ответ проверяется, чтобы увидеть, является ли целое число 0. В противном случае ключ заключается в том, чтобы увидеть, как часто переключаются биты, которые, как я думаю, вы хотите видеть, являются ли все 1 вместе как группа, вместе Арифметика здесь довольно проста. Если переключатель равен 2, то он имеет такую ​​форму.

Answer 4

Сдвиг влево, пока не получите 0, как только вы получите ноль, вы не должны снова получить 1

Answer 5

В двоичном виде степень двойки - это число вида 100...0 (A 1, за которым следует x 0 s, где x - показатель степени)

Следовательно, любое двоичное число вида 2 ⁱ - 2 ^j будет строкой 1 с, за которой следует строка 0 с.

Windows Calculator (в двоичном режиме) - отличный способ поэкспериментировать с этим.