level30.lesson08.task01

Самая последняя написанная в JavaRush задача, к сожалению, написана с багом.
Приведу условие:

Найдем число 2 в максимальной степени
Реализуйте логику метода maxPowerOf2,
который должен возвращать число 2 в максимальной степени, которое получается поместить в переданное число
Аргументом maxPowerOf2 может быть только положительное число
Используйте только операции: 1)побитовые сдвиги, 2) присваивание, 3) побитовое ИЛИ
Не оставляйте комментарии

На самом деле, пользуясь ТОЛЬКО этими тремя операциями, решить задачу не представляется возможным.
Это если кратко.


А вообще: моя идея была проста: перебираем степени двойки с максимальной и, если побитовое ИЛИ степени двойки и анализируемого числа даёт анализируемое число, то мы нашли искомую степень.
Вот мой код:

int y = 1 << 30;
      while ((x | y) != x)
         y = y >> 1;

      return y;


Ясное дело, что здесь присутствует как минимум операция НЕРАВНО. Этот код валидатор не принял, чем меня, разумеется не удивил.

Спустя три часа ломания голову об искомый алгоритм, я начал гуглить, а возможно ли это вообще.
Результатом поисков стала вот эта статья, в которой описан и пришедший мне на ум вариант.

Прошу разработчиков изменить тесты или условие.

PS: Задачу пройти возможно, достаточно воспользоваться последним алгоритмом из статьи. Он содержит операцию БОЛЬШЕ ИЛИ РАВНО, но тем не менее проходит проверку.

34 комментария

babayotakun
Если я ошибаюсь, и алгоритм, использующий только три описанные операции существует, буду очень рад его описанию или ссылке.
В любом случае, валидатор принял код, явно неподходящий под условия, что всё равно является багом.
hubert
А попробуй без y, обойтись одним переданным x
babayotakun
  • babayotakun
  • 0
  • Комментарий отредактирован 2014-08-06 14:59:21 пользователем babayotakun
Не спорю, есть ещё один очевидный вариант:
x |= x >> 1;
   x |= x >> 2;
   x |= x >> 4;
   x |= x >> 8;
   x |= x >> 16;
   return x - (x >> 1);

Я и подобный (не точь-в-точь, но почти) код валидатору скармливал, не работает. Да и… Тут есть операция ВЫЧИТАНИЕ же.
GDove
операцию вычитания можно легко заменить на один логический оператор.
silh
Хм, может на 2?
GDove
кокретно в обсуждаемом примере 1. всего их 4, так что выбор не велик =)
silh
Хм, и она попадает в допустимые? 1)побитовые сдвиги, 2) присваивание, 3) побитовое ИЛИ
GDove
it is debatable. как бы да и как бы нет.
silh
& ~ — ты не про них?)
GDove
  • GDove
  • 0
  • Комментарий отредактирован 2014-09-02 16:16:36 пользователем GDove
нет, вот тут =)
HenryJekyll
Почему не принимает?
public static int maxPowerOf2(int x) {
x = x|x>>1;
x = x|x>>2;
x = x|x>>4;
x = x|x>>8;
x = x|x>>16;
return x+1>>>1;
}
hubert
А + к чему относится? Побитовому сдвигу, или присваиванию?
silh
  • silh
  • 0
  • Комментарий отредактирован 2014-08-08 13:26:35 пользователем silh
Ура, прошел, но используется не только |, но и & ~.
ahmoxa
Прошло используя вычитание. Если у кого то вышло решить, используя только
1)побитовые сдвиги, 2) присваивание, 3) побитовое ИЛИ
прошу скинуть в ЛС. Побитовые операции тяжко даются(
pelmewer
В моем случае решение вообще без оператора |, но с операторами & и ~. Было бы любопытно посмотреть решение, удовлетворяющее условию задачи.
nanoezhik
Задача действительно решается без побитового ИЛИ, перечитайте лекцию про приоритет операций (Уровень 21), там даны все операторЫ присвоения.
poxyu
hubert , подскажи, пожалуйста, почему принимает задачу с побитовым отрицанием и побитовым И (& и ~)?

кто-нибудь решил задачу использую только операции из условия? :) поделитесь мыслями
Sequoza
Если кто сможет помочь буду крайне благодарен.
public static int maxPowerOf2(int x)
    {
        if(x>=2)
        {
            x=maxPowerOf2(x>>1);
            return x<<1;
        }
        else
        {
            return 1;
        }
    }

