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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Не, неверно.

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

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

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

Ага.

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

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

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

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

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