предположу, переводим в двоичную систему, к примеру 8 -> 00000111 далее циклически смещаем вправо это есть деление на два ну и так далее. сразу оговорюсь забыл уже как на асме делять на два :)) умножают смещением влево
Любая степень двойки в двоичном виде будет иметь в старшем разряде единицу, а во всех остальных, младших, нули.
Дальше - дело техники))
Или прям программу написать? ;)
fsv,
это больше похоже на определение на четности/нечетности.
И, не хочу, чтобы меня считали ханжой, но проверка условия без каких-либо последующих действий выглядит как-то странно... В смысле, лучше писать, что же все-таки будет "then"...
gilya,
(x-1)^x + 1 == 2*x
если x=9,
8^9+1 = 2^9.???
8^9+1 - даже не четное %)
Shurick, x есть N из условия задачи.
7 xor 6 = 1,
естественно xor поразрядно сравнивает 111 и 110.
Другое дело, что я не задумываюсь над представлением числа в двоичной системе, так данные и хранятся :)
fsv,
Дошло откуда это)
(Я-то сперва xor и and как чисто логические операторы воспринял)...
понятно, 2^x-1 в двоичной системе всегда будет состоять только из "1"...
Вот что сходу пришло в голову (чужие комментарии я читаю после своего ответа, а чаще вообще не читаю).
Если N степень двойки, то 2 в степени N делится на N, в противном случае не делится (надеюсь это всем понятно, если нет – пишите, поясню). Обе операции выполняются без циклов.
6 октября 2008 в 19:43
так?
~(x-1)==0
6 октября 2008 в 23:44
предположу, переводим в двоичную систему, к примеру 8 -> 00000111 далее циклически смещаем вправо это есть деление на два ну и так далее. сразу оговорюсь забыл уже как на асме делять на два :)) умножают смещением влево
7 октября 2008 в 16:17
а не, я обшибся :)
надо так:
(x-1)^x + 1 == 2*x
7 октября 2008 в 17:43
DaniilKhanin, не используя циклы! скажем так, у Вас нет такой функции, как циклический сдвиг.
7 октября 2008 в 18:04
gilya, что-то не то в Вашей формуле:
(2-1)^2 + 1 ~= 2*2
(4-1)^4 + 1 ~= 2*4
7 октября 2008 в 18:20
я так понимаю через логарифм тоже нельзя, т. к. это слишком просто
7 октября 2008 в 18:21
WeKo, конечно :)
7 октября 2008 в 21:06
if (x xor (x-1))=(x*2-1) then7 октября 2008 в 21:13
или
if (x and (x-1))=08 октября 2008 в 10:07
Любая степень двойки в двоичном виде будет иметь в старшем разряде единицу, а во всех остальных, младших, нули.
Дальше - дело техники))
Или прям программу написать? ;)
8 октября 2008 в 10:17
fsv,
это больше похоже на определение на четности/нечетности.
И, не хочу, чтобы меня считали ханжой, но проверка условия без каких-либо последующих действий выглядит как-то странно... В смысле, лучше писать, что же все-таки будет "then"...
gilya,
если x=9,
8^9+1 = 2^9.???
8^9+1 - даже не четное %)
8 октября 2008 в 10:51
Shurick, на что бы это не было похоже, свою задачу оно выполняет
if (x xor (x-1))=(x*2-1) then write (x, ' есть целая степень двойки')8 октября 2008 в 11:25
fsv,
Объясни, пожалуйста.
Возьмем, например, число 7 (111).
- вот здесь я уже в тупике.
Как тут сравнивать? Поразрядно (и это без цикла)? 111 и 110?
Получим 110. Или нет?
- это 35 (100011)
110 100011, 635.
Что такое "x" вообще?
8 октября 2008 в 11:26
Описка:
не x xor (x-1), а
(x*2-1) = 35
8 октября 2008 в 11:31
Shurick,
не используя циклы сможешь ли ты определить где там 1, а где 0
8 октября 2008 в 11:57
Shurick, x есть N из условия задачи.
7 xor 6 = 1,
естественно xor поразрядно сравнивает 111 и 110.
Другое дело, что я не задумываюсь над представлением числа в двоичной системе, так данные и хранятся :)
8 октября 2008 в 14:26
fsv,
Дошло откуда это)
(Я-то сперва xor и and как чисто логические операторы воспринял)...
понятно, 2^x-1 в двоичной системе всегда будет состоять только из "1"...
8 октября 2008 в 14:44
^ - это у меня xor
так что все верно
9 октября 2008 в 20:06
а можно сдвинуть на один разряд. Например влево. далее делим N на результат свдига. если получается 2, то число есть степень двойки
9 октября 2008 в 21:47
вообще-то любое четное число при сдвиге влево дает деление на 2
8 ноября 2008 в 13:43
c#
if ((N-1)&N!=0) throw new Exception("Not a power of two");
Договоримся, что битовое представление - младьшие разряды справа
N-1 до первой единицы заменяет все 0 на 1, эту единицу убирает
если остались ещё единицы - это не степень двойки
8 ноября 2008 в 13:47
в т.ч. 1 является степенью 2
исключение int.MinValue e.i. 0x80000000
5 октября 2009 в 16:09
Надо отметить, что для вариантов:
((x - 1) & x) != 0
и
(a ^ (a - 1)) == ((a << 1) - 1)
существует исключение - число 0.
А для первого варианта, в итоге 2 исключения получается.
13 февраля 2010 в 10:07
Проще всего с помощью рекурсии=)
13 января 2011 в 11:39
int N;
N = 256;
if ((N & (N - 1)) == 0)
MessageBox.Show("ok");
else
MessageBox.Show("no");
13 января 2011 в 11:44
C#:
if ((N & (N - 1)) == 0 && N != 0)
MessageBox.Show("yes");
else
MessageBox.Show("no");
7 июня 2011 в 00:43
Вот что сходу пришло в голову (чужие комментарии я читаю после своего ответа, а чаще вообще не читаю).
Если N степень двойки, то 2 в степени N делится на N, в противном случае не делится (надеюсь это всем понятно, если нет – пишите, поясню). Обе операции выполняются без циклов.
1 января 2012 в 03:15
Хи) А можно просто перевести в двоичный вид и посмотреть, если там всего одна единица - то число целая степень двойки.