Операция xor, большие числа

@Retry32 · Регистрация: 05.05.2021

Студворк — интернет-сервис помощи студентам

Здравствуйте! Хотел бы попросить помощи по следующей задачи:
Есть два числа X, Y (1 ≤ X, Y ≤ 10^9). Нужно подсчитать сумму: i XOR (i - 1) для всех i от x до y включительно.
Попробовал написать такой код:

Python
1
2
3
4
5
x, y = map(int, input().split())
count = 0
for i in range(x, y + 1):
    count += i ^ (i - 1)
print(count)

В тупую пройти не получилось потому что очень долго для больших значений x, y.
Я попробовал использовать свойства xor:

Python
1
2
3
4
5
6
7
8
9
x, y = map(int, input().split())
count = 0
if x ^ (x - 1) == 1:
    for i in range(x + 1, y + 1, 2):
        count += i ^ (i - 1)
else:
    for i in range(x, y + 1, 2):
        count += i ^ (i - 1)
print(count + (y - x) // 2 + 1)

Но все равно очень долго. Помогите пожалуйста, буду очень благодарен!

@eaa · 30.08.2023, 09:42

https://oeis.org/A003815
изучи для начала. если не получится пиши.

@Retry32 · 30.08.2023, 10:24 **[ТС]**

Сообщение от eaa

https://oeis.org/A003815
изучи для начала. если не получится пиши.

Честно, не совсем понимаю как использовать эту задачу для решения моей. Я вижу сходства, но не могу понять как из этого получить подсказку к решению своей проблемы. Не могли бы вы подробнее объяснить?

@Red white socks · 30.08.2023, 10:35

Retry32,
пусть
s_x = 1 ^ 2 ^ ... ^ x,
s_y = 1 ^ 2 ^ ... ^ y

Чему равно s_x ^ s_y?

Кажется, я спросонья задачу не понял...
Тут обычные префиксные суммы.

@eaa · 30.08.2023, 10:42

Retry32, ошибся, задачу прочитал не правильно. сорри.
вот https://oeis.org/A038712

@Red white socks · 30.08.2023, 10:52

Еще лучше вот здесь A080277

@eaa · 30.08.2023, 11:15

Red white socks, ну да. это следующий этап. там подсчет за логарифм.

Python
1
2
3
4
5
6
7
8
def foo(n):
    if n == 0:
        return 0
    return n + 2 * foo(n // 2)
 
 
x, y = map(int, input().split())
print(foo(y) - foo(x - 1))

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .

Операция xor, большие числа

Решение

Решение

Решение

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	30.08.2023, 09:42
	https://oeis.org/A003815 изучи для начала. если не получится пиши. 2

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	30.08.2023, 10:35
	Retry32, пусть s_x = 1 ^ 2 ^ ... ^ x, s_y = 1 ^ 2 ^ ... ^ y Чему равно s_x ^ s_y? Кажется, я спросонья задачу не понял... Тут обычные префиксные суммы. 2

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	30.08.2023, 10:42
	Сообщение было отмечено Retry32 как решение Решение Retry32, ошибся, задачу прочитал не правильно. сорри. вот https://oeis.org/A038712 3

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	30.08.2023, 10:52
	Сообщение было отмечено Retry32 как решение Решение Еще лучше вот здесь A080277 3