Вроде использовал оператор отношения, даже тот, который юзал топикстартер. Тут ошибка в нём? Если да, то какие можно всё-таки использовать?
pelmewer
Полагаю, что if/else нельзя использовать. У меня их не было.
Sequoza
Благодарю за мгновенный ответ.
Sequoza
Если кому понадобится, задачку можно решить с данными условиями. На мой субъективный взгляд, самая лучшая из всего курса(если не гуглить).
GreenJedi
если бы не кривое условие, то может быть была бы неплохой задачкой, а так получается нужно додумать, что там ещё разрешено использовать =_=
isaenkovl
На 29 уровне есть совет посмотреть методы Integer. Посмотрите… там есть аналогичный метод, можно просто содрать решение)))
kterrita
Спасибо, хотя там и есть операция вычитания :/
PolyMorph
Спс за подсказку. Но правда, там есть операция вычитания, а в условии явно сказано, что кроме тех трех операций использовать другие нельзя! И если можно вычитание, то почему нельзя сложение? И почему тогда такое не проходит:
public static int maxPowerOf2(int x) {
		for(int i = 0; i < 31; i++) {
			x = x | x >> 1;
		}
		return ++x >> 1;
    }
Naissur
Тоже не понимаю. Почему, к примеру, не проходит такой вариант, хотя результат верный:
int result = 2;

        while ((result << 1) <= x) {
            result = result << 1;
        }

        return result;
VitaliyHTC
Есть такой готовый метод. Полезно все таки исходники смотреть.

Как это выглядит в битах :)

100010001011100000
110011001111110000
111111111111111100
111111111111111111
111111111111111111
111111111111111111
111111111111111111
131072

10000000010
11000000011
11110000011
11111111011
11111111111
11111111111
11111111111
1024

10001
11001
11111
11111
11111
11111
11111
16
remain4life
Задачу сдал, используя, помимо указанных в задаче, ещё один побитовый оператор — никак не получается строго по заданию. Если кто-то решил с использованием только указанных операторов по условию — буду очень благодарен за пример в личку!
Medniy
Не понимаю тему с побитовыми операторами. Просто нашел ответ на ОТВЕТ. А как это работает не знаю. Хотелось бы по больше розяснительного материала, задач, примеров по этой теме. Пока что прохожу курс дальше. Потом вернусь к этой теме, так как для меня это вообще не понятно…
tcltk
Спасибо. Тоже, в принципе понимаю, что такое побитовые операции, но высасывать из пальца три часа решение желания никакого нет.
Ognerezov
А мне нравится мое решение, хоть и не проходит.

public static int maxPowerOf2(int x) {

int y=1;
while (x>1){
x=x>>1;
y=y<<1;
}

return y;
}
mainbord
Дам одну подсказку для тех, кто хочет решить сам или понять готовое решение.
К примеру наше число
140_000
В двоичной системе представляется:
100010001011100000
Максимальная степень двойки для этого числа, это наше двоичное число, где слева 1, а все остальное нули
100000000000000000
Теперь нам осталось придумать алгоритм, который без использования циклов, операций сложений и сравнений и прочих только побитовыми операциями сделать из
100010001011100000
это
100000000000000000
и вернуть как десятичное число
paNNo4ka
  • paNNo4ka
  • 0
  • Комментарий отредактирован 2017-01-05 11:58:36 пользователем paNNo4ka
Спасибо, стало яснее.

А из вот этой статьи, про которую говорил автор поста, сейчас проходит проверку ТОЛЬКО второй метод. Хотя все три не совсем подходят под условие:)
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.