Как проверить, что переменная != (степень двойки - 1)

#python

Как написать проверку, что число не является (степенью двойки - 1), не прибегая к
использованию заранее заполненного списка подобных чисел:

f2 = [1,3,7,15]
x = int(input("Задать: "))
if x not in (f2):
    print ("Нет")
else:
    print ("Да")


А как-то с помошью вот этого 

(x != 0) && !(x & (x - 1)


или вот этого

 while (((x % 2) == 0) && x > 1) /* While x is even and > 1 */
   x /= 2;
 return (x == 1);


методов?
    

Ответы

Ответ 1

А так не пойдет?
from math import log
r = log(a+1)/log(2.)
print r!=int(r)


Ответ 2

Ну, буквально на пальцах - нужно было сделать проверку, является ли переменная одним
из начений множества ((степень двойки)- 1). 

Было поздно, меня беспощадно заклинило, и потому не мог сформулировать.
Однако пока читал этот пост - расклинило. Получилось примерно так:

def po2Minus1 ():
    global testvalue
    global limit
    limit = int(input("Enter upper limit: "))
    f = []
    x = range(2, limit)
    for i in (x):
        if (i and i & (i - 1) == 0):
            i = i-1
            f.append(i)
    testvalue = int(input("Enter test value: "))
    if testvalue not in (f):
        print ("The number you entered is not a power of 2 minus 1")
    else:
        print ("The number you entered is a power of 2 minus 1")


Вот. За что всем поучаствовавшим спасибо. Наверняка можно то же самое написать компактней,
только я не знаю как.


Ответ 3

У вас уже в самом вопросе приведена проверка того, является ли число степенью двойки.
Можно немного её модифицировать и получить то, что требуется. Я использовал подобную
схему работы с битами, наверняка её можно улучшить:

def check(x):
    return x ^ (x + 1) == 2 * x + 1


Она основана на том, что в двоичной системе счисления число, равное степени двойки
без единицы, представлено в виде последовательности n единиц: 11...111. Добавив единицу
к этому числу мы получим число, в записи которого будет одна единица и n нулей: 100...000.

Для удобства запишу их друг под другом и сложу их побитово по модулю два:

  11...111 +
 100...000 =
 111...111


Побитовое сложение по модулю два даст в сумме число, равное удвоенному изначальному
числу плюс один только в одном случае -- когда были сложены число, равное степени двойки
и это же число без единицы. Это довольно несложно понять и доказать.

UPD

Добавлю из комментария @VlaD упрощённый вариант:

def check(x):
    return not x & (x + 1)


Он работает ровно по той же причине, что и код выше.


Ответ 4

Стандартный способ определить является ли целое число степенью двойки:

def is_power_two(n):
    assert n >= 0
    return n != 0 and n & (n - 1) == 0


Поэтому чтобы узнать, что переменная является положительной степенью двойки минус
один (n -> n+1):

def is_pos_power_two_minus_one(n):
    assert n >= 0
    return n != 0 and (n + 1) & n == 0


Обратное условие: 

def not_pos_power_two_minus_one(n):
    assert n >= 0
    return n == 0 or (n + 1) & n != 0


Пример:

for n in range(10):
    not_ = "not " * not_pos_power_two_minus_one(n)
    print("{n} {n:04b} is {not_}(2**N - 1)".format(**vars()))


Результат

0 0000 is not (2**N - 1)
1 0001 is (2**N - 1)
2 0010 is not (2**N - 1)
3 0011 is (2**N - 1)
4 0100 is not (2**N - 1)
5 0101 is not (2**N - 1)
6 0110 is not (2**N - 1)
7 0111 is (2**N - 1)
8 1000 is not (2**N - 1)
9 1001 is not (2**N - 1)


Если разрешить N == 0, то 2**0 == 1 и поэтому ноль является "(степень двойки - 1)".
В итоге "переменная != (степень двойки - 1)":

def not_power_two_minus_one(n):
    assert n >= 0
    return (n + 1) & n != 0


что совпадает со вторым решением в ответе @Timofey Bondarev.

Объяснение

Cтепень двойки (2**N) в двоичном представлении это просто единичка c N нулями, например:
2**3 == 0b1000, соответственно "(степень двойки - 1)" (2**N - 1) -- это просто N единичек,
например: 2**3 - 1 == 0b0111. Очевидно, что 2**N & (2**N - 1) == 0 (где N >= 0), например:

    1000
&   0111
    ----
    0000


потому что 0 & 1 == 0, где & это побитовое "и". То есть, если n это степень двойки,
то n & (n - 1) == 0.

Также верно обратное: если n & (n - 1) == 0 для положительного целого числа n, то
n это степень двойки («от противного» можно доказать).

Таким образом, n & (n - 1) == 0 условие является необходимым и достаточным для положительных
целых чисел, чтобы определить, что n -- это степень двойки (2**N).