Как проверить, является ли число мощностью 2

Question

Как проверить, является ли число мощностью 2

Сегодня мне нужен простой алгоритм для проверки того, является ли число силой ulong.

Алгоритм должен быть:

просто
Правильно для любого значения.private bool IsPowerOfTwo(ulong number) { if (number == 0) return false; for (ulong power = 1; power > 0; power = power << 1) { // This for loop used shifting for powers of 2, meaning // that the value will become 0 after the last shift // (from binary 1000...0000 to 0000...0000) then, the 'for' // loop will break out. if (power == number) return true; if (power > number) return false; } return false; }

Я придумал этот простой алгоритм:

log₂ x

Но потом я подумал, как насчет проверки, Math.Logявляется ли точно круглый номер? Но когда я проверил 2 ^ 63 + 1, doubleвернул ровно 63 из-за округления. Поэтому я проверил, соответствует ли 2 мощности 63 исходному числу, и это потому, что вычисление выполняется в s, а не в точном числе:private bool IsPowerOfTwo_2(ulong number) { double log = Math.Log(number, 2); double pow = Math.Pow(2, Math.Round(log)); return pow == number; }

true

Возвращаемый 9223372036854775809для данного неправильного значения: .bool IsPowerOfTwo(ulong x) { return (x & (x - 1)) == 0; }

Есть ли лучший алгоритм?

c#,algorithm,math,

487

Ответов: 21

C #, алгоритм, математика,

Похожие вопросы

score 1046 · Answer 1

1046 ов принято

Для этого есть простой трюк:

Обратите внимание, что эта функция будет отчитываться 2за 0, что не сила 2. Если вы хотите исключить это, вот как это сделать:

bool IsPowerOfTwo(ulong x)
{
    return (x != 0) && ((x & (x - 1)) == 0);
}

объяснение

Прежде всего побитовое двоичное bool b = оператор IsPowerOfTwo ( 4 ) из определения MSDN:

Бинарные и операторы предопределены для интегральных типов и bool. Для интегральных типов & вычисляет логическое побитовое И его операндов. Для операндов bool и вычисляет логический AND своих операндов; то есть результатом является возврат ( 4 ! = 0 ) && (( 4 & ( 4 - 1 )) == 0 ); тогда и только тогда, когда оба операнда верны.

Теперь давайте посмотрим, как все это происходит:

Функция возвращает boolean (true / false) и принимает один входящий параметр типа unsigned long (x, в этом случае). Для простоты предположим, что кто-то прошел значение 4 и назвал функцию так:

((4 & (4-1)) == 0)

Теперь мы заменяем каждое вхождение x на 4:

((4 & 3) == 0)

Ну, мы уже знаем, что 4! = 0 оценивает истину, пока что так хорошо. Но что насчет:

4&3

Это, конечно же, означает:

100 = 4
011 = 3

Но что конкретно &?

Бинарное представление 4 равно 100, а двоичное представление 3 равно 011 (помните, что & берет двоичное представление этих чисел). Таким образом, мы имеем:

1 & 1 = 1

Представьте, что эти значения сложены как элементарное дополнение. &Оператор говорит , что , если оба значения равны 1 , то результат будет 1, в противном случае он равен 0. Таким образом 1 & 0 = 0, 0 & 0 = 0, 0 & 1 = 0и . Итак, мы делаем математику:100 011 ---- 000

return (4 != 0) && ((4 & 3) == 0);

Результат - просто 0. Итак, мы вернемся и посмотрим, что теперь означает наш оператор return:

return true && (0 == 0);

Это переводит теперь:

return true && true;

true && true

Мы все знаем, что trueэто просто true, и это показывает, что для нашего примера 4 является степенью 2.

score 88 · Answer 2

88

Некоторые сайты, которые документируют и объясняют это и другие биты,

http://graphics.stanford.edu/~seander/bithacks.html
( http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 )
http://bits.stephan-brumme.com/
( http://bits.stephan-brumme.com/isPowerOfTwo.html )

И дедушка из них, книга «Хакерское наслаждение» Генри Уоррена-младшего :

http://www.hackersdelight.org/

Как объясняет страница Шона Андерсона , выражение ((x & (x - 1)) == 0)неправильно указывает, что 0 - это сила 2. Он предлагает использовать:

(!(x & (x - 1)) && x)

чтобы исправить эту проблему.

score 38 · Answer 3

38 ов

return (i & -i) == i

score 20 · Answer 4

20

Я недавно написал статью об этом в http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/ . Он охватывает подсчет бит, правильное использование логарифмов, классическую проверку «x &&! (X & (x - 1))» и другие.

score 19 · Answer 5

19 ов

bool IsPowerOfTwo(ulong x)
{
    return x > 0 && (x & (x - 1)) == 0;
}