5 ms·
A neat one for large, sparse integers is: for(i=0; !x; ++i) { x = (x-1)&x } return i; Which runs only a number of iterations equal to the number of
by amalcon 5y ago
A neat one for large, sparse integers is:
for(i=0; !x; ++i) {
x = (x-1)&x
}
return i;
Which runs only a number of iterations equal to the number of 1 bits. This works because (x-1) actually just flips the rightmost 1 bit and all zeroes to its right, then the & zeroes all of those.
It's not that fast unless your integer is really sparse (since it has a branch), but I've always liked the bit hack.
- pbsd 5y agoWhen 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.