We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Yes, the problem requires to calculate a logarithm. But calculating logarithm of an integer is O(log log n). This is even without hardware optimizations. It's much much less than O(log n).
And there are hardware optimizations, becuase this particular problem really only requires answering "how many leading zero bits are there in a 64-bit integer?". If you need 64 iterations to check that, well, I can certainly see much room for improvement!
Strange Counter
You are viewing a single comment's thread. Return to all comments →
Yes, the problem requires to calculate a logarithm. But calculating logarithm of an integer is O(log log n). This is even without hardware optimizations. It's much much less than O(log n).
And there are hardware optimizations, becuase this particular problem really only requires answering "how many leading zero bits are there in a 64-bit integer?". If you need 64 iterations to check that, well, I can certainly see much room for improvement!