Blessed Monks, I humbly prithee guidance bestow. I'm looking to benchmark for a variant of the binary search algorithm, but before I begin I'm trying to bake it down to the most efficient Perl code I possibly can. I'm looking for the most efficient way to find the Most Significant Set Bit of a given integer value. I am unaware of a Perl function that does this. I have almost no experience in C, but I read that GCC does have an algorithm for this. Up to now, I have been using the following code to find the most significant set bit of a given 64-bit integer. I did my best to format it legibly here; though it looks like puke, it's a single statement. Is there a better performing solution? 
$m is assigned the most significant set bit of 64-bit integer $z, for 
+the cost of 6 ANDs and 6 truth tests.

 my $m=-4294967296&$z? -281474976710656&$z? -72057594037927936&$z?
   -1152921504606846976&$z? -4611686018427387904&$z? -9223372036854775
+808&$z?
                  4611686018427387904:   2305843009213693952
    : -2305843009213693952&$z?
                  1152921504606846976:   576460752303423488
   : -288230376151711744&$z? -576460752303423488&$z?
                  288230376151711744:    144115188075855872
    : -144115188075855872&$z?
                  72057594037927936:     36028797018963968
  : -4503599627370496&$z? -18014398509481984&$z?   -36028797018963968&
+$z?
                  18014398509481984:     9007199254740992
    : -9007199254740992&$z?
                  4503599627370496:      2251799813685248
   : -1125899906842624&$z? -2251799813685248&$z?
                  1125899906842624:      562949953421312
    : -562949953421312&$z?
                  281474976710656:       140737488355328
 : -1099511627776&$z? -17592186044416&$z? -70368744177664&$z? -1407374
+88355328&$z?
                  70368744177664:        35184372088832
    : -35184372088832&$z?
                  17592186044416:        8796093022208
   : -4398046511104&$z? -8796093022208&$z?
                  4398046511104:         2199023255552
    : -2199023255552&$z?
                  1099511627776:         549755813888
  : -68719476736&$z? -274877906944&$z? -549755813888&$z?
                  274877906944:          137438953472
    : -137438953472&$z?
                  68719476736:           34359738368
   : -17179869184&$z? -34359738368&$z?
                  17179869184:           8589934592
    : -8589934592&$z?
                  4294967296:            2147483648
: -65536&$z? -16777216&$z? -268435456&$z? -1073741824&$z? -2147483648&
+$z?
                  1073741824:            536870912
    : -536870912&$z?
                  268435456:             134217728
   : -67108864&$z? -134217728&$z?
                  67108864:              33554432
    : -33554432&$z?
                  16777216:              8388608
  : -1048576&$z? -4194304&$z? -8388608&$z?
                  4194304:               2097152
    : -2097152&$z?
                  1048576:               524288
   : -262144&$z? -524288&$z?
                  262144:                131072
    : -131072&$z?
                  65536:                 32768
 : -256&$z? -4096&$z? -16384&$z? -32768&$z?
                  16384:                 8192
    : -8192&$z?   4096:                  2048
   : -1024&$z? -2048&$z?
                  1024:                  512
    : -512&$z?    256:                   128
  : -16&$z? -64&$z? -128&$z?
                  64:                    32
    : -32&$z?     16:                    8
   : -4&$z? -8&$z?
                  4:                     2
    :             2                      ;

[download]
EDIT 2024/3/25: Updating for completeness.

As bliako generously published GCC::Builtins in response to this question, and a benchmark in the documentation refers back to this code for comparison, I've posted an updated version below which is more directly comparable. The code I originally posted above is exactly as slow, but the output constants represented the answer in different terms to clz(). The new code is just for comparing apples to apples (and heeding some legibility advice from hv).

I was surprised that GCC::Builtins::clz is only twice as fast, considering the essential part is just one CPU instruction (LZCNT) which should take practically no time at all. I guess most of that time is spent on the call stack and related. 

my $z=17;
my $m;

