Как проверить, является ли число степенью двойки за O(1)

Решение на Dart.

В JS это выглядит примерно так.

const isIntegerPowerOfTwo = number =>
    number > 0 && (number & (number - 1)) === 0;
Вход в полноэкранный режим Выход из полноэкранного режима

Спасибо Люку Ширу за код.

Объяснение

В двоичном представлении числа состоят из 0 и 1. И так получилось, что все степени двойки равны 10*.
Например, 2 -> 10, 8 -> 1000 и так далее.
Когда мы проводим сравнение числа & число — 1 == 0, мы проверяем 100 & 011, что всегда даст 0.

3 → 11. 3 & 2 => 11 & 10 = 1.

Оцените статью
devanswers.ru
Добавить комментарий