Скажите, если 32-разрядное число со знаком int является степенью 2

Question

Мне нужно определить, является ли знаковое 32-битное число степенью двойки. До сих пор я знаю, что первое, что нужно сделать, это проверить, не отрицателен ли он, поскольку отрицательные числа не могут быть степенями 2. Затем мне нужно проверить, действительны ли следующие числа и т. Д., Поэтому я смог написать это так:

// Return 1 if x is a power of 2, and return 0 otherwise.
int func(int x)
{
     return ((x != 0) && ((x & (~x + 1)) == x));
}

Но для своего задания я могу использовать только 20 из этих операторов:

! ~ & ^ | + << >>

и НИКАКИЕ операторы равенства или циклы, или приведение, или языковые конструкции.

Итак, я пытаюсь преобразовать части равенства, и я знаю, что! (A ^ b) - это то же самое, что и == b, но я не могу понять это полностью. Любые идеи о том, как преобразовать это в разрешенные операторы?

Answer 1

Попробуйте эти идеи:

• ~!!x+1 дает маску: 0, если x==0, и -1, если x!=0.
• (x&(~x+1))^x дает 0, если x имеет не более 1 установленного бита, и ненулевое значение в противном случае, кроме случаев, когда ~x равен INT_MIN, в этом случае результат не определен ... Возможно, вы могли бы разделить его на несколько частей с помощью битовых смещений, чтобы избежать этого, но тогда я думаю, что вы превысите рабочий предел.
• Вы также хотите проверить знаковый бит, поскольку отрицательные значения не являются степенями двух ...

Кстати, ваш инструктор не знает, что переполнение со знаком является UB в C. Он должен писать эти проблемы для беззнаковых целых чисел. Даже если вы хотите обработать значение семантически, как если бы оно было подписано, вам понадобится арифметика без знака для выполнения значимых побитовых операций, подобных этой.

Answer 2

Комментарий Тима мне стыдно. Позвольте мне попытаться помочь вам найти ответ самостоятельно.

Что означает, что x является степенью 2 с точки зрения битовых манипуляций? Это означает, что только один бит установлен в 1. Как мы можем сделать такой трюк, который превратит этот бит в 0, а некоторые другие, возможно, в 1? Так что & даст 0? В одном выражении? Если вы узнаете - вы выиграете.

Answer 3

Во-первых, в вашем решении это должно быть

return ((x > 0) && ((x & (~x + 1)) == x));

, поскольку отрицательные числа не могут быть степенью 2. В соответствии с вашим требованием нам нужно преобразовать ">", "&&", "== "в разрешенные операторы.

Сначала подумайте о"> ", целом числе> 0, когда его знаковый бит равен 1, а он не равен 0;поэтому мы считаем

~(x >> 31) & (x & ~0)

это выражение, приведенное выше, вернет ненулевое число, если x не является положительным.Обратите внимание, что ~ 0 = -1, что составляет 0x11111111.Мы используем x & ~ 0, чтобы проверить, все ли эти числа равны 0 для каждой цифры.

Во-вторых, мы рассматриваем "&&".AND довольно прост - нам нужно только получить 0x01 и 0x01, чтобы вернуть 1. Так что здесь нам нужно добавить (!!) перед нашим первым ответом, чтобы изменить его на 0x01, если он возвращает ненулевое число.

Наконец, мы рассмотрим "==".Чтобы проверить эквити A и B, нам нужно только сделать

!(A ^ B)

Итак, наконец, у нас есть

return (!!(~(x >> 31) & (x & ~0))) & (!((x&(~x+1)) ^ x))

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

Answer 4

int ispower2(int x)
{

    int ispositive= ! ( (x>>31) ^ 0) & !!(x^0);         
    int temp= !((x & ~x+1) ^ x);
    return temp & ispositive;

}

Answer 5

Подумайте об этом ... любая степень 2 минус 1 - это строка 0, за которой следует строка 1. Вы можете реализовать минус один с помощью x + ~0. Подумайте о том, где строка 1 начинается с отношения 1 к степени 1, равной 2.

Answer 6

Интересно и эффективно использовать побитовые операторы в C для решения некоторых проблем. В этом вопросе нам нужно разобраться с двумя проверками:

1. знак чека. Если отрицательный, верните 0; в противном случае верните 1;

   ! (x >> 31 & ox1) &! (! x)

   / * Это оп. извлекает бит знака в х. Однако >> в этом случае будет арифметическим. Это означает, что перед последним битом (LSB) будет все 1. Для отрицательного значения int это oxFFFFFFFF (-); в противном случае oxFFFFFFFE (+). AND ox1 op. исправляет >> в ox1 (-) или ox0 (+). Логично! превращает ox1 (-) и ox0 (+) в 0 или 1 соответственно. ! (! X) удостоверяется, что 0 не является силой (2) * /

2. Проверка isPower (2). Если да, верните 1; в противном случае 0.

   ! (X & (~ x + ox1) ^ x)

   / * Это оп. делает проверку isPower (2). X & (~ x + ox1) возвращает x тогда и только тогда, когда x - степень (2). Например: x = ox2 и ~ x + ox1 = oxFFFFFFFE. x & (~ x + ox1) = ox2; если x = ox5 и ~ x + ox1 = oxFFFFFFFB. x & (~ x + ox1) = ox1. Следовательно, ox2 ^ ox2 = 0; но ox5 ^ ox1 = ox4. ! op превращает 0 и другие в 1 и 0 соответственно. * /

Последний И соч. от 1 до 2 проверок будет генерировать результат функции isPower (2).