{   no warnings;  ## to suppress warning
                  ## "Hexadecimal number > 0xffffffff non-portable"
    $m=
    0xFFFFFFFF80000000&$z?
        0xFFFF800000000000&$z?
            0xFF80000000000000&$z?
                0xF800000000000000&$z?
                    0xE000000000000000&$z?
                        0xC000000000000000&$z?
                            0x8000000000000000&$z?      0
                        :                       1:      2
                    :   0xF000000000000000&$z?  3:      4
                :   0xFE00000000000000&$z?
                        0xFC00000000000000&$z?  5:      6
                    :   0xFF00000000000000&$z?  7:      8
            :   0xFFF8000000000000&$z?
                    0xFFE0000000000000&$z?
                        0xFFC0000000000000&$z?  9:      10
                    :   0xFFF0000000000000&$z?  11:     12
                :   0xFFFE000000000000&$z?
                        0xFFFC000000000000&$z?  13:     14
                    :   0xFFFF000000000000&$z?  15:     16
        :   0xFFFFFF8000000000&$z?
                0xFFFFF80000000000&$z?
                    0xFFFFE00000000000&$z?
                        0xFFFFC00000000000&$z?  17:     18
                    :   0xFFFFF00000000000&$z?  19:     20
                :   0xFFFFFE0000000000&$z?
                        0xFFFFFC0000000000&$z?  21:     22
                    :   0xFFFFFF0000000000&$z?  23:     24
            :   0xFFFFFFF800000000&$z?
                    0xFFFFFFE000000000&$z?
                        0xFFFFFFC000000000&$z?  25:     26
                    :   0xFFFFFFF000000000&$z?  27:     28
                :   0xFFFFFFFE00000000&$z?
                        0xFFFFFFFC00000000&$z?  29:     30
                    :   0xFFFFFFFF00000000&$z?  31:     32
    :   0xFFFFFFFFFFFF8000&$z?
            0xFFFFFFFFFF800000&$z?
                0xFFFFFFFFF8000000&$z?
                    0xFFFFFFFFE0000000&$z?
                        0xFFFFFFFFC0000000&$z?  33:     34
                    :   0xFFFFFFFFF0000000&$z?  35:     36
                :   0xFFFFFFFFFE000000&$z?
                        0xFFFFFFFFFC000000&$z?  37:     38
                    :   0xFFFFFFFFFF000000&$z?  39:     40
            :   0xFFFFFFFFFFF80000&$z?
                    0xFFFFFFFFFFE00000&$z?
                        0xFFFFFFFFFFC00000&$z?  41:     42
                    :   0xFFFFFFFFFFF00000&$z?  43:     44
                :   0xFFFFFFFFFFFE0000&$z?
                        0xFFFFFFFFFFFC0000&$z?  45:     46
                    :   0xFFFFFFFFFFFF0000&$z?  47:     48
        :   0xFFFFFFFFFFFFFF80&$z?
                0xFFFFFFFFFFFFF800&$z?
                    0xFFFFFFFFFFFFE000&$z?
                        0xFFFFFFFFFFFFC000&$z?  49:     50
                    :   0xFFFFFFFFFFFFF000&$z?  51:     52
                :   0xFFFFFFFFFFFFFE00&$z?
                        0xFFFFFFFFFFFFFC00&$z?  53:     54
                    :   0xFFFFFFFFFFFFFF00&$z?  55:     56
            :   0xFFFFFFFFFFFFFFF8&$z?
                    0xFFFFFFFFFFFFFFE0&$z?
                        0xFFFFFFFFFFFFFFC0&$z?  57:     58
                    :   0xFFFFFFFFFFFFFFF0&$z?  59:     60
                :   0xFFFFFFFFFFFFFFFE&$z?
                        0xFFFFFFFFFFFFFFFC&$z?  61:     62
                    :   0xFFFFFFFFFFFFFFFF&$z?  63:     64;
                    }

[download]


32-bit version: 
my $m=0xFFFF8000&$z?
        0xFF800000&$z?
            0xF8000000&$z?
                0xE0000000&$z?
                    0xC0000000&$z?
                        0x80000000&$z?  0
                    :               1:  2
                :   0xF0000000&$z?  3:  4
            :   0xFE000000&$z?
                    0xFC000000&$z?  5:  6
                :   0xFF000000&$z?  7:  8
        :   0xFFF80000&$z?
                0xFFE00000&$z?
                    0xFFC00000&$z?  9:  10
                :   0xFFF00000&$z?  11: 12
            :   0xFFFE0000&$z?
                    0xFFFC0000&$z?  13: 14
                :   0xFFFF0000&$z?  15: 16
    :   0xFFFFFF80&$z?
            0xFFFFF800&$z?
                0xFFFFE000&$z?
                    0xFFFFC000&$z?  17: 18
                :   0xFFFFF000&$z?  19: 20
            :   0xFFFFFE00&$z?
                    0xFFFFFC00&$z?  21: 22
                :   0xFFFFFF00&$z?  23: 24
        :   0xFFFFFFF8&$z?
                0xFFFFFFE0&$z?
                    0xFFFFFFC0&$z?  25: 26
                :   0xFFFFFFF0&$z?  27: 28
            :   0xFFFFFFFE&$z?
                    0xFFFFFFFC&$z?  29: 30
                :   0xFFFFFFFF&$z?  31: 32;

[download]


There really isn't any good reason to use this, as bliako's GCC::Builtins::clz is about twice as fast (and about 64 times simpler) - unless, of course, you're modifying the constants to return some other pre-computed result for which there is no builtin alternative, to eliminate a few instructions. Personally, I'm going to see if I can write the whole encompassing piece of work in Perl+Assembly, as suggested. Straight down the rabbit hole at terminal velocity.

In reply to 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.