теперь всё чётенько. как и должно было быть.

сегодняшняя задача. объясните, почему (5, 7) должен дать 4? 5 & 7 == 5

а, я понял

ух. классная задачка.

напечатался в консоли двоичное представление чисел в разных диапазонах

прежде чем увидеть прикол

я решил в лоб с одной лишь оптимизацией — прошло

мне кажется, что я так же сделал. с той же самой оптимизацией.

скажем так, когда нуля не избежать 😂

да)

теперь смотрю чужие решения — там прямо огонь

Хорошая задача. Немного подумать пришлось

Согласен, мне тоже понравилась)

И не сильно обременяет и есть удовольствие от решения

А кто как решил? Я с помощью логарифма и сдвига

Аналогично)

https://leetcode.com/problems/bitwise-and-of-numbers-range/discuss/593506/C-elementary-bitwise-O(1)-solution

Не ну тут что-то слишком красиво у тебя)

А у тебя как?)

а зачем тут нужен логарифм?

Теперь не хочу показывать)

сейчас

а зачем тут нужен логарифм?

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

И это значит, что в этом диапазоне у чисел точно будут меняться биты

И битовое И даст 0

Да, потому что если сделать & для чисел, чьё битовое представление требует на бит больше получится 0

у меня вышло так https://github.com/vtambourine/leetcode-go/blob/master/0201.bitwise_and_of_numbers_range/bitwise_and_of_numbers_range.go

А как вы кодом делитесь?

С лииткода?

я просто комичу решения в свой репозиторий

Пишу там пост в Discuss

или что-то другое имеешь ввиду?

Ну да, я вижу что у тебя гитхаб, тут понятно) Я удивился что Клён поделился. Но теперь понял, спасибо

у меня вышло так https://github.com/vtambourine/leetcode-go/blob/master/0201.bitwise_and_of_numbers_range/bitwise_and_of_numbers_range.go

Я не рискнул брутить)

Показалось, что по времени не пройдет

я решил в лоб с одной лишь оптимизацией — прошло

Так

Там можно брутфорсом?

Кто нить пробовал?

Да

Выше

Там или O(N) или O(1) как я понял

Ну да

https://pastebin.com/NERYLZzA

Я так написал. Просто не знал как это более красиво оформить

Но как я понимаю, Клён, у тебя точно такое же решение?

У меня нет цикла

Этот цикл срабатывает очень редко)

Только если m и n в одинаковом диапазоне степеней. Во всех остальных случаях 0(1).

При len 0 можно n & m убрать, например. Просто число вернуть

А что ифе делается?

где на нули проверяешь

Кто нить пробовал?

вот такой брутфорс у меня прошел: func rangeBitwiseAnd(m int, n int) int { ans := m for m < n { if ans == 0 { return 0 } m++ ans &= m } return ans }

собственно, после этого решения я уже стал дулмать, как решить быстрее

Вычисляется степень двойки последнего числа и первого. Просто при переходе на один разряд больше происходит обнуление. Например 7 - 111 а 8 - 1000. 0111 & 1000 = 0000 и дальше нет смысла проверять так как всегда будет 0

Ну и значит если последнее число хотя бы на разряд больше первого - значит нет смысла цикл запускать

рано или поздно превратится в 0

А, ну да. Та же идея, просто по другому)

То то я думал, чего так много нулей получается. При тестах

Да) Сразу на мысли и наводит

вот такой брутфорс у меня прошел: func rangeBitwiseAnd(m int, n int) int { ans := m for m < n { if ans == 0 { return 0 } m++ ans &= m } return ans }

о, это прямо прикольно 👍 и не надо ничего проверять заранее.

А у меня так не прошло

Причём последний кейс

https://leetcode.com/problems/bitwise-and-of-numbers-range/discuss/593506/C-elementary-bitwise-O(1)-solution

это вообще огонь.

Да) Сразу на мысли и наводит

https://leetcode.com/problems/bitwise-and-of-numbers-range/discuss/593239/Easy-python-with-explanation-(100-memory)

вот похоже на твоё, вроде

Я без логарифма проверку делал такую: n >= 2 * m – если больше чем в два раза значит одна степень двойки лежит между n и m. Единственно это может дать переполнение, поэтому несложное алгебраическое преобразование даёт ту же проверку n - m >= m.

вот похоже на твоё, вроде

Ого, да) Только гораздо элегантней)

В остальном брутфорсик вышел на коротком интервале.

Я без логарифма проверку делал такую: n >= 2 * m – если больше чем в два раза значит одна степень двойки лежит между n и m. Единственно это может дать переполнение, поэтому несложное алгебраическое преобразование даёт ту же проверку n - m >= m.

Действительно, так проще!

Я без логарифма проверку делал такую: n >= 2 * m – если больше чем в два раза значит одна степень двойки лежит между n и m. Единственно это может дать переполнение, поэтому несложное алгебраическое преобразование даёт ту же проверку n - m >= m.

И потом тоже сдвиг на степень двойки?

не, потом брутфорс. т.е. если мы понимает, что «точно нуля» не будет — в цикле сделаем, что просят.

Ясно, понял

@KlenZeleny а как у тебя вот это работает m & n & (~0 << shift), сможешь рассказать?

m & n оставит нам единицы, которые есть в каждом числе у границ диапазона. Но чтобы они остались нужно их & с единицей. ~0 даст нам набор единиц. А shift даст нам сдвиг на столько битов, сколько точно менялись при последовательном & для всех чисел.

you are a machine)

И они нам не нужны. Но могут быть нужны старшие биты на "перекрытии" старших битов у двух границ.

you are a machine)

Всё бы так быстро решалось)

Если проще, то мы выкидываем степени двойки, которые влезают в разницу n-m. Те, которые получится. И оставляем те, которые не получится

На то число степеней, которые выкинули, нам и нужен сдвиг

Помните радостную для многих новость? В этом году в ШАД можно поступить и без знания хардкорной математики. Для таких студентов прочитают специальный адаптационный курс. До этого шадовцам, поступившим без сильной математической базы, приходилось гораздо сложнее. Прочитайте историю Ваге Егиазаряна о том, как Школа анализа данных вновь открыла для него высшую математику и путь в науку 🎓 https://ya.cc/t/1KF88Iu9Ai2tD