еще раз о битах

[avva]

Вот еще одна задачка для программистов. Если знаете ответ, не пишите. Комментарии скрывать не буду; советую попробовать решить самостоятельно, до того, как подсматривать чужие ответы - красивая штука.

Дано 64-битное число x. Мы делаем с ним следующее (в псевдокоде):

accum = 0
do 64 times:
  accum += x
  x = x rot 1
end

Здесь rot - вращение числа на один разряд влево (выходящий слева бит становится вправо). И accum, и x - 64-битные числа без знака; при сложении мы отбрасываем бит переноса, если он образуется.

Вопросы: 1) что мы получаем? 2) почему это так получается?

Comments

[itman.livejournal.com]

А разве может что-нибудь быстрее тупого сложения по модулю 2^n? При циклическом сдвиге каждый бит оказывается при каждом множителе вида 2^k ровно один раз, дальше выделяем общий множитель 2^n - 1 и вуаля? Или это и есть пресловутый divide and conquer?

[avva.livejournal.com]

Первый алгоритм быстрее использует свойства операции x & (x-1).

Второй алгоритм быстрее, который divite and conquer, основан на следующей мысли: что если бы могли, используя одни и те же инструкции, параллельно вычислить в нижних 32 битах кол-во единиц в них, в верхних - кол-во единиц в них, и тогда остается только сложить? Тот же вопрос для 32 бит решает далее рекурсивно итд.