I'm not quite sure what is meant by doing a binary search on the bits
I mean the exact thing that OP used as an example :-) My phrasing "binary search on the bits" might not be the best name for it; maybe "a log-based binary search"?
Written in a generic manner, it might look like
my ($min, $max, $mid)= (0, 62);
while ($min < $max) {
$mid= int(($min+$max)/2);
if ($n < (1 << $mid)) { $max= $mid-1; }
else { $min= $mid; }
}
but since we know the range is 64 bit, it can be unrolled as
if ($n < 0x100000000) {
if ($n < 0x10000) {
if ($n < 0x100) {
if ($n < 0x10) {
if ($n < 8) {
if ($n< 4) {
return $n < 2? 1 : 2;
and so on.
Now, I have to retract my earlier statement about analyzing log() in terms of generic-length bit strings, because this binary search does actually depend on greater and lessthan ops being constants. In a variable-length bit string, those would also be loops. Still, I think even for fixed-width 64-bit numbers the log() function is probably implemented as a loop because they have to calculate out the full floating point precision, so it should be at least as expensive as floating point division, which is notoriously slower than the other floating-point operations.
