Инновационный способ проверки того, имеет ли номер только один бит в подписанном int

Я ищу инновационный способ проверить, имеет ли число только один бит в подписанном int.

Мне хорошо известно, что я могу просто сделать цикл с помощью счетчика, некоторое модульное деление и бит-сдвиг. Но мне любопытно, есть ли лучший способ, поскольку мы только ищем бит ONE для включения.

bool HasOnlyOneBit (int  numb)
{
   //return true if numb has only one bit (I.E. is equal to 1, 2, 4, 8, 16... Int.MinValue)
}

Ответы

Ответ 1

return x == (x & -x);

Этот ответ работает из-за того, как была разработана двухкомпонентная нотация.

Во-первых, пример. Предположим, что у нас есть 8-разрядные целые числа.

00010000  =  16
11110000  = -16

Побитовое и даст вам 00010000 в результате, равное исходному значению! Причина, по которой это работает, заключается в том, что при отрицании в 2 дополнениях сначала инвертируйте все биты, затем добавьте 1. У вас будет куча нулей и множество переносов до тех пор, пока один не встанет на свои места. Побитовое и затем проверяет, установлен ли правильный бит.

В случае числа, которое не является степенью двух:

  00101010  =  42
& 11010110  = -42
----------
  00000010 !=  42

У вашего результата будет только один бит, но он не будет соответствовать исходному значению. Поэтому ваше исходное значение имеет несколько бит.

Примечание: Этот метод возвращает true для 0, что может быть или не быть желательным.

Ответ 2

Это известная проблема

(x & x-1) == 0

Сила 2 из Wiki: здесь

64 = 01000000 (x)
63 = 00111111 (x-1)
______________
&  = 00000000  == 0
______________

Случай, когда некоторые другие биты ВКЛЮЧЕНЫ

18 = 00010010 (x)
17 = 00010001 (x-1)
______________
&  = 00010000  != 0
______________

Ответ 3

Я бы порекомендовал вам взглянуть на страницу Bit Twiddling Hacks и выбрать наиболее подходящий вариант в разделе " Определение, является ли целое число степенью 2" или " Установлены счетные биты".

Ответ 4

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

Ответ 5

return (x && (0x8000000000000000ULL % x));

Это упрощение следующего кода:

if (x == 0) {
    return false;
} else if (0x8000000000000000ULL % x) {
    return false;
} else {
    return true;
}

Объяснение: 0x8000000000000000 является самым высоким значением "только 1 бит" для 64-битного регистра. Только разделение другим значением "только 1 бит" не приведет к остатку.

Ответ 6

Возьмите журнал на базу 2 вашего номера, если это целое число, ваш номер имеет только 1 бит. Не уверен, что я думаю, что это лучше, чем любой из ваших исключенных вариантов.