A binary search should be the 3rd alternative here. First alternative, if the problem space is only 64 bits, is a linear search through 64 bits. Second alternative should probably be a mathematical solution. And the third would be a binary search. It's really hard to make the complexity of a binary search beat the speed of a linear search for a small search set.

It's true that a binary search in a 64 bit unsigned integer range is going to take, at worst, 64 comparisons. And on average, a lot less than 64 comparisons, in a randomized data set of 64 bit numbers. This is O(log(n)). But a linear search through a 64-bit vector to find the most significant bit for an integer, is also O(log(n)); you have at most 64 comparisons with a binary search through 2**64 numbers, or you have at most 64 comparisons if you do a linear search through the bits of a number that fits within 64 bits. And a linear search will be very fast for such a small problem space.

But a mathematical solution to the problem is that the most significant bit of any unsigned integer will be found at index int(log2(n)). So if n is 1, int(log2(n)) is 0 (the zero-index bit; the right-most bit). The int(log2(32767)) is 15. You cannot represent 32767 in fewer than 16 bits. And the most significant bit will be the left-most bit, or the bit at index (offset) 15.

Therefore, a solution that requires NO iteration at all could be:

sub most_significant_ix {
    my $n = shift;
    return if $_[0] == 0;
    return int(log($_[0])/log(2));
}

[download]

Unfortunately the log function isn't inexpensive, so the linear search through 64 bits will probably still win, though on paper this solution is O(1), whereas the linear search through bits of an integer, and the binary search through the integer range, will both be O(log(n)) time complexity.

A linear search through the bits solution would look like this:

sub most_significant_ix {
    my $n = shift;
    return undef if $n == 0;
    my $bits = 64;
    while (--$bits >= 0) {
        return $bits if (2**$bits) & $n;
    }
}

[download]

Dave

In reply to Re: Most Significant Set Bit by davido
in thread Most Significant Set Bit by coldr3ality

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.