Количество единиц в двоичных представлениях целых чисел с дополнением до двух

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

Одна из основ компьютерных наук - знать, как числа представлены в дополнении до 2-х. Представьте, что вы записываете все числа от A до B включительно в дополнительном представлении 2, используя 32 бита. Сколько единиц вы запишете всего? Входные данные: Первая строка содержит количество тестовых примеров T (

Пример ввода: 3 - 2 0 { {1}} - 3 4 - 1 4 Пример вывода: 63 99 37

Пояснение: {{1} } В первом случае -2 содержит 31 единицу, за которой следует 0, -1 содержит 32 единицы, а 0 содержит 0 единиц. Таким образом, всего 63. Для второго случая ответ: 31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99

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

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