Как узнать, является ли число степенью 2? (Побитовый и итеративный) [Python Script]
[adsense1]
Как я и обещал, я продолжаю отвечать на ваши вопросы.
Один из читателей myprogrammingblog.com написал мне письмо с вопросом, как узнать, является ли число степенью 2 ? Он также попросил меня написать побитовое решение, а также итеративное решение с использованием Python . В Интернете есть много примеров подобных вопросов, но я подумал, что было бы неплохо поставить их и здесь, так как человек спрашивает.
Хорошо, поехали!
Итак, первое решение – побитовое .
В этом решении мы будем использовать легендарный побитовый оператор AND (&) . Это решение основано на уникальном свойстве всех чисел степени 2, в которых только один бит установлен в один, а все остальные биты равны нулю. Таким образом, число 1 удалит это одноразрядное выражение, равное нулю, если число является степенью двойки. Вы заметите, что есть особый случай – число! = 0 . Если вы поместите 0 в выражение ниже, вы увидите, что, несмотря на то, что 0 не является степенью двойки, выражение вернет true. Поэтому, чтобы исключить особый случай, я просто убедился, что число не равно нулю.
Вот сама функция:
# Bitwise version def powTwoBit(number): return (number & (number-1) == 0) and (number != 0)
[adsense1]
Второе решение
Второе решение легче понять, если вы не большой поклонник побитовых операций, поскольку оно использует регулярные циклы и основано на свойстве, которое имеет любое число, равное степени двух, – делимое на два без остатка. Таким образом, в этом решении я зацикливаю и делю число на 2, пока число не станет равным 1. Если одно из этих делений покажет мне, что деление произвело остаток, я знаю, что число не является степенью двойки. Я также учитываю особый случай – номер должен быть положительным.
</div> #Iterative version def powTwoIter(number): isPowOfTwo=True; while (number != 1 and number > 0): if(number%2): # can do return here as well isPowOfTwo = False number=number/2 return isPowOfTwo and (number > 0)
Итак, вот они – 2 решения о том, как найти, является ли число степенью 2 в Python. Я поместил этот код в репозиторий github вместе с модульными тестами. Так что не стесняйтесь использовать его.
Конечно, есть много других решений. Например, вы можете создать массив значений степени 2, отсортированных от наименьшего к наибольшему (диапазон, соответствующий проблеме, которую вы пытаетесь решить), и использовать двоичный поиск, чтобы определить, соответствует ли ваше число одному из этих значений в массиве.
[adsense1]
Выберите то, что работает для вас!