Как проверить является ли натуральное число степенью двойки в Python
Теперь, взяв and между n и n-1, мы получим все нули в двоичной записи. Для числа, не являющегося степенью двойки, мы не получим настолько "инвертированные" записи. По аналогии с десятичной системой: только отняв от круглого числа вроде 10000 или 1000 единицу, мы получим в результате все девятки.
Проверку на n=0 можно не делать, так как по условию задачи n — натуральное. То есть итоговое решение будет выглядеть как:
Как узнать, является ли число степенью 2? (Побитовый и итеративный) [Python Script]
Как я и обещал, я продолжаю отвечать на ваши вопросы.
Один из читателей myprogrammingblog.com написал мне письмо с вопросом, как узнать, является ли число степенью 2 ? Он также попросил меня написать побитовое решение, а также итеративное решение с использованием Python . В Интернете есть много примеров подобных вопросов, но я подумал, что было бы неплохо поставить их и здесь, так как человек спрашивает.
Итак, первое решение – побитовое .
В этом решении мы будем использовать легендарный побитовый оператор AND (&) . Это решение основано на уникальном свойстве всех чисел степени 2, в которых только один бит установлен в один, а все остальные биты равны нулю. Таким образом, число 1 удалит это одноразрядное выражение, равное нулю, если число является степенью двойки. Вы заметите, что есть особый случай – число! = 0 . Если вы поместите 0 в выражение ниже, вы увидите, что, несмотря на то, что 0 не является степенью двойки, выражение вернет true. Поэтому, чтобы исключить особый случай, я просто убедился, что число не равно нулю.
Вот сама функция:
Второе решение
Второе решение легче понять, если вы не большой поклонник побитовых операций, поскольку оно использует регулярные циклы и основано на свойстве, которое имеет любое число, равное степени двух, – делимое на два без остатка. Таким образом, в этом решении я зацикливаю и делю число на 2, пока число не станет равным 1. Если одно из этих делений покажет мне, что деление произвело остаток, я знаю, что число не является степенью двойки. Я также учитываю особый случай – номер должен быть положительным.
Итак, вот они – 2 решения о том, как найти, является ли число степенью 2 в Python. Я поместил этот код в репозиторий github вместе с модульными тестами. Так что не стесняйтесь использовать его.
Конечно, есть много других решений. Например, вы можете создать массив значений степени 2, отсортированных от наименьшего к наибольшему (диапазон, соответствующий проблеме, которую вы пытаетесь решить), и использовать двоичный поиск, чтобы определить, соответствует ли ваше число одному из этих значений в массиве.
Как определить, является ли число степенью двойки на python3?
Проблема в том, что log(16, 2) # = 4.0 по мнению интерпретатора не является целым числом.
Как можно по другому проверить является ли n степенью двойки?
- Вопрос задан более трёх лет назад
- 23213 просмотров
- Вконтакте
- Вконтакте
- Вконтакте
- Вконтакте
Тебе же в прошлом вопросе разжевали всё, зачем снова плодить глупые вопросы? Но если ты прошлый вопрос спрашивал, чтобы таким образом проверять на степень двойки, то лучше сразу уходи их профессии. Изучи хотя бы основы построения алгоритмов.
Нормальная и быстрая проверка на степень двойки делается через бинарные операции:
Проверить, является ли число степенью 4 или нет
Учитывая положительное число, проверьте, является ли оно степенью четырех или нет.
Подход 1
Простое решение состоит в том, чтобы вычислить log4n на заданный номер n . Если он возвращает целочисленное значение, то мы можем сказать, что число является степенью числа четыре.
Этот подход демонстрируется ниже на C++, Java и Python:
результат:
256 is a power of 4
результат:
256 is a power of 4
Python
результат:
256 is a power of 4
Подход 2
Данный номер n является степенью числа 4, если это степень числа 2, и его единственный установленный бит присутствует в четной позиции (0, 2, 4, …) .
Как проверить степень двойки?
Мы также можем выражение (n & -n) == n чтобы проверить, является ли положительное целое число степенью 2 или нет. Для получения более подробной информации см. эта почта.
Как проверить положение установленного бита?
Чтобы проверить позицию установленного бита, мы можем использовать 0xAAAAAAAA как маска. Маска 0xAAAAAAAA имеет 1 во всех своих нечетных позициях. Итак, если выражение !(n & 0xAAAAAAAA) верно, позиция установленного бита в n даже.
Ниже приведена программа на C++, Java и Python, которая демонстрирует это: