Эта проблема из Codesprint 2011 (http://csfall11.interviewstreet.com/):

Одной из основ информатики является знание того, как числа представлены в дополнении 2. Представьте, что вы записываете все числа между A и B включительно в представлении дополнения 2, используя 32 бита. Сколько всего 1 вы запишите? Входные данные: первая строка содержит количество тестов 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

Я понимаю, что вы можете использовать тот факт, что число 1 в -X равно числу 0 в дополнении (-X) = X-1, чтобы ускорить поиск. В решении утверждается, что для генерации ответа существует рекуррентное отношение O (log X), но я его не понимаю. Код решения можно посмотреть здесь:https://gist.github.com/1285119

Я был бы признателен, если бы кто-то мог объяснить, как происходит это отношение!