Как проверить является ли натуральное число степенью двойки в Python
Теперь, взяв and между n и n-1, мы получим все нули в двоичной записи. Для числа, не являющегося степенью двойки, мы не получим настолько "инвертированные" записи. По аналогии с десятичной системой: только отняв от круглого числа вроде 10000 или 1000 единицу, мы получим в результате все девятки.
Проверку на n=0 можно не делать, так как по условию задачи n — натуральное. То есть итоговое решение будет выглядеть как:
Проверьте, является ли данное число степенью двойки в Python
Моя идея состояла в том, чтобы вместо проверки для каждого входа, является ли оно степенью 2, начиная с 1 и умножая на 2 до превышения числа ввода, сравнивая на каждом шаге, я заранее сохраняю все степени 2 в наборе, чтобы проверить заданный вход в O (1). Как это можно улучшить?
3 ответа
Вы специально избегаете библиотек?
Если нет, вы могли бы использовать math для своей власти (понял? Сила . не важно):
EDIT1: или альтернативно используйте:
Стоит отметить, что для любого n <= 0 они будут выбрасывать ValueError , так как он математически не определен (и, следовательно, не должен представлять логической проблемы).
EDIT2: Но лучшим подходом будет использование битовых манипуляций:
Объяснение: каждая степень 2 имеет ровно 1 бит, установленный в 1 (бит в индексе base-2 журнала этого числа — 8 равен 1000 при 2 ^ 3 = 8, поэтому бит в индексе 3 установлен). Таким образом, вычитая из него 1, этот бит переходит на 0, а все предыдущие биты переворачиваются на 1. Это делает эти 2 числа обратными друг другу, поэтому при И-их мы получим 0 в качестве результата. Итак, в заключение, всякий раз, когда мы вычитаем единицу из числа и И с результатом, и это становится 0, это число является степенью 2.
РЕДАКТИРОВАТЬ1: время
Согласно комментарию @FilipHaglund, я вернулся к математические документы, чтобы попытаться собрать информацию об эффективности. Я обнаружил, что метод log с заданной базой фактически вычисляет log(x)/log(base) , что, очевидно, медленнее.
Чем я видел, есть еще один метод — log2 — который берет только число и, очевидно, вычисляет его логарифм по основанию 2, который звучит так, как будто он должен быть быстрее.
В конце я хотел посмотреть, как они соотносятся с бинарным подходом. Итак, результаты:
Использование log с аргументом base=2 : 2.672359 с
Используя log2 : 2.114203 с
Используя бинарный подход: 1.352385s
Код, который я использовал для этих мер, приведен ниже. Что я в основном сделал, так это проверил все числа от 1 до 1М, являются ли они степенью 2 в каждом методе, 10 раз и взял среднее значение. Конечно, это не научно, но дает представление .
EDIT2: также следует отметить, что для действительно больших чисел (например, 2**100 ) первое log не является точным и фактически дает ложноотрицательные результаты.
Надеюсь, вы найдете мое небольшое исследование полезным 🙂
Используйте * 2 вместо битовых сдвигов. Битовые сдвиги ограничены размером int, но умножение — нет. Умножение или сложение гораздо более читабельно.
Обратитесь к превосходному и подробному ответу на вопрос «Как проверить, является ли число степенью 2» — для C #. Эквивалентная реализация Python, также использующая «побитовый оператор» & , это:
Python имеет целые числа произвольной точности, это работает для любого целого числа n , если оно помещается в память.
Кратко резюмируя приведенный выше ответ: первый член перед логическим оператором and просто проверяет, равен ли n 0, и, следовательно, не имеет степень 2. Второе слагаемое проверяет, является ли оно степенью 2, проверяя, чтобы все биты после этой побитовой & операции были равны 0. Битовая операция предназначена только для True для степеней из 2 — с одним исключением: if n (и, следовательно, все его биты) были 0 для начала.
Чтобы добавить к этому: логический << X0>> «короткие замыкания» оценка двух терминов, было бы более эффективно изменить их порядок, если в конкретном случае менее вероятно, что данный n будет 0, чем степень 2.
Как определить, является ли число степенью двойки на python3?
Проблема в том, что log(16, 2) # = 4.0 по мнению интерпретатора не является целым числом.
Как можно по другому проверить является ли n степенью двойки?
- Вопрос задан более трёх лет назад
- 19962 просмотра
- Вконтакте
- Вконтакте
- Вконтакте
- Вконтакте
Тебе же в прошлом вопросе разжевали всё, зачем снова плодить глупые вопросы? Но если ты прошлый вопрос спрашивал, чтобы таким образом проверять на степень двойки, то лучше сразу уходи их профессии. Изучи хотя бы основы построения алгоритмов.
Нормальная и быстрая проверка на степень двойки делается через бинарные операции: