Я ищу инновационный способ проверить, имеет ли число только один бит в подписанном 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)
}
return x == (x & -x);
Этот ответ работает из-за того, как была разработана двухкомпонентная нотация.
Во-первых, пример. Предположим, что у нас есть 8-разрядные целые числа.
00010000 = 16
11110000 = -16
Побитовое и даст вам 00010000 в результате, равное исходному значению! Причина, по которой это работает, заключается в том, что при отрицании в 2 дополнениях сначала инвертируйте все биты, затем добавьте 1. У вас будет куча нулей и множество переносов до тех пор, пока один не встанет на свои места. Побитовое и затем проверяет, установлен ли правильный бит.
В случае числа, которое не является степенью двух:
00101010 = 42
& 11010110 = -42
----------
00000010 != 42
У вашего результата будет только один бит, но он не будет соответствовать исходному значению. Поэтому ваше исходное значение имеет несколько бит.
Примечание: Этот метод возвращает true для 0, что может быть или не быть желательным.
Это известная проблема
(x & x-1) == 0
Сила 2 из Wiki: здесь
64 = 01000000 (x)
63 = 00111111 (x-1)
______________
& = 00000000 == 0
______________
Случай, когда некоторые другие биты ВКЛЮЧЕНЫ
18 = 00010010 (x)
17 = 00010001 (x-1)
______________
& = 00010000 != 0
______________
Я бы порекомендовал вам взглянуть на страницу Bit Twiddling Hacks и выбрать наиболее подходящий вариант в разделе " Определение, является ли целое число степенью 2" или " Установлены счетные биты".
return (x && ((x & x-1) == 0))
return (x && (0x8000000000000000ULL % x));
Это упрощение следующего кода:
if (x == 0) {
return false;
} else if (0x8000000000000000ULL % x) {
return false;
} else {
return true;
}
Объяснение: 0x8000000000000000 является самым высоким значением "только 1 бит" для 64-битного регистра. Только разделение другим значением "только 1 бит" не приведет к остатку.
Возьмите журнал на базу 2 вашего номера, если это целое число, ваш номер имеет только 1 бит. Не уверен, что я думаю, что это лучше, чем любой из ваших исключенных вариантов.