由买买提看人间百态

topics

全部话题 - 话题: popcount
(共0页)
f*****e
发帖数: 2992
1
popcount?汇编指令?
a******t
发帖数: 100
2
来自主题: CS版 - 谁有什么solution吗?

I am not sure if you can do it in constant time.
A lg(n) algorithm is obvious, where n is number of bits in registers.
Just count how many 1's in (x - 1).
If you use popcount instruction in IA-64, it is constant time, from what
you see.
r*******n
发帖数: 51
3
来自主题: CS版 - 谁有什么solution吗?
I agree with you because we can assume that the x can't be larger than what
the register can load. The complexity of operation x&(-x) should be somehow
constant, I guess, because the operation & should be done in one clock cycle
but -x might depend on bit length. However, it doesn't matter because we treat
sub operation as a O(1) operation. In this sense, we can say x&(-x) is a O(1)
operation.
I am now just wondering that if I want to use popcount, the only way to do it
is using assembly, right?
(共0页)