user
*Clarification: This task is asking for the position of two bits in the binary representation of a positive integer. Some parts of this task assume that this is the native representation in the language you are working in. Any part of this task which makes assumptions about native representation should be treated as a recommendation which is only relevant in some contexts. A bit is defined as the exponent in a binary polynomial -- an exponent corresponding to a power of 2 which has a non-zero multiplier in the summation sequence of powers of two which yields the desired positive integer, where the only allowed coefficients are 0 and 1.*

Define routines (or operators) **lwb** and **upb** that find the *first* and *last* set bit in a binary value. Implement using a binary search to find the location of the particular upper/lower bit.

Also: Define the reverse routines (or operators) **rlwb** and **rupb** that find host's *positive integers* least- and most-significant set bit in a binary value expressed in LSB 0 bit numbering, i.e. indexed from the extreme right bit.

Use primarily **bit** operations, such as **and**, **or**, and bit shifting. Avoid additions, multiplications and especially avoid divisions.

Two implementations

1. For the host word size on the host platform, implement the routine "efficiently" in without looping or recursion.
2. For the extended precision/long word implement the algorithm more generally - maybe as a template, and maybe with looping - so that any *bits width* for a binary type can be accommodated.

Test cases

1. For the host machine word size: Use the powers of 42 up to host's the "natural" word size to calculate the index of the first and last set bit.
2. For the extended precision: Use the powers of 1302 up to the host's next "natural" **long** host *word* size to calculate the index of the first and last set bit.
3. Output bit indexes in LSB 0 bit numbering.

Additionally

In a particular language, there maybe (at least) two alternative approaches of calculating the required values:

* Using an external library.
* Using a built-in library.

If any of these approaches are available, then *also* note the library or built-in name.

See also

* Find the log base 2 of an N-bit integer in O(lg(N)) operations
* 80386 Instruction Set - BSF -- Bit Scan Forward
assistant
(formerly Perl 6)

Raku integers are arbitrary sized, and the lsb and msb methods are built-in.

```
sub table ($base,$power) {
    my $digits = ($base ** $power).chars;
    printf "%{$digits}s  lsb msb\n", 'number';
    for 0..$power {
	my $x = $base ** $_;
	printf "%{$digits}d  %2d  %2d\n", $x, $x.lsb, $x.msb;
    }
}

table 42, 20;
table 1302, 20;

```

Output:

```
                           number  lsb msb
                                1   0   0
                               42   1   5
                             1764   2  10
                            74088   3  16
                          3111696   4  21
                        130691232   5  26
                       5489031744   6  32
                     230539333248   7  37
                    9682651996416   8  43
                  406671383849472   9  48
                17080198121677824  10  53
               717368321110468608  11  59
             30129469486639681536  12  64
           1265437718438866624512  13  70
          53148384174432398229504  14  75
        2232232135326160725639168  15  80
       93753749683698750476845056  16  86
     3937657486715347520027492352  17  91
   165381614442044595841154678784  18  97
  6946027806565873025328496508928  19  102
291733167875766667063796853374976  20  107
                                                         number  lsb msb
                                                              1   0   0
                                                           1302   1  10
                                                        1695204   2  20
                                                     2207155608   3  31
                                                  2873716601616   4  41
                                               3741579015304032   5  51
                                            4871535877925849664   6  62
                                         6342739713059456262528   7  72
                                      8258247106403412053811456   8  82
                                  10752237732537242494062515712   9  93
                               13999413527763489727269395457024  10  103
                            18227236413148063624904752885045248  11  113
                         23731861809918778839625988256328912896  12  124
                      30898884076514250049193036709740244590592  13  134
                   40230347067621553564049333796081798456950784  14  144
                52379911882043262740392232602498501590949920768  15  155
             68198645270420328087990686848453049071416796839936  16  165
          88794636142087267170563874276685869890984669485596672  17  175
      115610616256997621856074164308245002598062039670246866944  18  186
   150525022366610903656608561929334993382676775650661420761088  19  196
195983579121327396560904347631994161384245161897161169830936576  20  206
```