Эта проблема относится к 2011 Codesprint (http://csfall11.interviewstreet.com/):
Одна из основ компьютерной науки - знание того, как числа представлены в 2 дополнениях. Представьте, что вы записываете все числа между A и B включительно в 2 дополнениях с использованием 32 бит. Сколько всего вы запишете? Входные данные: Первая строка содержит количество тестовых примеров T (< 1000). Каждая из следующих T строк содержит два целых числа A и B. Вывод: Выходные линии T, соответствующие каждому тестовому примеру. Ограничения: -2 ^ 31 <= A <= B <= 2 ^ 31 - 1
Пример ввода: 3 -2 0 -3 4 -1 4 Результат выборки: 63 99 37
Объяснение: В первом случае -2 содержит 31 1, за которым следует 0, -1 содержит 32 1 и 0 содержит 0 1. Таким образом, общее число составляет 63. Для второго случая ответ равен 31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99
Я понимаю, что вы можете использовать тот факт, что число 1s в -X равно числу 0s в дополнении (-X) = X-1, чтобы ускорить поиск. В решении утверждается, что для генерации ответа существует рекуррентное отношение O (log X), но я его не понимаю. Код решения можно посмотреть здесь: https://gist.github.com/1285119
Я был бы признателен, если бы кто-нибудь мог объяснить, как это отношение получается!