4 ms·
When the integer is expected to be dense, you have the corresponding trick size_t count = sizeof(x) * 8; while(x != -1) { x |= x+1; --c
by pbsd 5y ago
When the integer is expected to be dense, you have the corresponding trick
size_t count = sizeof(x) * 8;
while(x != -1) {
x |= x+1;
--count;
}
return count;
- throw5away 5y agoThis is essentially equivalent to feeding the input through bitwise-NOT first. Unfortunately, there are far more integers that are neither sparse nor dense than integers that are sparse or dense.
- jffry 5y agoBut I can certainly imagine there could be problem domains where most of some collection of integers being manipulated are expected to be sparse or dense.