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

[avva]

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

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

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

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

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

Comments

[insie-ru.livejournal.com]

почувствовал себя кретином

[avva.livejournal.com]

Это полезное чувство. Случается со мной не реже раза в неделю, и обычно помогает :)

[insie-ru.livejournal.com]

тут не поможет, лет 7 назад я бы решил эту задачку, а сейчас не вижу смысла все вспоминать или ломать голову о_О

[dimrub.livejournal.com]

1) -x
2) надо подумать

[dimrub.livejournal.com]

Впрочем, нет, вру: результат ведь зависит только от числа зажженых битов в x, а не от его значения.

[dimrub.livejournal.com]

В общем, я ведь если какую глупость не напишу, спать-то не пойду. Поэтому пишу глупость:

1. -к, где к - число зажженых битов в x
2. на каждой из 64 позиций аккумулятора в свое время побывает каждый из битов x, соответственно, результат можно выразить как

- - - - ... -
k k k k ... k - 64 раза.

иными словами,

acc = 2^63*k + 2^62*k + ... + 2^0*k = k(2^63 + ... + 2^0) = k * 111...111 (64 раза) = k * -1 = -k.

[kouzdra.livejournal.com]

Это x * (sum i=0..63 2^i) по модулю 2^64
соотвественно - (2^64-1)*x = -x

(если ничего не наврал +/-1 - пошел смотреть ответы)

[kouzdra.livejournal.com]

PS: Похоже не наврал - по крайней мере с dimrub сошлось

[kouzdra.livejournal.com]

Забавно - я вместо наблюдений над битами свернул сумму по формуле для прогрессии и раскрыл скобки.

[avva.livejournal.com]

Почему же глупость? Все правильно :)

[avva.livejournal.com]

С первым ответом dimrub, неверным. Впрочем, уже разобрались.

[failhigh.wordpress.com (from livejournal.com)]

Пусть в числе n-единиц.
Мы складываем само с собой 64 раза число сдвигаемое на 1 бит влево.
Если мы представим это сложением в столбик, то получим такой себе квадрат 64x64.
В каждой строке это число сдвигаемое на бит, но и в каждом столбце оно же!
Следовательно в каждом столбце n-единиц!
Поменяем единицы местами, так, чтобы в каждом столбце они шли подряд.
Так мы получаем n*0xFFFFFFFFFFFFFFFF = -n!
Спасибо за задачку!

Черт! Пока постил опередили...

[kouzdra.livejournal.com]

Да - увы.

[avva.livejournal.com]

Ничего страшного, это не забег :) все верно, да. Красиво, правда?

[(Anonymous)]

Да, безусловно.
Это я, как бы, первый раз поучаствовал в Ваших играх.
Хотя и не самый быстрый способ биты считать :)

[dimrub.livejournal.com]

По аналогии с предыдущей. Т.е. я разобрался, что делает g, но зачем это может быть нужно - так и не понял пока. Не рассказывай, я еще подумаю :).

[spamsink.livejournal.com]

Красиво. Особенно когда через 10 минут размышлений понимаешь, что это издевательство, и что ответы на 1) и 2) - это одно и то же. :)

[a-konst.livejournal.com]

а у меня сперва получилось просто 0xff..f * (чётность количества битов в x), со сложением многих экземпляров
0xff..f напутал.

Красиво, да.
Интересно, это самый эффективный способ посчитать это самое количество? Если пользоваться только базовыми инструкциями процессора.

Хотя, наверно если умело использовать флаг переполнения и условные переходы, то можно быстрее.

[avva.livejournal.com]

Нет, есть два разных способа посчитать быстрее :) oдин ненамного быстрее, и еще один намного.

наконец-то!

[ex-ex-fatal.livejournal.com]

он сделал это!

[dizzy57.livejournal.com]

Второй это divide and conquer?

[qaraabayna.livejournal.com]

Эта задачка мне нравится больше.

[dizzy57.livejournal.com]

При обдумывании почти одновременно «выстрелили» две аналогии — симметризация тензора и преобразование Барроуза-Вилера. Вторая оказалась решающей, получилась конструкция как у failhigh.

[avva.livejournal.com]

Ага.

[drw.livejournal.com]

Отрицание числа единиц в x.

[drw.livejournal.com]

Т.е. отрицание в смысле дополнения до двух, а не побитовое.

[avva.livejournal.com]

ага.

[itman.livejournal.com]

Тьфу ты елки, первая из задачек Аввы, которую я решил правильно и за 5 секунд. В действительности, если просуммировать все полученные числа и взять остаток по модулю два, то ответ получается еще быстрее :-)

[itman.livejournal.com]

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

[avva.livejournal.com]

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

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

[neatfires.livejournal.com]

А по-моему, прелесть в том, что как раз один из самых простых. Техника скрыта, с виду все чистенько.

[avva.livejournal.com]

Не, неверно.

[cmm.livejournal.com]

потому что "two's complement".

[ex-tws5249.livejournal.com]

получается минус количество единиц в x

только зачем это, разве быстрее никак нельзя?

кольцевые числа

[qaraabayna.livejournal.com]

только сейчас пришло в голову, что мое представление об int как о множестве-кольце можно поменять на представление о int как множестве из кольцевых представлений.

[ygam.livejournal.com]

Забавно!

1. Получается минус количество единиц в двоичном представлении x.

2. Представим x как сумму степеней двойки. Для каждой степени двойки аккумулятор будет равен 11111111...1 (т.е. -1). Для всех - -1 умноженное на количество степеней двойки, т.е. минус количество единиц в двоичном представлении x.

[avva.livejournal.com]

Ага.

[shamany.livejournal.com]

в калькуляторах все умножения есть сложения+сдвиги, а все сложения есть тоже сдвиги ;)

"кто видел Felix (tm) того ничем уже не удивишь"

[(Anonymous)]

Никак не могу понять, откуда берутся отрицательные числа, если по условиям задачи, все опранды без знака?

[avva.livejournal.com]

Можно объяснить так: в конце концов мы получаем число n * (2^64-1), где второй множитель равен 0x1111111111111111. Если его, этот множитель, интерпретировать как число со знаком, то это -1, и тогда результат можно интерпретировать как -n. Если продолжать к нему относиться как к числу без знака, то это просто какое-то неинтересное умножение.

Умножение на отрицательное число и на положительное без знака, ровно с теми же битами - один и тот же результат дает.

[panikowsky.livejournal.com]

Это не факториал, а восклицательный знак.

[barzel.livejournal.com]

Можно задать вопрос вне темы?
Я тут решил разобраться с логарифмической линейкой. Вооружившись знанием того, что это очень "просто" я приступил к изучению и сразу споткнулся:
Есть способ получить корент из больших чисел(например порядка миллиона), есть даже описание, но описание какое-то не полное. В общем я не понял как оно работает, моет у Вас есть идея?
http://www.sliderule.ca/k12-prep-p14-15.jpg

Буду очень благодарен

[it-person.livejournal.com]

Отвечаю, не глядя в комменты.

Каждый ненулевой бит будет повторен 64 раза, вот так:

1111111111111111111111111111111111111111111111111111111111111111

это 2^64-1, что соответствует -1

И эта штука будет прибавлена столько раз, сколько в этом числе ненулевых бит.

В результате accum = -1 * (число ненулевых бит в числе x)

Иначе говоря accum = 2^64 - (сумма цифр x)