Bit counting, обзор методов

[dreamiurg]

Comments

[dream_inspector]

Еще классический способ, отнять единичку и сделать and. ДО те пор пока число не станет нулем, сколько раз сделал - столько и единиц.

[dreamiurg]

Да, это как раз вариант dense/sparse - для 0 и 1, соответственно. Плюшки в том, что вместо цикла на 8-16-32.. операций по количеству сдвигов, получаем максимум N/2. Я там выше писал, для этого лучше знать, какие биты преобладают - но и в худшем случае производительность сравнима с шифтером

[dream_inspector]

Тейбл на 16 бит рулит :)

[dreamiurg]

в теории мог бы зарулить тейбл и на 32, но сильно много места скушает, да и не поместится в памяти, так что на свопах потеряем :)