|
Название: Степень двойки Отправлено: fortpost от Апрель 02, 2012, 23:43:00 Как определить, является ли целое положительное число n целой степенью двойки, не используя циклы?
Название: Re: Степень двойки Отправлено: moonlight от Апрель 03, 2012, 00:54:33 Код: bool Pow2(int n) Название: Re: Степень двойки Отправлено: iPhonograph от Апрель 03, 2012, 08:07:42 посмотреть на логарифм
Название: Re: Степень двойки Отправлено: Вилли ☂ от Апрель 03, 2012, 09:37:20 в двоичном коде выглядетъ как 1000...000
Название: Re: Степень двойки Отправлено: fortpost от Апрель 03, 2012, 10:03:07 Код: bool Pow2(int n) Название: Re: Степень двойки Отправлено: fortpost от Апрель 03, 2012, 10:05:43 посмотреть на логарифм Та нема ж двоичных логарифмов в ЯПах, тока натуральные, а тогда погрешность может вылезть.Название: Re: Степень двойки Отправлено: fortpost от Апрель 03, 2012, 10:07:05 в двоичном коде выглядетъ как 1000...000 Да, а дальше что с этим делать?Название: Re: Степень двойки Отправлено: Ivan A. Kosarev от Апрель 03, 2012, 10:46:21 Степень двойки в двоичном представлении -- это единственный взведенный разряд в какой-либо позиции. Если в двоичном представлении степени двойки единственный взведенный разряд имеет позицию b, тогда у числа на единицу меньшего этой степени двойки все разряды младше b будут взведены, а все остальные, включая разряд в позиции b, сброшены. Значит, степень двойки -- это число, которое не равно нулю и не имеет общих взведенных разрядов с числом, на единицу меньшим этой степени двойки.
Код: int is_power_of_two(unsigned n) Название: Re: Степень двойки Отправлено: Вилли ☂ от Апрель 03, 2012, 10:48:39 * меняем первую единичку на нолик (или отбрасываем его) и число сравниваем с 0
* узнаём кол-во бит числа и сравниваем с соответствующей степенью двойки * вычитаем единичку -> кол-во бит числа уменьшилось на один (1000 -> 0111) * побитовый сдвиг влево/вправо и сравнение с исходным числом Название: Re: Степень двойки Отправлено: Вилли ☂ от Апрель 03, 2012, 11:08:59 -
Название: Re: Степень двойки Отправлено: kinder от Апрель 03, 2012, 12:24:10 ну вы даёте :)
return !(n&1); Название: Re: Степень двойки Отправлено: Ivan A. Kosarev от Апрель 03, 2012, 12:26:05 ну вы даёте :) return !(n&1); Это проверка на четность. :) Название: Re: Степень двойки Отправлено: fortpost от Апрель 04, 2012, 00:17:43 А можно так. Если 2n делится на n, то n является степенью двойки, если не делится, то не является.
|