Как узнать, является ли число степенью 2? (Побитовый и итеративный) [Python Script]

Python programming compressed

[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]

Выберите то, что работает для вас!