bit operations in O(1) time?

[micahscopes]

It says on the front page that bit operations are done in O(1) time. Shouldn't that say O(n) time? The time complexity of bitwise operations between two words might be O(1), but this iterates over multiple words, so the time complexity is still scaling O(n/32) = O(n).

This would be different if these operations were done in parallel of course, which they definitely could be.

[mattkrick]

You're absolutely right, it's really O(n/31) = O(n). That denominator is nontrivial for long running tasks & I remember digging through every library looking for something that didn't just run a forEach loop on each set bit, which offers little to no savings over a traditional array.