theJam.ru

Логические задачиЗадача для программистов

6 октября 2008 | Добавил: aleg940

хотя человек со знанием математики и логики тоже способен ее решить.

Как определить, является ли число N целой степенью двойки? (не используя циклы)

Хотите регулярно получать новые задачи и познавательные топики? Подпишитесь на рассылку

Комментариев: 30

  1. gilya пишет:

    так?
    ~(x-1)==0

  2. DaniilKhanin пишет:

    предположу, переводим в двоичную систему, к примеру 8 -> 00000111 далее циклически смещаем вправо это есть деление на два ну и так далее. сразу оговорюсь забыл уже как на асме делять на два :)) умножают смещением влево

  3. gilya пишет:

    а не, я обшибся :)
    надо так:
    (x-1)^x + 1 == 2*x

  4. SusAnna пишет:

    DaniilKhanin, не используя циклы! скажем так, у Вас нет такой функции, как циклический сдвиг.

  5. SusAnna пишет:

    gilya, что-то не то в Вашей формуле:
    (2-1)^2 + 1 ~= 2*2
    (4-1)^4 + 1 ~= 2*4

  6. WeKo пишет:

    я так понимаю через логарифм тоже нельзя, т. к. это слишком просто

  7. SusAnna пишет:

    WeKo, конечно :)

  8. fsv пишет:

    if (x xor (x-1))=(x*2-1) then

  9. fsv пишет:

    или
    if (x and (x-1))=0

  10. Shurick пишет:

    Любая степень двойки в двоичном виде будет иметь в старшем разряде единицу, а во всех остальных, младших, нули.
    Дальше - дело техники))
    Или прям программу написать? ;)

  11. Shurick пишет:

    fsv,
    это больше похоже на определение на четности/нечетности.
    И, не хочу, чтобы меня считали ханжой, но проверка условия без каких-либо последующих действий выглядит как-то странно... В смысле, лучше писать, что же все-таки будет "then"...

    gilya,

    (x-1)^x + 1 == 2*x

    если x=9,
    8^9+1 = 2^9.???
    8^9+1 - даже не четное %)

  12. fsv пишет:

    Shurick, на что бы это не было похоже, свою задачу оно выполняет
    if (x xor (x-1))=(x*2-1) then write (x, ' есть целая степень двойки')

  13. Shurick пишет:

    fsv,
    Объясни, пожалуйста.
    Возьмем, например, число 7 (111).

    x xor (x-1)

    - вот здесь я уже в тупике.
    Как тут сравнивать? Поразрядно (и это без цикла)? 111 и 110?
    Получим 110. Или нет?

    x xor (x-1)

    - это 35 (100011)

    110 100011, 635.

    if (x and (x-1))=0

    Что такое "x" вообще?

  14. Shurick пишет:

    Описка:
    не x xor (x-1), а

    (x*2-1) = 35

  15. WeKo пишет:

    Shurick,
    не используя циклы сможешь ли ты определить где там 1, а где 0

  16. fsv пишет:

    Shurick, x есть N из условия задачи.
    7 xor 6 = 1,
    естественно xor поразрядно сравнивает 111 и 110.
    Другое дело, что я не задумываюсь над представлением числа в двоичной системе, так данные и хранятся :)

  17. Shurick пишет:

    fsv,
    Дошло откуда это)
    (Я-то сперва xor и and как чисто логические операторы воспринял)...
    понятно, 2^x-1 в двоичной системе всегда будет состоять только из "1"...

  18. gilya пишет:

    ^ - это у меня xor
    так что все верно

  19. autodafe пишет:

    а можно сдвинуть на один разряд. Например влево. далее делим N на результат свдига. если получается 2, то число есть степень двойки

  20. SusAnna пишет:

    вообще-то любое четное число при сдвиге влево дает деление на 2

  21. x4m пишет:

    c#
    if ((N-1)&N!=0) throw new Exception("Not a power of two");

    Договоримся, что битовое представление - младьшие разряды справа

    N-1 до первой единицы заменяет все 0 на 1, эту единицу убирает

    если остались ещё единицы - это не степень двойки

  22. x4m пишет:

    в т.ч. 1 является степенью 2

    исключение int.MinValue e.i. 0x80000000

  23. fbd пишет:

    Надо отметить, что для вариантов:

    ((x - 1) & x) != 0
    и
    (a ^ (a - 1)) == ((a << 1) - 1)

    существует исключение - число 0.
    А для первого варианта, в итоге 2 исключения получается.

  24. АнТоНи0 пишет:

    Проще всего с помощью рекурсии=)

  25. Nurlan пишет:

    int N;
    N = 256;

    if ((N & (N - 1)) == 0)
    MessageBox.Show("ok");
    else
    MessageBox.Show("no");

  26. Nurlan пишет:

    C#:

    if ((N & (N - 1)) == 0 && N != 0)
    MessageBox.Show("yes");
    else
    MessageBox.Show("no");

  27. Virtus пишет:

    Вот что сходу пришло в голову (чужие комментарии я читаю после своего ответа, а чаще вообще не читаю).
    Если N степень двойки, то 2 в степени N делится на N, в противном случае не делится (надеюсь это всем понятно, если нет – пишите, поясню). Обе операции выполняются без циклов.

  28. В.С.Ё. пишет:

    Хи) А можно просто перевести в двоичный вид и посмотреть, если там всего одна единица - то число целая степень двойки.

  29. Virtus пишет:

    N степень 2 тогда и только тогда, когда N&(N-1)=0 (& означает логическое "и").
    Реализуется без циклов в любом языке программирования!

  30. Тигран пишет:

    (2^N)/N==0

Комментировать!

Друзья, обращаю ваше внимание, что все бессмысленные и пустые сообщения будут удаляться, ровно как и комментарии с заведомо не существующми e-mail адресами. Спасибо!


Случайное:
ОБЗОР ИГРЫ ASSASIN’S CREED ROGUE
Assassin’s Creed Rogue, последняя на сегодняшний день «полноценная», если так можно сказать, часть и
Полезные советы перед началом прохождения The Witcher 3
Относительно недавно состоялся выход, наверное, одной из самых ожидаемых игр как в жанре RPG, так
История возникновения компьютерных игр
Многие пользователи интересуются феноменом огромной популярности индии - игр, несмотря на то, что мн
Обзор Игры FAR CRY 3
Far Cry 3 – это игра, которая у многих ассоциируется всего лишь с одним словом – «безумие». Мы играе
Какие бывают на данный момент типы компьютерных игр?
Классификация компьютерных игр – это достаточно спорный вопрос, поскольку на данный момент предостав


 
2005-2011 theДжем.ru - сайт для тех, кто умеет читать и думать. ↑ вверх
полезно знать