Как проверить является ли натуральное число степенью двойки в 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 степенью двойки?
- Вопрос задан более трёх лет назад
- 23197 просмотров
- Вконтакте
- Вконтакте
- Вконтакте
- Вконтакте
Тебе же в прошлом вопросе разжевали всё, зачем снова плодить глупые вопросы? Но если ты прошлый вопрос спрашивал, чтобы таким образом проверять на степень двойки, то лучше сразу уходи их профессии. Изучи хотя бы основы построения алгоритмов.
Нормальная и быстрая проверка на степень двойки делается через бинарные операции:
Проверьте, является ли данное число степенью двойки в Python
Моя идея заключалась в том, чтобы вместо проверки для каждого входа, является ли оно степенью 2, начиная с 1 и умножая на 2 до превышения числа ввода, сравнивая на каждом шаге, я заранее сохраняю все степени 2 в наборе, чтобы проверить заданный вход в O(1). Как это можно улучшить?
12 ответов
Вы специально избегаете библиотек?
Если нет, вы можете использовать math к твоей власти (понял? сила. неважно)
РЕДАКТИРОВАТЬ1: или альтернативно использовать:
Стоит отметить, что для любого n <= 0 те бросят ValueError поскольку это математически не определено (и поэтому не должно представлять логическую проблему).
РЕДАКТИРОВАТЬ 2: Но лучший подход будет использовать битовые манипуляции:
EDIT1: время
Согласно комментарию @FilipHaglund, я вернулся к математическим документам, чтобы попытаться собрать информацию об эффективности. Я узнал, что log метод с заданной базой, фактически вычисляет log(x)/log(base) который, очевидно, медленнее.
Чем я видел, есть другой метод — log2 — который берет только число и, очевидно, вычисляет его логарифм с основанием-2, при этом звуки должны быть быстрее.
В конце я хотел посмотреть, как они соотносятся с бинарным подходом. Итак, результаты:
С помощью log с аргументом base=2 : 2.672359s
С помощью log2 : 2.114203s
Использование бинарного подхода: 1.352385s
Код, который я использовал для этих мер, приведен ниже. Что я в основном сделал, так это проверил все числа от 1 до 1М, являются ли они степенью 2 в каждом методе, 10 раз и взял среднее значение. Конечно, это не научно, но дает представление.
EDIT2: также следует отметить, что для действительно больших чисел (например, 2**100 ) первый log не является точным и фактически дает ложные отрицания.