Find first and last set bit of a long integer

From Rosetta Code
Revision as of 20:46, 10 December 2023 by Boreal (talk | contribs) (Added XPL0 example.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Find first and last set bit of a long integer is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.


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



11l

L(i) 6
    V x = Int(42 ^ i)
    print(‘#10 MSB: #2 LSB: #2’.format(x, bsr(x), bsf(x)))
 
L(i) 6
    V x = Int64(1302 ^ i)
    print(‘#20 MSB: #2 LSB: #2’.format(x, bsr(x), bsf(x)))
Output:
         1 MSB:  0 LSB:  0
        42 MSB:  5 LSB:  1
      1764 MSB: 10 LSB:  2
     74088 MSB: 16 LSB:  3
   3111696 MSB: 21 LSB:  4
 130691232 MSB: 26 LSB:  5
                   1 MSB:  0 LSB:  0
                1302 MSB: 10 LSB:  1
             1695204 MSB: 20 LSB:  2
          2207155608 MSB: 31 LSB:  3
       2873716601616 MSB: 41 LSB:  4
    3741579015304032 MSB: 51 LSB:  5

Ada

with Ada.Text_IO;
with Ada.Integer_Text_IO;
with Ada.Unchecked_Conversion;

procedure Find_Last_Bit is

   type My_Integer is range -2**63 .. 2**63 - 1;

   procedure Find_Set_Bits (Value   : in     My_Integer;
                            MSB_Bit :    out Integer;
                            LSB_Bit :    out Integer)
   is
      type Bit_Field is array (0 .. My_Integer'Size - 1) of Boolean;
      pragma Pack (Bit_Field);
      for Bit_Field'Size use My_Integer'Size;

      function To_Field is
         new Ada.Unchecked_Conversion (My_Integer, Bit_Field);

      Field : constant Bit_Field := To_Field (Value);
   begin

      LSB_Bit := -1;
      MSB_Bit := -1;

      for Bit in Field'Range loop
         if Field (Bit) then
            LSB_Bit := Bit;
            exit;
         end if;
      end loop;

      for Bit in reverse Field'Range loop
         if Field (Bit) then
            MSB_Bit := Bit;
            exit;
         end if;
      end loop;
   end Find_Set_Bits;


   procedure Put_Result (Value : in My_Integer) is
      package My_Integer_IO is
         new Ada.Text_IO.Integer_IO (My_Integer);
      use Ada.Text_IO;
      use Ada.Integer_Text_IO;
      Use My_Integer_IO;

      LSB_Bit, MSB_Bit : Integer;
      Placeholder : String := " MSB XX LSB YY";
      Image_MSB     : String renames Placeholder ( 6 ..  7);
      Image_LSB     : String renames Placeholder (13 .. 14);
   begin
      Find_Set_Bits (Value,
                     MSB_Bit => MSB_Bit,
                     LSB_Bit => LSB_Bit);
      Put (Value, Width => 18);
      Put (Value, Width => 66, Base => 2);
      Put (Image_MSB, MSB_Bit);
      Put (Image_LSB, LSB_Bit);
      Put_Line (Placeholder);
   end Put_Result;

begin
   Put_Result (Value => 0);
   for A in 0 .. 11 loop
      Put_Result (Value => 42 ** A);
   end loop;
end Find_Last_Bit;
Output:
                 0                                                              2#0# MSB -1 LSB -1
                 1                                                              2#1# MSB  0 LSB  0
                42                                                         2#101010# MSB  5 LSB  1
              1764                                                    2#11011100100# MSB 10 LSB  2
             74088                                              2#10010000101101000# MSB 16 LSB  3
           3111696                                         2#1011110111101100010000# MSB 21 LSB  4
         130691232                                    2#111110010100011000010100000# MSB 26 LSB  5
        5489031744                              2#101000111001010111111101001000000# MSB 32 LSB  6
      230539333248                         2#11010110101101001101110000111010000000# MSB 37 LSB  7
     9682651996416                   2#10001100111001101011000010000110000100000000# MSB 43 LSB  8
   406671383849472              2#1011100011101110110001111010111111110101000000000# MSB 48 LSB  9
 17080198121677824         2#111100101011100101100110000101101111000110010000000000# MSB 53 LSB 10
717368321110468608   2#100111110100100110101010111111110000111010000110100000000000# MSB 59 LSB 11

ALGOL 68

Works with: ALGOL 68 version Revision 1 - one minor extension to language used - PRAGMA READ, similar to C's #include directive.
Works with: ALGOL 68G version Any - tested with release algol68g-2.3.5.

File: Template.Find_first_and_last_set_bit.a68

INT lbits width = UPB []BOOL(LBITS(2r0));

OP LWB = (BITS in x)INT: bits width - RUPB in x;

OP RUPB = (BITS in x)INT:
  ### 32 bit LWB Find Lower Set Bit using an unrolled loop ###
# Note: BITS ELEM 1 is actually numerically the Most Significant Bit!! #
  IF in x = 2r0 THEN 
    -1 # EXIT #
  ELSE
    BITS x := in x, out := 2r0;
    IF(x AND NOT 2r1111111111111111)/=2r0 THEN x := x SHR 16; out := out OR 2r10000 FI;
    IF(x AND NOT 2r11111111)        /=2r0 THEN x := x SHR  8; out := out OR 2r1000 FI;
    IF(x AND NOT 2r1111)            /=2r0 THEN x := x SHR  4; out := out OR 2r100 FI;
    IF(x AND NOT 2r11)              /=2r0 THEN x := x SHR  2; out := out OR 2r10 FI;
    IF(x AND NOT 2r1)               /=2r0 THEN                out := out OR 2r1 FI;
    ABS out # EXIT #
  FI;

OP LWB = (LBITS in x)INT: lbits width - RUPB in x;

OP RUPB = (LBITS in x)INT:
  ### Generalised Find Lower Set Bit using a loop ###
# Note: BITS ELEM 32 is actually numerically the Least Significant Bit!! #
  IF in x = 2r0 THEN 
    -1 # EXIT #
  ELSE
    LBITS x := in x;
    BITS
      out bit := BIN 1 SHL (bits width - LWB BIN lbits width),
      out := BIN 0;
    WHILE
      LBITS mask := NOT BIN (ABS (LONG 2r1 SHL ABS out bit) - 1);
      IF(x AND mask) /= 2r0 THEN 
        x := x SHR ABS out bit; 
        out := out OR out bit FI;
      out bit := out bit SHR 1;
  # WHILE # out bit /= 2r0 DO SKIP OD;
    ABS out # EXIT #
  FI;

OP UPB = (BITS in x)INT: bits width - RLWB in x;

OP RLWB = (BITS in x)INT:
  ### 32 bit Find Upper Set Bit using an unrolled loop ###
# Note: BITS ELEM 1 is actually numerically the Most Significant Bit!! #
  IF in x = 2r0 THEN 
    0 # EXIT #
  ELSE
    BITS x := in x, out := 2r0;
    IF(x AND 2r1111111111111111)=2r0 THEN x := x SHR 16; out := out OR 2r10000 FI;
    IF(x AND 2r11111111)        =2r0 THEN x := x SHR  8; out := out OR 2r1000 FI;
    IF(x AND 2r1111)            =2r0 THEN x := x SHR  4; out := out OR 2r100 FI;
    IF(x AND 2r11)              =2r0 THEN x := x SHR  2; out := out OR 2r10 FI;
    IF(x AND 2r1)               =2r0 THEN                out := out OR 2r1 FI;
    ABS out # EXIT #
  FI;

OP UPB = (LBITS in x)INT: lbits width - RLWB in x;

OP RLWB = (LBITS in x)INT:
  ### Generalised Find Upper Set Bit using a loop ###
# Note: BITS ELEM 1 is actually numerically the Most Significant Bit!! #
  IF in x = 2r0 THEN 
    0 # EXIT #
  ELSE
    LBITS x := in x;
    BITS
      out bit := BIN 1 SHL (bits width - LWB BIN lbits width),
      out := BIN 0;
    WHILE
      LBITS mask := BIN (ABS (LONG 2r1 SHL ABS out bit) - 1);
      IF(x AND mask) = 2r0 THEN 
        x := x SHR ABS out bit; 
        out := out OR out bit FI;
      out bit := out bit SHR 1;
  # WHILE # out bit /= 2r0 DO SKIP OD;
    ABS out # EXIT #
  FI;

File: test.Find_first_and_last_set_bit.a68

#!/usr/local/bin/a68g --script #

MODE LBITS = LONG BITS;
PR READ "Template.Find_first_and_last_set_bit.a68" PR

INT bits of prod;
FORMAT header fmt = $g 36k"|RLWB|RUPB|Bits"l$;
FORMAT row fmt0 = $g(-35)"|"2(g(-3)" |"),2rd l$;
FORMAT row fmt  = $g(-35)"|"2(g(-3)" |"),2rn(bits of prod+1)d l$;

test int:(
  printf((header fmt, "INT: find first & last set bit"));
  INT prod := 0;
  
  # test case 0 #
  prod := 0; bits of prod := RUPB BIN prod;
  printf((row fmt0, prod, RLWB BIN prod, RUPB BIN prod, BIN prod));
  
  prod := 1; # test case 1 etc ... #
  INT zoom := 2 * 3 * 7;
  WHILE
    bits of prod := RUPB BIN prod;
    printf((row fmt, prod, RLWB BIN prod, RUPB BIN prod, BIN prod));
# WHILE # prod <=      max int / zoom DO
    prod *:= zoom
  OD
);

test long int:(
  printf(($l$,header fmt, "LONG INT:"));
  LONG INT prod := 0;
  
  # test case 0 #
  prod := 0; bits of prod := RUPB BIN prod;
  printf((row fmt0, prod, RLWB BIN prod, RUPB BIN prod, BIN prod));
  
  prod := 1; # test case 1 etc ... #
  INT zoom := 2 * 3 * 7 * 31;
  WHILE
    bits of prod := RUPB BIN prod;
    printf((row fmt, prod, RLWB BIN prod, RUPB BIN prod, BIN prod));
# WHILE # prod <= long max int / zoom DO
    prod *:= zoom
  OD
)
Output:
INT: find first & last set bit     |RLWB|RUPB|Bits
                                  0|  0 | -1 |0
                                  1|  0 |  0 |1
                                 42|  1 |  5 |101010
                               1764|  2 | 10 |11011100100
                              74088|  3 | 16 |10010000101101000
                            3111696|  4 | 21 |1011110111101100010000
                          130691232|  5 | 26 |111110010100011000010100000

LONG INT:                          |RLWB|RUPB|Bits
                                  0|  0 | -1 |0
                                  1|  0 |  0 |1
                               1302|  1 | 10 |10100010110
                            1695204|  2 | 20 |110011101110111100100
                         2207155608|  3 | 31 |10000011100011101000010110011000
                      2873716601616|  4 | 41 |101001110100010110110110110111001100010000
                   3741579015304032|  5 | 51 |1101010010101111001001000000000110110011001101100000
                4871535877925849664|  6 | 62 |100001110011011001011000001001000001010010101110100101001000000
             6342739713059456262528|  7 | 72 |1010101111101011100110010001000111100000010010111111100111010000110000000
          8258247106403412053811456|  8 | 82 |11011010100110000000111100100000001110101011000010011010001000101110110000100000000
      10752237732537242494062515712|  9 | 93 |1000101011111000001010111001110110111101010011111100010111111101101100111001110101011000000000
   13999413527763489727269395457024| 10 |103 |10110000101100101000101101110101000100000011010011101110001111100001001111100000100011110110010000000000
18227236413148063624904752885045248| 11 |113 |111000001010101100000100010100010101100000011011010011001110101111101110010001100000011001010001101001100000000000

Arturo

msb: function [x]-> dec size as.binary x
lsb: function [x]-> msb and x neg x

loop 0..5 'i [
    x: 42 ^ i
    print [pad to :string x 10 "-->" "MSB:" pad.right to :string (msb x) 2 "- LSB:" lsb x]
]

print ""

loop 0..5 'i [
    x: 1302 ^ i
    print [pad to :string x 17 "-->" "MSB:" pad.right to :string (msb x) 2 "- LSB:" lsb x]
]
Output:
         1 --> MSB: 0  - LSB: 0 
        42 --> MSB: 5  - LSB: 1 
      1764 --> MSB: 10 - LSB: 2 
     74088 --> MSB: 16 - LSB: 3 
   3111696 --> MSB: 21 - LSB: 4 
 130691232 --> MSB: 26 - LSB: 5 

                1 --> MSB: 0  - LSB: 0 
             1302 --> MSB: 10 - LSB: 1 
          1695204 --> MSB: 20 - LSB: 2 
       2207155608 --> MSB: 31 - LSB: 3 
    2873716601616 --> MSB: 41 - LSB: 4 
 3741579015304032 --> MSB: 51 - LSB: 5

AutoHotkey

loop, 12{
	First := Last := ""
	n:=42**(A_Index-1)
	while (n>v)
		if (n&v := 2**(A_Index-1))
			First := First ? First : A_Index-1 , Last := A_Index-1
	Res .= 42 "^" A_Index-1 " --> First : " First " , Last : " Last "`n"
}
MsgBox % Res
Output:
42^0 --> First : 0 , Last : 0
42^1 --> First : 1 , Last : 5
42^2 --> First : 2 , Last : 10
42^3 --> First : 3 , Last : 16
42^4 --> First : 4 , Last : 21
42^5 --> First : 5 , Last : 26
42^6 --> First : 6 , Last : 32
42^7 --> First : 7 , Last : 37
42^8 --> First : 8 , Last : 43
42^9 --> First : 9 , Last : 48
42^10 --> First : 10 , Last : 53
42^11 --> First : 11 , Last : 59

BASIC256

print "INT: find first & last set bit"
p = 1
for j = 0 to 5
	print rjust(p,9); " "; rjust(ToBinary(p),29,0); " MSB: "; rjust(MSB(p),2); " LSB: "; rjust(LSB(p),2)
	p *= 42
next j
print
end

function MSB(i)
	return length(ToBinary(i))-1
end function

function LSB(i)
	return (i & -i)
end function
Output:
INT: find first & last set bit
        1 00000000000000000000000000001 MSB:  0 LSB:  1
       42 00000000000000000000000101010 MSB:  5 LSB:  2
     1764 00000000000000000011011100100 MSB: 10 LSB:  4
    74088 00000000000010010000101101000 MSB: 16 LSB:  8
  3111696 00000001011110111101100010000 MSB: 21 LSB: 16
130691232 00111110010100011000010100000 MSB: 26 LSB: 32


C

#include <stdio.h>
#include <stdint.h>

uint32_t msb32(uint32_t n)
{
	uint32_t b = 1;
	if (!n) return 0;

#define step(x) if (n >= ((uint32_t)1) << x) b <<= x, n >>= x
	step(16); step(8); step(4); step(2); step(1);
#undef step
	return b;
}

int msb32_idx(uint32_t n)
{
	int b = 0;
	if (!n) return -1;

#define step(x) if (n >= ((uint32_t)1) << x) b += x, n >>= x
	step(16); step(8); step(4); step(2); step(1);
#undef step
	return b;
}

#define lsb32(n) ( (uint32_t)(n) & -(int32_t)(n) )

/* finding the *position* of the least significant bit
   rarely makes sense, so we don't put much effort in it*/
inline int lsb32_idx(uint32_t n) { return msb32_idx(lsb32(n)); }

int main()
{
	int32_t n;
	int i;

	for (i = 0, n = 1; ; i++, n *= 42) {
		printf("42**%d = %10d(x%08x): M x%08x(%2d) L x%03x(%2d)\n",
			i, n, n,
			msb32(n), msb32_idx(n),
			lsb32(n), lsb32_idx(n));

		if (n >= INT32_MAX / 42) break;
	}

	return 0;
}
Output:
42**0 =          1(x00000001): M x00000001( 0) L x001( 0)
42**1 =         42(x0000002a): M x00000020( 5) L x002( 1)
42**2 =       1764(x000006e4): M x00000400(10) L x004( 2)
42**3 =      74088(x00012168): M x00010000(16) L x008( 3)
42**4 =    3111696(x002f7b10): M x00200000(21) L x010( 4)
42**5 =  130691232(x07ca30a0): M x04000000(26) L x020( 5)

Where "x###" are in base 16

GCC extension

Works with: GCC
#include <stdio.h>
#include <limits.h>

int msb_int(unsigned int x) {
	int ret = sizeof(unsigned int) * CHAR_BIT - 1;
	return x ? ret - __builtin_clz(x) : ret;
}

int msb_long(unsigned long x) {
	int ret = sizeof(unsigned long) * CHAR_BIT - 1;
	return x ? ret - __builtin_clzl(x) : ret;
}

int msb_longlong(unsigned long long x) {
	int ret = sizeof(unsigned long long) * CHAR_BIT - 1;
	return x ? ret - __builtin_clzll(x) : ret;
}

#define lsb_int(x)	(__builtin_ffs(x) - 1)
#define lsb_long(x)	(__builtin_ffsl(x) - 1)
#define lsb_longlong(x) (__builtin_ffsll(x) - 1)

int main()
{
	int i;

        printf("int:\n");
	unsigned int n1;
	for (i = 0, n1 = 1; ; i++, n1 *= 42) {
		printf("42**%d = %10u(x%08x): M %2d L %2d\n",
			i, n1, n1,
			msb_int(n1),
			lsb_int(n1));

		if (n1 >= UINT_MAX / 42) break;
	}

        printf("long:\n");
	unsigned long n2;
	for (i = 0, n2 = 1; ; i++, n2 *= 42) {
		printf("42**%02d = %20lu(x%016lx): M %2d L %2d\n",
			i, n2, n2,
			msb_long(n2),
			lsb_long(n2));

		if (n2 >= ULONG_MAX / 42) break;
	}

	return 0;
}
Output:
int:
42**0 =          1(x00000001): M  0 L  0
42**1 =         42(x0000002a): M  5 L  1
42**2 =       1764(x000006e4): M 10 L  2
42**3 =      74088(x00012168): M 16 L  3
42**4 =    3111696(x002f7b10): M 21 L  4
42**5 =  130691232(x07ca30a0): M 26 L  5
long:
42**00 =                    1(x0000000000000001): M  0 L  0
42**01 =                   42(x000000000000002a): M  5 L  1
42**02 =                 1764(x00000000000006e4): M 10 L  2
42**03 =                74088(x0000000000012168): M 16 L  3
42**04 =              3111696(x00000000002f7b10): M 21 L  4
42**05 =            130691232(x0000000007ca30a0): M 26 L  5
42**06 =           5489031744(x00000001472bfa40): M 32 L  6
42**07 =         230539333248(x00000035ad370e80): M 37 L  7
42**08 =        9682651996416(x000008ce6b086100): M 43 L  8
42**09 =      406671383849472(x000171dd8f5fea00): M 48 L  9
42**10 =    17080198121677824(x003cae5985bc6400): M 53 L 10
42**11 =   717368321110468608(x09f49aaff0e86800): M 59 L 11

Where "x###" are in base 16

D

(This task is not complete, the second part will be added later.)

import std.stdio, core.bitop, std.bigint;

void main() {
    enum size_t test = 42;
    for (size_t i = 0; true; i++) {
        immutable size_t x = test ^^ i;
        if (x != BigInt(test) ^^ i)
            break;
        writefln("%18d %0*b MSB: %2d LSB: %2d",
                 x, size_t.sizeof * 8, x, bsr(x), bsf(x));
    }
}
Output:

On a 32 bit system:

                 1 00000000000000000000000000000001 MSB:  0 LSB:  0
                42 00000000000000000000000000101010 MSB:  5 LSB:  1
              1764 00000000000000000000011011100100 MSB: 10 LSB:  2
             74088 00000000000000010010000101101000 MSB: 16 LSB:  3
           3111696 00000000001011110111101100010000 MSB: 21 LSB:  4
         130691232 00000111110010100011000010100000 MSB: 26 LSB:  5

On a 64 bit system:

                 1 0000000000000000000000000000000000000000000000000000000000000001 MSB:  0 LSB:  0
                42 0000000000000000000000000000000000000000000000000000000000101010 MSB:  5 LSB:  1
              1764 0000000000000000000000000000000000000000000000000000011011100100 MSB: 10 LSB:  2
             74088 0000000000000000000000000000000000000000000000010010000101101000 MSB: 16 LSB:  3
           3111696 0000000000000000000000000000000000000000001011110111101100010000 MSB: 21 LSB:  4
         130691232 0000000000000000000000000000000000000111110010100011000010100000 MSB: 26 LSB:  5
        5489031744 0000000000000000000000000000000101000111001010111111101001000000 MSB: 32 LSB:  6
      230539333248 0000000000000000000000000011010110101101001101110000111010000000 MSB: 37 LSB:  7
     9682651996416 0000000000000000000010001100111001101011000010000110000100000000 MSB: 43 LSB:  8
   406671383849472 0000000000000001011100011101110110001111010111111110101000000000 MSB: 48 LSB:  9
 17080198121677824 0000000000111100101011100101100110000101101111000110010000000000 MSB: 53 LSB: 10
717368321110468608 0000100111110100100110101010111111110000111010000110100000000000 MSB: 59 LSB: 11

Delphi

Thanks for Rudy Velthuis for Velthuis.BigIntegers[1].

program Find_first_and_last_set_bit_of_a_long_integer;

{$APPTYPE CONSOLE}

uses
  System.SysUtils,
  Velthuis.BigIntegers;

function bsf(x: string): Integer;
begin
  Result := x.Length - x.LastIndexOf('1') - 1;
end;

function bsr(x: string): Integer;
begin
  Result := x.Length - x.IndexOf('1') - 1;
end;

var
  i: integer;
  value: BigInteger;
  binary: string;

begin
  for i := 0 to 11 do
  begin
    value := BigInteger.Pow(42, i);
    binary := value.ToBinaryString.PadLeft(64, '0');

    Writeln(format('%18s %60s MSB: %2d LSB: %2d', [value.ToString, binary, bsr(binary),
      bsf(binary)]));
  end;

  readln;
end.
Output:
                 1 0000000000000000000000000000000000000000000000000000000000000001 MSB:  0 LSB:  0
                42 0000000000000000000000000000000000000000000000000000000000101010 MSB:  5 LSB:  1
              1764 0000000000000000000000000000000000000000000000000000011011100100 MSB: 10 LSB:  2
             74088 0000000000000000000000000000000000000000000000010010000101101000 MSB: 16 LSB:  3
           3111696 0000000000000000000000000000000000000000001011110111101100010000 MSB: 21 LSB:  4
         130691232 0000000000000000000000000000000000000111110010100011000010100000 MSB: 26 LSB:  5
        5489031744 0000000000000000000000000000000101000111001010111111101001000000 MSB: 32 LSB:  6
      230539333248 0000000000000000000000000011010110101101001101110000111010000000 MSB: 37 LSB:  7
     9682651996416 0000000000000000000010001100111001101011000010000110000100000000 MSB: 43 LSB:  8
   406671383849472 0000000000000001011100011101110110001111010111111110101000000000 MSB: 48 LSB:  9
 17080198121677824 0000000000111100101011100101100110000101101111000110010000000000 MSB: 53 LSB: 10
717368321110468608 0000100111110100100110101010111111110000111010000110100000000000 MSB: 59 LSB: 11


Forth

Works with: gforth version 0.7.3
: bin. base @ 2 base ! swap u. base ! ;

: lwb ( n -- u )
  0 swap
  begin
  dup 1 and 0= while
    1 rshift
    swap 1+ swap
  repeat drop ;

: upb ( n -- u )
  -1 swap
  begin
  dup 0<> while
    1 rshift
    swap 1+ swap
  repeat drop ;

: Find_first_and_last_set_bit_of_a_long_integer
  1 6 0 do
    dup dup dup dup
    cr 10 .r ." : " ." MSB:" upb 2 .r ." , LSB:" lwb 2 .r ." , %" bin.
    42 *
  loop drop ;

Find_first_and_last_set_bit_of_a_long_integer
Output:
         1: MSB: 0, LSB: 0, %1 
        42: MSB: 5, LSB: 1, %101010 
      1764: MSB:10, LSB: 2, %11011100100 
     74088: MSB:16, LSB: 3, %10010000101101000 
   3111696: MSB:21, LSB: 4, %1011110111101100010000 
 130691232: MSB:26, LSB: 5, %111110010100011000010100000  ok


Fortran

Since the Fortran 2008 standard, the language has LEADZ and TRAILZ intrinsic functions that yield respectively the number of leading (i.e. HSB) and trailing (LSB) zero bits. This gives an immediate solution to the task.

program bits
    implicit none
    integer :: n = 1, i

    do i = 1, 6
        print "(B32,2(' ',I2))", n, trailz(n), 31 - leadz(n)
        n = 42 * n
    end do
end program
Output:
                               1  0  0
                          101010  1  5
                     11011100100  2 10
               10010000101101000  3 16
          1011110111101100010000  4 21
     111110010100011000010100000  5 26

By divide and conquer

Even though Fortran has intrinsic functions, and modern machines have special instructions for the task, it still seems worthwhile to write out functions.

One thing that is evident, if you study the various ways to implement these functions, is that Fortran is ill suited, in a way most high-level languages have been ill suited since the beginning of time: they do not have built in unsigned integers with overflow explicitly allowed. ISO standard C does (and thus so does ATS, because its integers are exactly C integers). But this is unusual, outside of C and its relatives, and (I would imagine) owes to C's origins as a replacement for assembly language.

! As was already pointed out, Fortran has intrinsic functions that
! should compile to efficient code, such as a single machine
! instruction. But it seems profitable to have written implementations
! according to the task description.

! Here, by the way, is a page devoted to the topic of finding the LS1B
! and MS1B positions:
! https://www.chessprogramming.org/index.php?title=BitScan&oldid=22495#With_separated_LS1B

! I am uncertain what the "lwb" and "upb" are supposed to mean, but I
! imagine it is to isolate the bit. I do this below using
! bit-twiddling methods, *before* doing binary searches to find the
! positions of the bits.

module bit_thingies_for_rosetta_code

  ! INT64 is the largest integer kind standardized in ISO_FORTRAN_ENV,
  ! although 128-bit integers are available with gfortran on AMD64. I
  ! shall stick with INT64; the principles do not differ.
  use, intrinsic :: iso_fortran_env, only: int64

  implicit none

  integer(kind = int64), parameter :: most_negative = ishft (1_int64, 63)

  integer(kind = int64), parameter :: mask1 = &
       & int (b'1010101010101010101010101010101010101010101010101010101010101010', &
       &      kind = int64)
  integer(kind = int64), parameter :: mask2 = &
       & int (b'1100110011001100110011001100110011001100110011001100110011001100', &
       &      kind = int64)
  integer(kind = int64), parameter :: mask3 = &
       & int (b'1111000011110000111100001111000011110000111100001111000011110000', &
       &      kind = int64)
  integer(kind = int64), parameter :: mask4 = &
       & int (b'1111111100000000111111110000000011111111000000001111111100000000', &
       &      kind = int64)
  integer(kind = int64), parameter :: mask5 = &
       & int (b'1111111111111111000000000000000011111111111111110000000000000000', &
       &      kind = int64)
  integer(kind = int64), parameter :: mask6 = &
       & int (b'1111111111111111111111111111111100000000000000000000000000000000', &
       &      kind = int64)

contains

  ! LS1B-position by binary search. This method is MUCH improved by
  ! first isolating the least significant 1-bit, so I do that. This
  ! action makes the masks more effective.
  elemental function rlwb (n) result (i)
    integer(kind = int64), value :: n
    integer :: i

    if (n == most_negative) then
       !
       ! With the most negative two's complement number, one cannot
       ! trust Fortran to do arithmetic as one intends. Thus this
       ! branch. (There would be no such problem with *unsigned*
       ! integers in C; these are required by the standard to overflow
       ! and underflow freely.)
       !
       ! If you take into account the task's restriction to positive
       ! integers, then of course this case never occurs, and you can
       ! leave out the branch.
       !
       i = 63
    else
       ! Isolate the least significant 1-bit. This method is specific
       ! for two's complement. Your platform is very unlikely not to
       ! be two's complement.
       n = iand (n, -n)

       i = 0_int64
       if (iand (n, not (mask6)) == 0) i = 32_int64
       if (iand (n, not (mask5)) == 0) i = i + 16_int64
       if (iand (n, not (mask4)) == 0) i = i + 8_int64
       if (iand (n, not (mask3)) == 0) i = i + 4_int64
       if (iand (n, not (mask2)) == 0) i = i + 2_int64
       if (iand (n, not (mask1)) == 0) i = i + 1_int64
    end if
  end function rlwb

  ! MS1B-position by binary search. This method is MUCH improved by
  ! first isolating the most significant 1-bit, so I do that. This
  ! action makes the masks more effective.
  elemental function rupb (n) result (i)
    integer(kind = int64), value :: n
    integer :: i

    if (ibits (n, 63, 1) /= 0) then
       ! The task restricts itself to positive integers, but I shall
       ! do a branch for negative numbers.
       i = 0_int64
    else if (ibits (n, 62, 1) /= 0) then
       ! Also, in Fortran one cannot safely add one to every 63-bit
       ! number, so another special branch.
       i = 1_int64
    else
       ! Fill all bits to the right of the MS1B.
       n = ior (n, ishft (n, -1))
       n = ior (n, ishft (n, -2))
       n = ior (n, ishft (n, -4))
       n = ior (n, ishft (n, -8))
       n = ior (n, ishft (n, -16))
       n = ior (n, ishft (n, -32))

       ! Isolate the most significant 1-bit.
       n = ishft (n + 1, -1)

       i = 0_int64
       if (iand (n, mask6) /= 0) i = 32_int64
       if (iand (n, mask5) /= 0) i = i + 16_int64
       if (iand (n, mask4) /= 0) i = i + 8_int64
       if (iand (n, mask3) /= 0) i = i + 4_int64
       if (iand (n, mask2) /= 0) i = i + 2_int64
       if (iand (n, mask1) /= 0) i = i + 1_int64
    end if
  end function rupb

end module bit_thingies_for_rosetta_code

program find_set_bits
  use, intrinsic :: iso_fortran_env, only: int64
  use, non_intrinsic :: bit_thingies_for_rosetta_code
  implicit none

  integer :: i
  integer(kind = int64) :: n

  write (*, '(A70)') "Using intrinsic functions TRAILZ and LEADZ"
  n = 1_int64
  do i = 0, 11
     write (*, '(B0.64, 2(" ", I2))') n, trailz (n), 63 - leadz (n)
     n = 42_int64 * n
  end do

  write (*, '()')

  write (*, '(A70)') "Using binary search"
  n = 1_int64
  do i = 0, 11
     write (*, '(B0.64, 2(" ", I2))') n, rlwb (n), rupb (n)
     n = 42_int64 * n
  end do

end program find_set_bits
Output:
$ gfortran -std=f2018 find_set_bits.f90 && ./a.out
                            Using intrinsic functions TRAILZ and LEADZ
0000000000000000000000000000000000000000000000000000000000000001  0  0
0000000000000000000000000000000000000000000000000000000000101010  1  5
0000000000000000000000000000000000000000000000000000011011100100  2 10
0000000000000000000000000000000000000000000000010010000101101000  3 16
0000000000000000000000000000000000000000001011110111101100010000  4 21
0000000000000000000000000000000000000111110010100011000010100000  5 26
0000000000000000000000000000000101000111001010111111101001000000  6 32
0000000000000000000000000011010110101101001101110000111010000000  7 37
0000000000000000000010001100111001101011000010000110000100000000  8 43
0000000000000001011100011101110110001111010111111110101000000000  9 48
0000000000111100101011100101100110000101101111000110010000000000 10 53
0000100111110100100110101010111111110000111010000110100000000000 11 59

                                                   Using binary search
0000000000000000000000000000000000000000000000000000000000000001  0  0
0000000000000000000000000000000000000000000000000000000000101010  1  5
0000000000000000000000000000000000000000000000000000011011100100  2 10
0000000000000000000000000000000000000000000000010010000101101000  3 16
0000000000000000000000000000000000000000001011110111101100010000  4 21
0000000000000000000000000000000000000111110010100011000010100000  5 26
0000000000000000000000000000000101000111001010111111101001000000  6 32
0000000000000000000000000011010110101101001101110000111010000000  7 37
0000000000000000000010001100111001101011000010000110000100000000  8 43
0000000000000001011100011101110110001111010111111110101000000000  9 48
0000000000111100101011100101100110000101101111000110010000000000 10 53
0000100111110100100110101010111111110000111010000110100000000000 11 59

FreeBASIC

Translation of: Python
Function MSB(i As Integer) As Integer
    Return Len(Bin(i))-1
End Function

Function LSB(i As Integer) As Integer
    Return MSB(i And -i)
End Function

Dim As Integer p = 1
For j As Integer = 0 To 11
    Print Using "################## & MSB: ## LSB: ##"; p; Bin(p,64); MSB(p); LSB(p)
    p *= 42
Next j
Sleep
Output:
                 1 0000000000000000000000000000000000000000000000000000000000000001 MSB:  0 LSB:  0
                42 0000000000000000000000000000000000000000000000000000000000101010 MSB:  5 LSB:  1
              1764 0000000000000000000000000000000000000000000000000000011011100100 MSB: 10 LSB:  2
             74088 0000000000000000000000000000000000000000000000010010000101101000 MSB: 16 LSB:  3
           3111696 0000000000000000000000000000000000000000001011110111101100010000 MSB: 21 LSB:  4
         130691232 0000000000000000000000000000000000000111110010100011000010100000 MSB: 26 LSB:  5
        5489031744 0000000000000000000000000000000101000111001010111111101001000000 MSB: 32 LSB:  6
      230539333248 0000000000000000000000000011010110101101001101110000111010000000 MSB: 37 LSB:  7
     9682651996416 0000000000000000000010001100111001101011000010000110000100000000 MSB: 43 LSB:  8
   406671383849472 0000000000000001011100011101110110001111010111111110101000000000 MSB: 48 LSB:  9
 17080198121677824 0000000000111100101011100101100110000101101111000110010000000000 MSB: 53 LSB: 10
717368321110468608 0000100111110100100110101010111111110000111010000110100000000000 MSB: 59 LSB: 11


FutureBasic

local fn IntegerToBinaryStr( x as NSInteger ) as CFStringRef
  CFStringRef resultStr = @""
  while ( x )
    resultStr = fn StringByAppendingString( fn StringWithFormat( @"%lu", x && 1 ), resultStr )
    x = x >> 1
  wend
end fn = resultStr

local fn FirstAndLastBit
  NSInteger i, p = 1
  for i = 0 to 11
    CFStringRef binaryStr = fn IntegerToBinaryStr(p)
    printf @"%20lld %-62s  MSB: %2lld  LSB: %2lld", p, fn StringUTF8String( binaryStr ), len( binaryStr ) - 1, i
    p = p * 42
  next
end fn

fn FirstAndLastBit

HandleEvents

{{output}

                   1 1                                                               MSB:  0  LSB:  0
                  42 101010                                                          MSB:  5  LSB:  1
                1764 11011100100                                                     MSB: 10  LSB:  2
               74088 10010000101101000                                               MSB: 16  LSB:  3
             3111696 1011110111101100010000                                          MSB: 21  LSB:  4
           130691232 111110010100011000010100000                                     MSB: 26  LSB:  5
          5489031744 101000111001010111111101001000000                               MSB: 32  LSB:  6
        230539333248 11010110101101001101110000111010000000                          MSB: 37  LSB:  7
       9682651996416 10001100111001101011000010000110000100000000                    MSB: 43  LSB:  8
     406671383849472 1011100011101110110001111010111111110101000000000               MSB: 48  LSB:  9
   17080198121677824 111100101011100101100110000101101111000110010000000000          MSB: 53  LSB: 10
  717368321110468608 100111110100100110101010111111110000111010000110100000000000    MSB: 59  LSB: 11


Go

Translation of: ALGOL 68
package main

import (
    "fmt"
    "math/big"
)

const (
    mask0, bit0 = (1 << (1 << iota)) - 1, 1 << iota
    mask1, bit1
    mask2, bit2
    mask3, bit3
    mask4, bit4
    mask5, bit5
)

func rupb(x uint64) (out int) {
    if x == 0 {
        return -1
    }
    if x&^mask5 != 0 {
        x >>= bit5
        out |= bit5
    }
    if x&^mask4 != 0 {
        x >>= bit4
        out |= bit4
    }
    if x&^mask3 != 0 {
        x >>= bit3
        out |= bit3
    }
    if x&^mask2 != 0 {
        x >>= bit2
        out |= bit2
    }
    if x&^mask1 != 0 {
        x >>= bit1
        out |= bit1
    }
    if x&^mask0 != 0 {
        out |= bit0
    }
    return
}

func rlwb(x uint64) (out int) {
    if x == 0 {
        return 0
    }
    if x&mask5 == 0 {
        x >>= bit5
        out |= bit5
    }
    if x&mask4 == 0 {
        x >>= bit4
        out |= bit4
    }
    if x&mask3 == 0 {
        x >>= bit3
        out |= bit3
    }
    if x&mask2 == 0 {
        x >>= bit2
        out |= bit2
    }
    if x&mask1 == 0 {
        x >>= bit1
        out |= bit1
    }
    if x&mask0 == 0 {
        out |= bit0
    }
    return
}

// Big number versions of functions do not use the techniques of the ALGOL 68
// solution.  The big number version of rupb is trivial given one of the
// standard library functions, And for rlwb, I couldn't recommend shifting
// the whole input number when working with smaller numbers would do.
func rupbBig(x *big.Int) int {
    return x.BitLen() - 1
}

// Binary search, for the spirit of the task, but without shifting the input
// number x.  (Actually though, I don't recommend this either.  Linear search
// would be much faster.)
func rlwbBig(x *big.Int) int {
    if x.BitLen() < 2 {
        return 0
    }
    bit := uint(1)
    mask := big.NewInt(1)
    var ms []*big.Int
    var y, z big.Int
    for y.And(x, z.Lsh(mask, bit)).BitLen() == 0 {
        ms = append(ms, mask)
        mask = new(big.Int).Or(mask, &z)
        bit <<= 1
    }
    out := bit
    for i := len(ms) - 1; i >= 0; i-- {
        bit >>= 1
        if y.And(x, z.Lsh(ms[i], out)).BitLen() == 0 {
            out |= bit
        }
    }
    return int(out)
}

func main() {
    show()
    showBig()
}

func show() {
    fmt.Println("uint64:")
    fmt.Println("power              number  rupb  rlwb")
    const base = 42
    n := uint64(1)
    for i := 0; i < 12; i++ {
        fmt.Printf("%d^%02d %19d %5d %5d\n", base, i, n, rupb(n), rlwb(n))
        n *= base
    }
}

func showBig() {
    fmt.Println("\nbig numbers:")
    fmt.Println("  power                               number  rupb  rlwb")
    base := big.NewInt(1302)
    n := big.NewInt(1)
    for i := 0; i < 12; i++ {
        fmt.Printf("%d^%02d %36d %5d %5d\n", base, i, n, rupbBig(n), rlwbBig(n))
        n.Mul(n, base)
    }
}
Output:
uint64:
power              number  rupb  rlwb
42^00                   1     0     0
42^01                  42     5     1
42^02                1764    10     2
42^03               74088    16     3
42^04             3111696    21     4
42^05           130691232    26     5
42^06          5489031744    32     6
42^07        230539333248    37     7
42^08       9682651996416    43     8
42^09     406671383849472    48     9
42^10   17080198121677824    53    10
42^11  717368321110468608    59    11

big numbers:
  power                               number  rupb  rlwb
1302^00                                    1     0     0
1302^01                                 1302    10     1
1302^02                              1695204    20     2
1302^03                           2207155608    31     3
1302^04                        2873716601616    41     4
1302^05                     3741579015304032    51     5
1302^06                  4871535877925849664    62     6
1302^07               6342739713059456262528    72     7
1302^08            8258247106403412053811456    82     8
1302^09        10752237732537242494062515712    93     9
1302^10     13999413527763489727269395457024   103    10
1302^11  18227236413148063624904752885045248   113    11

Icon and Unicon

The task definition makes some assumptions that don't work in Icon/Unicon and are going to require some reinterpretation. In Icon/Unicon all integers appear to be implemented as a single common type. A specific implementation may or may not have large integers, but if it does they are essentially indistinguishable from regular integers. Given all of this, implementing "efficient" procedures for the platform word size without loops or recursion makes little sense.

Instead of this, to meet the spirit of the task, these lsb and msb routines are generalized to reduce the integer in blocks of bits and then zoom in on the desired bit by binary search (i.e. successively looking a blocks that are half the size again). The exponent for the initial power used to create the masks does not need to be itself a power of two. The xsb_initial procedure uses introspection to determine the word size of a basic integer type. This is used to build a mask that fits within the basic word size of the implementation. In this way we won't create unnecessary large integers through implicit type conversions.

link printf,hexcvt

procedure main()
   every B := [42,2^32-1] | [1302,2^64-1] do {
      base := B[1]
      lim  := B[2]
      fmt := sprintf("%%i^%%i = %%%is (x%%0%is) : MSB=%%s LSB=%%s\n",*lim,*hexstring(lim))
      every e := seq(0) do {
         if (i := base^e) > lim then break
         printf(fmt,base,e,i,hexstring(i),msb(i)|"-",lsb(i)|"-")
      }
   }
end

procedure msb(i)  #: return the most significant set bit index or fail
static mask
initial mask := xsb_initial()

   if i > 0 then {  
      b := 0
      every m := mask[j := 1 to *mask by 2] & r := mask[j+1] do {
         repeat {
            l := iand(i,m)
            i := ishift(i,r)
            if i = 0 then break            
            b -:= r
            }         
         i := l
         }
      return b
   }
end

procedure lsb(i)   #: return the least significant set bit index or fail
static mask
initial mask := xsb_initial()

   if i > 0 then {
      b := 0
      every m := mask[j := 1 to *mask by 2] & r := mask[j+1] do 
         until iand(i,m) > 0 do {
            i := ishift(i,r)
            b -:= r
            }
      return b
   }
end

procedure xsb_initial() #: setup tables for lsb/msb
static mask
initial {                                          # build
      a := &allocated                              # bigint affects allocation
      p := if 2^63 & a=&allocated then 63 else 31  # find wordsize-1
      p *:= 2                                      # adjust pre-loop 
      mask := []
      until (p := p / 2) = 0 do put(mask,2^p-1,-p) # list of masks and shifts
   }
   return mask                                     # return pre-built data
end

printf.icn provides formatting hexcvt.icn provides hexstring

Output:
42^0 =          1 (x00000001) : MSB=0 LSB=0
42^1 =         42 (x0000002A) : MSB=5 LSB=1
42^2 =       1764 (x000006E4) : MSB=10 LSB=2
42^3 =      74088 (x00012168) : MSB=16 LSB=3
42^4 =    3111696 (x002F7B10) : MSB=21 LSB=4
42^5 =  130691232 (x07CA30A0) : MSB=26 LSB=5
1302^0 =                    1 (x0000000000000001) : MSB=0 LSB=0
1302^1 =                 1302 (x0000000000000516) : MSB=10 LSB=1
1302^2 =              1695204 (x000000000019DDE4) : MSB=20 LSB=2
1302^3 =           2207155608 (x00000000838E8598) : MSB=31 LSB=3
1302^4 =        2873716601616 (x0000029D16DB7310) : MSB=41 LSB=4
1302^5 =     3741579015304032 (x000D4AF2401B3360) : MSB=51 LSB=5
1302^6 =  4871535877925849664 (x439B2C120A574A40) : MSB=62 LSB=6

J

Implementation:

lwb=: 0:
upb=: (#: i: 1:)"0
rlwb=: #@#:"0 - 1:
rupb=: rlwb - upb

Notes:

This implementation is agnostic to numeric storage format.

J's #: converts integers to bit lists.

lwb is the required name for the index of "first set bit in a binary value". This is always zero here. Here's why:

   #: 7
1 1 1
   #: 8
1 0 0 0
   #: 20
1 0 1 0 0
   #: 789
1 1 0 0 0 1 0 1 0 1
   #:123456789123456789123456789x
1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 1 1 0 0 0 1 0 1 0 1

The the first set bit in J's binary representation for a positive integer is always the first bit of that integer (there's an exception for zero, because it has no first set bit, but that's outside the domain of this task). That said, note that this would not hold for an arbitrary integer in a list of integers. But bit representations of lists of integers is outside the scope of this task.

And the index of the first bit will always be 0.

Example use:

   (,.lwb,.upb,.rlwb,.rupb) <.i.@>.&.(42&^.) 2^64
                 1 0  0  0  0
                42 0  4  5  1
              1764 0  8 10  2
             74088 0 13 16  3
           3111696 0 17 21  4
         130691232 0 21 26  5
        5489031744 0 26 32  6
      230539333248 0 30 37  7
     9682651996416 0 35 43  8
   406671383849472 0 39 48  9
 17080198121677824 0 43 53 10
717368321110468608 0 48 59 11

   (,.lwb,.upb,.rlwb,.rupb) i.@x:@>.&.(1302&^.) 2^128
                                     1 0   0   0  0
                                  1302 0   9  10  1
                               1695204 0  18  20  2
                            2207155608 0  28  31  3
                         2873716601616 0  37  41  4
                      3741579015304032 0  46  51  5
                   4871535877925849664 0  56  62  6
                6342739713059456262528 0  65  72  7
             8258247106403412053811456 0  74  82  8
         10752237732537242494062515712 0  84  93  9
      13999413527763489727269395457024 0  93 103 10
   18227236413148063624904752885045248 0 102 113 11
23731861809918778839625988256328912896 0 112 124 12

Note, in the above sentences, the rightmost part of each sentence is about generating an arbitrary sequence of values. The phrase <.i.@>.&.(42&^.) 2^64 generates the sequence 1 42 1764 74088 3111696 130691232 ... and the phrase i.@x:@>.&.(1302&^.) 2^128 generates the sequence 1 1302 1695204 2207155608 ...

The left part of each sentence uses the words we defined here, organizing their results as columns in a table.

Java

Works with: Java version 1.5+
public class FirstAndLastBits {

    public static long LSB(Long aNumber) {
		if ( aNumber <= 0 ) {
			throw new IllegalArgumentException("Number must be positive");
		}		
		return Long.numberOfTrailingZeros(aNumber);
	}
	
	public static long MSB(Long aNumber) {
		if ( aNumber <= 0 ) {
			throw new IllegalArgumentException("Number must be positive");
		}		
		return 63 - Long.numberOfLeadingZeros(aNumber);
	}
	
	public static long LSB(BigInteger aNumber) {
		if ( aNumber.signum() <= 0 ) {
			throw new IllegalArgumentException("Number must be positive");
		}		
		return aNumber.getLowestSetBit();
	}
	
	public static long MSB(BigInteger aNumber) {
		if ( aNumber.signum() <= 0 ) {
			throw new IllegalArgumentException("Number must be positive");
		}		
		return aNumber.bitLength() - 1;
	}
	
	public static void main(String[] aArgs) {
		Long powerOf42 = 1L;		
		for ( int i = 0; i <= 11; i++ ) {
			System.out.print(String.format("%-5s%-3s%s", "42 ^ ", i, " = ")); 
			System.out.print(String.format("%1$" + 64 + "s", Long.toBinaryString(powerOf42)).replace(" ", "0"));
			System.out.println(String.format("%s%-2s%s%-2s", " -> LSB: ", LSB(powerOf42), ", MSB: ", MSB(powerOf42)));
			powerOf42 *= 42;
		}
		System.out.println();
		
		BigInteger bigInteger1302 = BigInteger.valueOf(1302);
		BigInteger powerOf1302 = BigInteger.ONE;		
		for ( int i = 0; i <= 6; i++ ) {
			System.out.print(String.format("%-7s%s%s", "1302 ^ ", i, " = ")); 
			System.out.print(String.format("%1$" + 64 + "s", powerOf1302.toString(2)).replace(" ", "0"));
			String line = String.format("%s%-2s%s%-2s", " -> LSB: ", LSB(powerOf1302), ", MSB: ", MSB(powerOf1302));
			System.out.println(line);
			powerOf1302 = powerOf1302.multiply(bigInteger1302);
		}
	}

}
Output:
42 ^ 0   = 0000000000000000000000000000000000000000000000000000000000000001 -> LSB: 0 , MSB: 0 
42 ^ 1   = 0000000000000000000000000000000000000000000000000000000000101010 -> LSB: 1 , MSB: 5 
42 ^ 2   = 0000000000000000000000000000000000000000000000000000011011100100 -> LSB: 2 , MSB: 10
42 ^ 3   = 0000000000000000000000000000000000000000000000010010000101101000 -> LSB: 3 , MSB: 16
42 ^ 4   = 0000000000000000000000000000000000000000001011110111101100010000 -> LSB: 4 , MSB: 21
42 ^ 5   = 0000000000000000000000000000000000000111110010100011000010100000 -> LSB: 5 , MSB: 26
42 ^ 6   = 0000000000000000000000000000000101000111001010111111101001000000 -> LSB: 6 , MSB: 32
42 ^ 7   = 0000000000000000000000000011010110101101001101110000111010000000 -> LSB: 7 , MSB: 37
42 ^ 8   = 0000000000000000000010001100111001101011000010000110000100000000 -> LSB: 8 , MSB: 43
42 ^ 9   = 0000000000000001011100011101110110001111010111111110101000000000 -> LSB: 9 , MSB: 48
42 ^ 10  = 0000000000111100101011100101100110000101101111000110010000000000 -> LSB: 10, MSB: 53
42 ^ 11  = 0000100111110100100110101010111111110000111010000110100000000000 -> LSB: 11, MSB: 59

1302 ^ 0 = 0000000000000000000000000000000000000000000000000000000000000001 -> LSB: 0 , MSB: 0 
1302 ^ 1 = 0000000000000000000000000000000000000000000000000000010100010110 -> LSB: 1 , MSB: 10
1302 ^ 2 = 0000000000000000000000000000000000000000000110011101110111100100 -> LSB: 2 , MSB: 20
1302 ^ 3 = 0000000000000000000000000000000010000011100011101000010110011000 -> LSB: 3 , MSB: 31
1302 ^ 4 = 0000000000000000000000101001110100010110110110110111001100010000 -> LSB: 4 , MSB: 41
1302 ^ 5 = 0000000000001101010010101111001001000000000110110011001101100000 -> LSB: 5 , MSB: 51
1302 ^ 6 = 0100001110011011001011000001001000001010010101110100101001000000 -> LSB: 6 , MSB: 62

Julia

Works with: Julia version 0.6

Module:

module Bits

export lwb, upb

lwb(n) = trailing_zeros(n)
upb(n) = 8 * sizeof(n) - leading_zeros(n) - 1

end  # module Bits

Main:

using Main.Bits

# Using the built-in functions `leading_zeros` and `trailing_zeros`
println("# 64 bits integers:")
@printf(" %-18s | %-64s | %-2s | %-2s\n", "number", "bit representation", "lwb", "upb")
for n in 42 .^ (0:11)
    @printf(" %-18i | %-64s | %-3i | %-3i\n", n, bits(n), lwb(n), upb(n))
end

println("\n# 128 bits integers:")
@printf(" %-40s | %-2s | %-2s\n", "number", "lwb", "upb")
for n in int128"1302" .^ (0:11)
    @printf(" %-40i | %-3i | %-3i\n", n, lwb(n), upb(n))
end
Output:
# 64 bits integers:
 number             | bit representation                                               | lwb | upb
 1                  | 0000000000000000000000000000000000000000000000000000000000000001 | 0   | 0
 42                 | 0000000000000000000000000000000000000000000000000000000000101010 | 1   | 5
 1764               | 0000000000000000000000000000000000000000000000000000011011100100 | 2   | 10
 74088              | 0000000000000000000000000000000000000000000000010010000101101000 | 3   | 16
 3111696            | 0000000000000000000000000000000000000000001011110111101100010000 | 4   | 21
 130691232          | 0000000000000000000000000000000000000111110010100011000010100000 | 5   | 26
 5489031744         | 0000000000000000000000000000000101000111001010111111101001000000 | 6   | 32
 230539333248       | 0000000000000000000000000011010110101101001101110000111010000000 | 7   | 37
 9682651996416      | 0000000000000000000010001100111001101011000010000110000100000000 | 8   | 43
 406671383849472    | 0000000000000001011100011101110110001111010111111110101000000000 | 9   | 48
 17080198121677824  | 0000000000111100101011100101100110000101101111000110010000000000 | 10  | 53
 717368321110468608 | 0000100111110100100110101010111111110000111010000110100000000000 | 11  | 59

# 128 bits integers:
 number                                   | lwb | upb
 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

Kotlin

As I have no idea what the difference is supposed to be between lwb/uwb and rlwb/ruwb (unless the former numbers bits from left to right), I have only provided implementations of the latter - using Java/Kotlin library functions - which seem to be all that is needed in any case to perform the task in hand:

// version 1.1.0

import java.math.BigInteger

fun Long.rlwb() = when {
        this <= 0L -> throw IllegalArgumentException("Receiver must be positive")
        else       -> java.lang.Long.numberOfTrailingZeros(this)
    }

fun Long.ruwb() = when {
        this <= 0L -> throw IllegalArgumentException("Receiver must be positive")
        else       -> 63 - java.lang.Long.numberOfLeadingZeros(this)
    }

fun BigInteger.rlwb() = when {
        this <= BigInteger.ZERO -> throw IllegalArgumentException("Receiver must be positive")
        else                    -> this.lowestSetBit
    }

fun BigInteger.ruwb() = when {
        this <= BigInteger.ZERO -> throw IllegalArgumentException("Receiver must be positive")
        else                    -> this.bitLength() - 1
    }

fun main(args: Array<String>) {
    var pow42 = 1L
    for (i in 0..11) {
        print("42 ^ ${i.toString().padEnd(2)}  = ${pow42.toString(2).padStart(64, '0').padEnd(64)} -> ")
        println("MSB: %2d, LSB: %2d".format(pow42.ruwb(), pow42.rlwb()))
        pow42 *= 42L
    } 
    println()
    val big1302 = BigInteger.valueOf(1302)
    var pow1302 = BigInteger.ONE
    for (i in 0..6) {
        print("1302 ^ $i = ${pow1302.toString(2).padStart(64, '0').padEnd(64)} -> ")
        println("MSB: %2d, LSB: %2d".format(pow1302.ruwb(), pow1302.rlwb()))
        pow1302 *= big1302
    } 
}
Output:
42 ^ 0   = 0000000000000000000000000000000000000000000000000000000000000001 -> MSB:  0, LSB:  0
42 ^ 1   = 0000000000000000000000000000000000000000000000000000000000101010 -> MSB:  5, LSB:  1
42 ^ 2   = 0000000000000000000000000000000000000000000000000000011011100100 -> MSB: 10, LSB:  2
42 ^ 3   = 0000000000000000000000000000000000000000000000010010000101101000 -> MSB: 16, LSB:  3
42 ^ 4   = 0000000000000000000000000000000000000000001011110111101100010000 -> MSB: 21, LSB:  4
42 ^ 5   = 0000000000000000000000000000000000000111110010100011000010100000 -> MSB: 26, LSB:  5
42 ^ 6   = 0000000000000000000000000000000101000111001010111111101001000000 -> MSB: 32, LSB:  6
42 ^ 7   = 0000000000000000000000000011010110101101001101110000111010000000 -> MSB: 37, LSB:  7
42 ^ 8   = 0000000000000000000010001100111001101011000010000110000100000000 -> MSB: 43, LSB:  8
42 ^ 9   = 0000000000000001011100011101110110001111010111111110101000000000 -> MSB: 48, LSB:  9
42 ^ 10  = 0000000000111100101011100101100110000101101111000110010000000000 -> MSB: 53, LSB: 10
42 ^ 11  = 0000100111110100100110101010111111110000111010000110100000000000 -> MSB: 59, LSB: 11

1302 ^ 0 = 0000000000000000000000000000000000000000000000000000000000000001 -> MSB:  0, LSB:  0
1302 ^ 1 = 0000000000000000000000000000000000000000000000000000010100010110 -> MSB: 10, LSB:  1
1302 ^ 2 = 0000000000000000000000000000000000000000000110011101110111100100 -> MSB: 20, LSB:  2
1302 ^ 3 = 0000000000000000000000000000000010000011100011101000010110011000 -> MSB: 31, LSB:  3
1302 ^ 4 = 0000000000000000000000101001110100010110110110110111001100010000 -> MSB: 41, LSB:  4
1302 ^ 5 = 0000000000001101010010101111001001000000000110110011001101100000 -> MSB: 51, LSB:  5
1302 ^ 6 = 0100001110011011001011000001001000001010010101110100101001000000 -> MSB: 62, LSB:  6

Mathematica / Wolfram Language

MSB[n_]:=BitLength[n]-1
LSB[n_]:=IntegerExponent[n,2]
Map[{#,"MSB:",MSB[#],"LSB:",LSB[#]}&,
Join[NestList[(42*#)&,42,5],NestList[(1302*#)&,1302,5]]]//TableForm

42			MSB:	5	LSB:	1
1764			MSB:	10	LSB:	2
74088			MSB:	16	LSB:	3
3111696			MSB:	21	LSB:	4
130691232		MSB:	26	LSB:	5
5489031744		MSB:	32	LSB:	6
1302			MSB:	10	LSB:	1
1695204			MSB:	20	LSB:	2
2207155608		MSB:	31	LSB:	3
2873716601616		MSB:	41	LSB:	4
3741579015304032	MSB:	51	LSB:	5
4871535877925849664	MSB:	62	LSB:	6

PARI/GP

This version uses PARI. These work on arbitrary-length integers; the implementation for wordsize integers would be identical to C's.

long
msb(GEN n)
{
	return expi(n);
}

long
lsb(GEN n)
{
	return vali(n);
}

This version uses GP. It works on arbitrary-length integers; GP cannot directly work on wordsize integers except in a vecsmall.

lsb(n)=valuation(n,2);
msb(n)=#binary(n)-1;

Perl

This is simple and works with both native and bigint numbers.

sub msb {
  my ($n, $base) = (shift, 0);
  $base++ while $n >>= 1;
  $base;
}
sub lsb {
  my $n = shift;
  msb($n & -$n);
}

With large bigints, this is much faster (while as_bin seems expensive, every Math::BigInt transaction has large overhead, so Perl ops on the binary string ends up being a huge win vs. anything doing shifts, ands, compares, etc.). If we want one function to work on both types, we could easily modify this to make a Math::BigInt object if the input isn't already one.

sub bi_msb {         # Input should be a Math::BigInt object
  length(shift->as_bin)-3;
}

With native ints, this meets the task description assuming a 64-bit Perl:

sub msb64 {
  my($n, $pos) = (shift, 0);
  die "n must be a 64-bit integer)" if $n > ~0;
  no warnings 'portable';  # Remove this and adjust lines for 32-bit
  if (($n & 0xFFFFFFFF00000000) == 0) { $pos += 32; $n <<= 32; }
  if (($n & 0xFFFF000000000000) == 0) { $pos += 16; $n <<= 16; }
  if (($n & 0xFF00000000000000) == 0) { $pos +=  8; $n <<=  8; }
  if (($n & 0xF000000000000000) == 0) { $pos +=  4; $n <<=  4; }
  if (($n & 0xC000000000000000) == 0) { $pos +=  2; $n <<=  2; }
  if (($n & 0x8000000000000000) == 0) { $pos +=  1; $n <<=  1; }
  63-$pos;
}

Phix

machine-sized integers

There is nothing like this already built in, so we will roll our own, in low-level assembly.
Of course you would normally hide this sort of stuff out of sight, far away from the usual day-to-day code.

without javascript_semantics 
function msb(integer i)
    #ilASM{
            [32]
                mov eax,[i]
                bsr ecx,eax
                mov [i],ecx
            [64]
                mov rax,[i]
                bsr rcx,rax
                mov [i],rcx
          }
    return i
end function
 
function lsb(integer i)
    #ilASM{
            [32]
                mov eax,[i]
                bsf ecx,eax
                mov [i],ecx
            [64]
                mov rax,[i]
                bsf rcx,rax
                mov [i],rcx
          }
    return i
end function
 
atom p = 1
for i=0 to 11 do
    printf(1,"%18d %064b MSB:%2d LSB: %2d\n",{p,p,msb(p),lsb(p)})
    p *= 42
    if not integer(p) then exit end if
end for
Output:
                 1 0000000000000000000000000000000000000000000000000000000000000001 MSB: 0 LSB:  0
                42 0000000000000000000000000000000000000000000000000000000000101010 MSB: 5 LSB:  1
              1764 0000000000000000000000000000000000000000000000000000011011100100 MSB:10 LSB:  2
             74088 0000000000000000000000000000000000000000000000010010000101101000 MSB:16 LSB:  3
           3111696 0000000000000000000000000000000000000000001011110111101100010000 MSB:21 LSB:  4
         130691232 0000000000000000000000000000000000000111110010100011000010100000 MSB:26 LSB:  5
        5489031744 0000000000000000000000000000000101000111001010111111101001000000 MSB:32 LSB:  6
      230539333248 0000000000000000000000000011010110101101001101110000111010000000 MSB:37 LSB:  7
     9682651996416 0000000000000000000010001100111001101011000010000110000100000000 MSB:43 LSB:  8
   406671383849472 0000000000000001011100011101110110001111010111111110101000000000 MSB:48 LSB:  9
 17080198121677824 0000000000111100101011100101100110000101101111000110010000000000 MSB:53 LSB: 10
717368321110468608 0000100111110100100110101010111111110000111010000110100000000000 MSB:59 LSB: 11

On 32-bit the table stops at msb of 26. Since this task is specifically looking for bsf/bsr it is explicitly tagged as incompatible with pwa/p2js
Aside: power(42,5) [and above] are implemented on the FPU using fyl2x, f2xm1, and fscale; on 64-bit that results in 130691232 + ~7.3e-12 rather than the integer 130691232 exactly, whereas repeated multiplication by 42 as shown keeps it integer for longer.

mpfr/gmp

Library: Phix/mpfr
with javascript_semantics 
include mpfr.e
 
function rupbz(mpz n)
    integer res = mpz_sizeinbase(n,2)
    while res!=0 and mpz_tstbit(n,res)=0 do
        res -= 1
    end while
    return res
end function
 
function rlwbz(mpz n)
    return mpz_scan1(n,0)
end function
 
mpz n = mpz_init(1)
for i = 0 to 12 do
    printf(1,"1302^%02d %38s %5d %5d\n", {i,mpz_get_str(n), rupbz(n), rlwbz(n)})
    mpz_mul_si(n,n,1302)
end for
Output:
1302^00                                      1     0     0
1302^01                                   1302    10     1
1302^02                                1695204    20     2
1302^03                             2207155608    31     3
1302^04                          2873716601616    41     4
1302^05                       3741579015304032    51     5
1302^06                    4871535877925849664    62     6
1302^07                 6342739713059456262528    72     7
1302^08              8258247106403412053811456    82     8
1302^09          10752237732537242494062515712    93     9
1302^10       13999413527763489727269395457024   103    10
1302^11    18227236413148063624904752885045248   113    11
1302^12 23731861809918778839625988256328912896   124    12

In my tests the while loop in rupbz() always iterated precisely once, suggesting it merely converts a 1-based bit count to a 0-based bit number and could be replaced by -1
Note that under pwa/p2js this will quietly perform the very kind of looping the task specifically asks not for, but at least it works, and it does not do that under desktop/Phix.

PicoLisp

(de msb (N)
   (dec (length (bin (abs N)))) )

(de lsb (N)
   (length (stem (chop (bin N)) "1")) )

Test:

(for N (1 42 717368321110468608 291733167875766667063796853374976)
   (tab (33 6 6) N (lsb N) (msb N)) )
Output:
                                1     0     0
                               42     1     5
               717368321110468608    11    59
291733167875766667063796853374976    20   107

Python

Works with: Python version 2.7+ and 3.1+
def msb(x):
    return x.bit_length() - 1

def lsb(x):
    return msb(x & -x)

for i in range(6):
    x = 42 ** i
    print("%10d MSB: %2d LSB: %2d" % (x, msb(x), lsb(x)))

for i in range(6):
    x = 1302 ** i
    print("%20d MSB: %2d LSB: %2d" % (x, msb(x), lsb(x)))
Output:
         1 MSB:  0 LSB:  0
        42 MSB:  5 LSB:  1
      1764 MSB: 10 LSB:  2
     74088 MSB: 16 LSB:  3
   3111696 MSB: 21 LSB:  4
 130691232 MSB: 26 LSB:  5
                   1 MSB:  0 LSB:  0
                1302 MSB: 10 LSB:  1
             1695204 MSB: 20 LSB:  2
          2207155608 MSB: 31 LSB:  3
       2873716601616 MSB: 41 LSB:  4
    3741579015304032 MSB: 51 LSB:  5

Quackery

Quackery numbers are BigInts.

lsb returns -1 if passed 0, which has no bits set.

msb returns -1 if passed a negative number, which has no highest set bit, or 0, which has no bits set.

The reverse functions rlwb and rupb are not meaningful for BigInts as they do not have a rightmost bit. (Well, they do because memory is finite, but the size limit is not fixed.)

 [ dup 0 = iff
     [ 1 - ] done
   0 swap
   [ dup 1 & not while
     dip 1+
     1 >>
     again ]
   drop ]              is lsb ( n --> n )

 [ -1 swap
   [ dup 1 < not while
     dip 1+
     1 >>
     again ]
   drop ]              is msb ( n --> n )

  6 times
    [ 42 i^ ** dup echo
      say "  msb:"
      dup msb echo
      say "  lsb:"
      lsb echo cr ]
  cr
  6 times
    [ 1302 i^ ** dup echo
      say "  msb:"
      dup msb echo
      say "  lsb:"
      lsb echo cr ]
Output:
1  msb:0  lsb:0
42  msb:5  lsb:1
1764  msb:10  lsb:2
74088  msb:16  lsb:3
3111696  msb:21  lsb:4
130691232  msb:26  lsb:5

1  msb:0  lsb:0
1302  msb:10  lsb:1
1695204  msb:20  lsb:2
2207155608  msb:31  lsb:3
2873716601616  msb:41  lsb:4
3741579015304032  msb:51  lsb:5

Racket

#lang racket
(require rnrs/arithmetic/bitwise-6)
(for/list ([n 20])
  (define x (expt 42 n))
  (list n (bitwise-first-bit-set x) (- (integer-length x) 1)))
Output:
'((0 0 0)
  (1 1 5)
  (2 2 10)
  (3 3 16)
  (4 4 21)
  (5 5 26)
  (6 6 32)
  (7 7 37)
  (8 8 43)
  (9 9 48)
  (10 10 53)
  (11 11 59)
  (12 12 64)
  (13 13 70)
  (14 14 75)
  (15 15 80)
  (16 16 86)
  (17 17 91)
  (18 18 97)
  (19 19 102))

Raku

(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

REXX

Programming note:   The task's requirements state to compute powers of   1302   up the host's next "natural"   long   host word
size ···,   but for REXX, the "natural" size is a character string (indeed, the only thing REXX knows are character strings, numbers
are expressed as character strings),   so the output (below) was limited to four times the default size,   but the actual (practical)
limit may be around eight million bytes (for some REXXes).

REXX programmers have no need to know what the host's word size is,   as it is irrelevant.

A fair amount of coding was added to align and/or center the displaying of the numbers for the output.

/*REXX program finds the  first and last  set bit  of  "integer"  and  "long integer".  */
parse arg digs .                                 /*obtain optional argument from the CL.*/
if digs=='' |  digs==","  then digs= 40          /*Not specified?  Then use the default.*/
numeric digits max(9, digs);         d= digits() /*maybe use more precision for this run*/
@= '─';        @4= copies(@, 4)                  /*build parts of the separator line.   */
                                     != '│'      /*  "   part   "  "    output    "     */
       do cycle=1  for 2
       base= word(42 1302, cycle)                /*pick an integer for this cycle.      */
       @d= copies(@, d)                          /*build part of the separator line.    */
       call sep '─┬─'                            /*  ─┬─  is part of the separator line.*/
       say center(base'**n  (decimal)', d)  !  center("rlwb", 4)  !  center('rupb', 4)  !,
            right(base"**n  (binary)" , d+5)     /*display the title for the output.    */  
       call sep '─┼─'                            /*  ─┼─  is part of the separator line.*/
                      do j=-1                    /*traipse through all the bits.        */
                      if j==-1  then x= 0        /*special handle the first time through*/
                                else x= base**j             /*compute a power of  BASE. */
                      if pos('E', x)>0  then leave          /*does it have an exponent? */
                      say right(x, d)  !  right(rlwb(x), 4)  !  right(rupb(x), 4)  !  bits
                      end   /*j*/
       call sep '─┴─'                            /*  ─┴─  is part of the separator line.*/
       if cycle==1  then do 3;   say;   end      /*show extra blank lines between sets. */
       end   /*cycle*/
exit 0                                           /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
n2b:  bits= word( strip( x2b( d2x( arg(1))), 'L', 0) 0, 1);  L= length(bits);  return bits
rlwb: arg #; call n2b #; if #==0  then return  0; return L - length( strip( bits, 'T', 0))
rupb: arg #; call n2b #; if #==0  then return -1; return L - 1
sep:  arg _; say @d || _ || @4 || _ || @4 || _ || copies(@, length( n2b(10**d) ));  return
output   when using the internal default inputs:

(Shown at   3/4   size.)

─────────────────────────────────────────┬──────┬──────┬──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
            42**n  (decimal)             │ rlwb │ rupb │                               42**n  (binary)
─────────────────────────────────────────┼──────┼──────┼──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
                                       0 │    0 │   -1 │ 0
                                       1 │    0 │    0 │ 1
                                      42 │    1 │    5 │ 101010
                                    1764 │    2 │   10 │ 11011100100
                                   74088 │    3 │   16 │ 10010000101101000
                                 3111696 │    4 │   21 │ 1011110111101100010000
                               130691232 │    5 │   26 │ 111110010100011000010100000
                              5489031744 │    6 │   32 │ 101000111001010111111101001000000
                            230539333248 │    7 │   37 │ 11010110101101001101110000111010000000
                           9682651996416 │    8 │   43 │ 10001100111001101011000010000110000100000000
                         406671383849472 │    9 │   48 │ 1011100011101110110001111010111111110101000000000
                       17080198121677824 │   10 │   53 │ 111100101011100101100110000101101111000110010000000000
                      717368321110468608 │   11 │   59 │ 100111110100100110101010111111110000111010000110100000000000
                    30129469486639681536 │   12 │   64 │ 11010001000100001011000001101110110000110001000010001000000000000
                  1265437718438866624512 │   13 │   70 │ 10001001001100101111001111001000101100000000001011011001010000000000000
                 53148384174432398229504 │   14 │   75 │ 1011010000010010110111111111011101100111000000111011110100100100000000000000
               2232232135326160725639168 │   15 │   80 │ 111011000101100011000101111101001011011100110100111010000011111101000000000000000
              93753749683698750476845056 │   16 │   86 │ 100110110001101001000001111010001001100000111010101110000110100110000010000000000000000
            3937657486715347520027492352 │   17 │   91 │ 11001011100100100111011010000001010001111100110100010010000010100111101010100000000000000000
          165381614442044595841154678784 │   18 │   97 │ 10000101100110000001110111000100110101110001111010010011110101101110000001111001000000000000000000
         6946027806565873025328496508928 │   19 │  102 │ 1010111101010111101001110001001001011010010110000010001000001010000001101001111011010000000000000000000
       291733167875766667063796853374976 │   20 │  107 │ 111001100010001100001011010010000001011010010011101011001010110100101000101100000111000100000000000000000000
     12252793050782200016679467841748992 │   21 │  113 │ 100101110000011011111111011001110100111011010000111010010101000110100010101100111100101000101000000000000000000000
    514617308132852400700537649353457664 │   22 │  118 │ 11000110001110010010111100110111100101110111001000110010001110110010010110001011111110010101010010000000000000000000000
  21613926941579800829422581272845221888 │   23 │  124 │ 10000010000101011000011011111100011110110110001011110000111101101101000010100011110110111001111101110100000000000000000000000
 907784931546351634835748413459499319296 │   24 │  129 │ 1010101010111100010000010010101101100001111100011101110001000011111100011101011100010000010000010100100001000000000000000000000000
─────────────────────────────────────────┴──────┴──────┴──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────



─────────────────────────────────────────┬──────┬──────┬──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
           1302**n  (decimal)            │ rlwb │ rupb │                             1302**n  (binary)
─────────────────────────────────────────┼──────┼──────┼──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
                                       0 │    0 │   -1 │ 0
                                       1 │    0 │    0 │ 1
                                    1302 │    1 │   10 │ 10100010110
                                 1695204 │    2 │   20 │ 110011101110111100100
                              2207155608 │    3 │   31 │ 10000011100011101000010110011000
                           2873716601616 │    4 │   41 │ 101001110100010110110110110111001100010000
                        3741579015304032 │    5 │   51 │ 1101010010101111001001000000000110110011001101100000
                     4871535877925849664 │    6 │   62 │ 100001110011011001011000001001000001010010101110100101001000000
                  6342739713059456262528 │    7 │   72 │ 1010101111101011100110010001000111100000010010111111100111010000110000000
               8258247106403412053811456 │    8 │   82 │ 11011010100110000000111100100000001110101011000010011010001000101110110000100000000
           10752237732537242494062515712 │    9 │   93 │ 1000101011111000001010111001110110111101010011111100010111111101101100111001110101011000000000
        13999413527763489727269395457024 │   10 │  103 │ 10110000101100101000101101110101000100000011010011101110001111100001001111100000100011110110010000000000
     18227236413148063624904752885045248 │   11 │  113 │ 111000001010101100000100010100010101100000011011010011001110101111101110010001100000011001010001101001100000000000
  23731861809918778839625988256328912896 │   12 │  124 │ 10001110110101001011100011111110101101101100001101011011001001101111110110111011000001001000010001101000010010001000000000000
─────────────────────────────────────────┴──────┴──────┴──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────

RPL

≪ → n 
  ≪ IF n #0 == THEN -1 ELSE
       0 #1 
       WHILE n OVER AND #0 == REPEAT SL SWAP 1 + SWAP END 
       DROP END
≫ ≫ 'LWB' STO

≪ → n 
  ≪ IF n #0 == THEN -1 ELSE
       63 #1 RR
       WHILE n OVER AND #0 == REPEAT SR SWAP 1 - SWAP END 
       DROP END
≫ ≫ 'UPB' STO
≪ { } 0 5 FOR j 42 j ^ R→B DUP UPB SWAP LWB R→C + NEXT ≫ EVAL
Output:
1: { (0,0) (5,1) (10,2) (16,3) (21,4) (26,5) }

Ruby

Translation of: Python
def msb(x)
  x.bit_length - 1
end

def lsb(x)
  msb(x & -x)
end

6.times do |i|
  x = 42 ** i
  puts "%10d MSB: %2d LSB: %2d" % [x, msb(x), lsb(x)]
end

6.times do |i|
  x = 1302 ** i
  puts "%20d MSB: %2d LSB: %2d" % [x, msb(x), lsb(x)]
end
Output:
         1 MSB:  0 LSB:  0
        42 MSB:  5 LSB:  1
      1764 MSB: 10 LSB:  2
     74088 MSB: 16 LSB:  3
   3111696 MSB: 21 LSB:  4
 130691232 MSB: 26 LSB:  5
                   1 MSB:  0 LSB:  0
                1302 MSB: 10 LSB:  1
             1695204 MSB: 20 LSB:  2
          2207155608 MSB: 31 LSB:  3
       2873716601616 MSB: 41 LSB:  4
    3741579015304032 MSB: 51 LSB:  5

Seed7

The library integer.s7i defines the functions bitLength and lowestSetBit, which compute the most- and least-significant set bit in a binary value expressed in LSB 0 bit numbering.

$ include "seed7_05.s7i";
  include "bigint.s7i";

const func integer: rlwb (in integer: num) is
  return lowestSetBit(num);

const func integer: rupb (in integer: num) is
  return bitLength(num);

const func integer: rlwb (in bigInteger: num) is
  return lowestSetBit(num);

const func integer: rupb (in bigInteger: num) is
  return bitLength(num);

const proc: main is func
  local
    var integer: i is 0;
    var integer: num is 0;
    var bigInteger: bigNum is 0_;
  begin
    for i range 0 to 5 do
      num := 42 ** i;
      writeln(num lpad 10 <& " " <& num radix 2 lpad0 32 <&
              " MSB: " <& rupb(num) lpad 2 <& " LSB: " <& rlwb(num) lpad 2);
    end for;
    for i range 0 to 9 do
      bigNum := 1302_ ** i;
      writeln(bigNum lpad 30 <& " " <& bigNum radix 16 lpad0 26 <&
              " MSB: " <& rupb(bigNum) lpad 2 <& " LSB: " <& rlwb(bigNum) lpad 2);
    end for;
  end func;
Output:
         1 00000000000000000000000000000001 MSB:  1 LSB:  0
        42 00000000000000000000000000101010 MSB:  6 LSB:  1
      1764 00000000000000000000011011100100 MSB: 11 LSB:  2
     74088 00000000000000010010000101101000 MSB: 17 LSB:  3
   3111696 00000000001011110111101100010000 MSB: 22 LSB:  4
 130691232 00000111110010100011000010100000 MSB: 27 LSB:  5
                             1 00000000000000000000000001 MSB:  1 LSB:  0
                          1302 00000000000000000000000516 MSB: 11 LSB:  1
                       1695204 0000000000000000000019dde4 MSB: 21 LSB:  2
                    2207155608 000000000000000000838e8598 MSB: 32 LSB:  3
                 2873716601616 00000000000000029d16db7310 MSB: 42 LSB:  4
              3741579015304032 0000000000000d4af2401b3360 MSB: 52 LSB:  5
           4871535877925849664 0000000000439b2c120a574a40 MSB: 63 LSB:  6
        6342739713059456262528 0000000157d73223c097f3a180 MSB: 73 LSB:  7
     8258247106403412053811456 000006d4c07901d584d1176100 MSB: 83 LSB:  8
 10752237732537242494062515712 0022be0ae76f53f17f6ce75600 MSB: 94 LSB:  9

Sidef

Sidef has arbitrary sized integers.

Translation of: Perl
func msb(n) {
    var b = 0
    while(n >>= 1) { ++b }
    return b
}

func lsb(n) {
    msb(n & -n)
}

Test cases:

Translation of: Raku
func table (base,power) {
    var digits = length(base**power)
    printf("%#{digits}s  lsb msb\n", 'number')
    for n in (0..power) {
        var x = base**n
        printf("%#{digits}s  %2s  %3s\n", x, lsb(x), msb(x))
    }
}

table(42, 20)
table(1302, 20)

Tcl

proc lwb {x} {
    if {$x == 0} {return -1}
    set n 0
    while {($x&1) == 0} {
	set x [expr {$x >> 1}]
	incr n
    }
    return $n
}
proc upb {x} {
    if {$x == 0} {return -1}
    if {$x < 0} {error "no well-defined max bit for negative numbers"}
    set n 0
    while {$x != 1} {
	set x [expr {$x >> 1}]
	incr n
    }
    return $n
}

Code to use the above:

package require Tcl 8.6; # For convenient bit string printing

proc powsTo {pow bits} {
    set result {}
    for {set n 1} {$n < 2**$bits} {set n [expr {$n * $pow}]} {
	lappend result $n
    }
    return $result
}
proc printPows {pow pows} {
    set len [string length [lindex $pows end]]
    puts [format "%8s | %*s | LWB | UPB | Bits" "What" $len "Number"]
    set n 0
    foreach p $pows {
	puts [format "%4d**%-2d = %*lld | %3d | %3d | %b" \
		  $pow $n $len $p [lwb $p] [upb $p] $p]
	incr n
    }
}

puts "Powers of 42 up to machine word size:"
printPows 42 [powsTo 42 [expr {$tcl_platform(wordSize) * 8}]]
puts "Powers of 1302 up to 128 bits"
printPows 1302 [powsTo 1302 128]
Output:
Powers of 42 up to machine word size:
    What |    Number | LWB | UPB | Bits
  42**0  =         1 |   0 |   0 | 1
  42**1  =        42 |   1 |   5 | 101010
  42**2  =      1764 |   2 |  10 | 11011100100
  42**3  =     74088 |   3 |  16 | 10010000101101000
  42**4  =   3111696 |   4 |  21 | 1011110111101100010000
  42**5  = 130691232 |   5 |  26 | 111110010100011000010100000
Powers of 1302 up to 128 bits
    What |                                 Number | LWB | UPB | Bits
1302**0  =                                      1 |   0 |   0 | 1
1302**1  =                                   1302 |   1 |  10 | 10100010110
1302**2  =                                1695204 |   2 |  20 | 110011101110111100100
1302**3  =                             2207155608 |   3 |  31 | 10000011100011101000010110011000
1302**4  =                          2873716601616 |   4 |  41 | 101001110100010110110110110111001100010000
1302**5  =                       3741579015304032 |   5 |  51 | 1101010010101111001001000000000110110011001101100000
1302**6  =                    4871535877925849664 |   6 |  62 | 100001110011011001011000001001000001010010101110100101001000000
1302**7  =                 6342739713059456262528 |   7 |  72 | 1010101111101011100110010001000111100000010010111111100111010000110000000
1302**8  =              8258247106403412053811456 |   8 |  82 | 11011010100110000000111100100000001110101011000010011010001000101110110000100000000
1302**9  =          10752237732537242494062515712 |   9 |  93 | 1000101011111000001010111001110110111101010011111100010111111101101100111001110101011000000000
1302**10 =       13999413527763489727269395457024 |  10 | 103 | 10110000101100101000101101110101000100000011010011101110001111100001001111100000100011110110010000000000
1302**11 =    18227236413148063624904752885045248 |  11 | 113 | 111000001010101100000100010100010101100000011011010011001110101111101110010001100000011001010001101001100000000000
1302**12 = 23731861809918778839625988256328912896 |  12 | 124 | 10001110110101001011100011111110101101101100001101011011001001101111110110111011000001001000010001101000010010001000000000000

Wren

Library: Wren-big
Library: Wren-fmt
import "./big" for BigInt
import "./fmt" for Fmt

var rupb = Fn.new { |x| (x is BigInt) ? x.bitLength - 1 : x.log2.floor }
var rlwb = Fn.new { |x| rupb.call(x & -x) }

System.print("Powers of 42 below 2^32 using Num:")
var x = 1
for (i in 0..5) {
    Fmt.print("42^$d = $,11d  rupb: $2d  rlwb: $2d", i, x, rupb.call(x), rlwb.call(x))
    x = x * 42
}

System.print("\nPowers of 1302 below 2^64 using BigInt:")
x = BigInt.new(1)
for (i in 0..6) {
    Fmt.print("1302^$d = $,25s  rupb: $2s  rlwb: $2s", i, x, rupb.call(x), rlwb.call(x))
    x = x * 1302
}
Output:
Powers of 42 below 2^32 using Num:
42^0 =           1  rupb:  0  rlwb:  0
42^1 =          42  rupb:  5  rlwb:  1
42^2 =       1,764  rupb: 10  rlwb:  2
42^3 =      74,088  rupb: 16  rlwb:  3
42^4 =   3,111,696  rupb: 21  rlwb:  4
42^5 = 130,691,232  rupb: 26  rlwb:  5

Powers of 1302 below 2^64 using BigInt:
1302^0 =                         1  rupb:  0  rlwb:  0
1302^1 =                     1,302  rupb: 10  rlwb:  1
1302^2 =                 1,695,204  rupb: 20  rlwb:  2
1302^3 =             2,207,155,608  rupb: 31  rlwb:  3
1302^4 =         2,873,716,601,616  rupb: 41  rlwb:  4
1302^5 =     3,741,579,015,304,032  rupb: 51  rlwb:  5
1302^6 = 4,871,535,877,925,849,664  rupb: 62  rlwb:  6

XPL0

include xpllib; \for Print

func UpB(N);    \Return position of highest set bit
int  N, C;
[C:= 0;
if N & $FFFF0000 then [C:= C+16;  N:= N & $FFFF0000];
if N & $FF00FF00 then [C:= C+ 8;  N:= N & $FF00FF00];
if N & $F0F0F0F0 then [C:= C+ 4;  N:= N & $F0F0F0F0];
if N & $CCCCCCCC then [C:= C+ 2;  N:= N & $CCCCCCCC];
if N & $AAAAAAAA then [C:= C+ 1];
return C;
];

func LwB(N);    \Return position of lowest set bit
int  N;
return UpB(N & -N);

int N, I;
[Print("            MSB LSB\n");
N:= 1;
for I:= 0 to 5 do
        [Print("%10d %3d %3d\n", N, UpB(N), LwB(N));
        N:= N*42;
        ];
]
Output:
            MSB LSB
         1   0   0
        42   5   1
      1764  10   2
     74088  16   3
   3111696  21   4
 130691232  26   5

Yabasic

Translation of: FreeBASIC
print "INT: find first & last set bit"
p = 1
for j = 0 to 5
    print p using("##########"), " MSB: ", MSB(p) using("##"), " LSB: ", LSB(p)
    p = p * 42
next j
print
end

sub MSB(i)
    return len(bin$(i))-1
end sub

sub LSB(i)
    return MSB(and(i,-i))
end sub
Output:
INT: find first & last set bit
         1 MSB:  0 LSB: 0
        42 MSB:  5 LSB: 1
      1764 MSB: 10 LSB: 2
     74088 MSB: 16 LSB: 3
   3111696 MSB: 21 LSB: 4
 130691232 MSB: 26 LSB: 5


Z80 Assembly

This version works with 8-bit values and is simple enough, given the CPU's obvious affinity for manipulating 8-bit data. First we display the "least" set bit, then the "most" set bit. These are in terms of LSB-0 ordering, e.g. %76543210 (where those numbers are bit positions rather than literals)

;;;;;;;;;;;;;;;;;;; HEADER   ;;;;;;;;;;;;;;;;;;;
read "\SrcCPC\winape_macros.asm"
read "\SrcCPC\MemoryMap.asm"
read "\SrcALL\winapeBuildCompat.asm"
;;;;;;;;;;;;;;;;;;; PROGRAM  ;;;;;;;;;;;;;;;;;;;

org &1000
ld a,%00101111
push af
call lwb_8
call showhex
call newline
pop af



call upb_8
call showhex
ret



upb_8:
ld b,8
upb_8_again:
or a
rla
jr c,upb_8_done:
djnz upb_8_again
ld a,255 ;failure code
ret
upb_8_done:
dec b
ld a,b
ret

lwb_8:
ld bc,&0800 ;ld b,8	ld c,0
lwb_8_again:
or a
rra
jr c,lwb_8_done
inc c
djnz lwb_8_again
ld a,255 ;failure code
ret
lwb_8_done:
ld a,c
ret


read "\SrcCPC\winape_stringop.asm"
read "\SrcCPC\winape_showhex.asm"
Output:
00
05


zkl

Translation of: C

This uses the Int method log2 (== MSB position), which returns the log base 2 of self. log2 is implemented with shifts and ors (it is a 5 step loop (for 64 bit ints) which could obviously be unrolled). See http://graphics.stanford.edu/~seander/bithacks.html.

fcn lsb(n){ n.bitAnd(n.bitNot()+1).log2() }
fcn msb(n){ n.log2() }

foreach p in (200){
  n:=(42).pow(p);
  println("42^%2d = %18d(x%015x): MSB(%2d) LSB(%2d)".fmt(
	  p,n,n, msb(n), lsb(n)));
  if (n>=(1).MAX / 42) break;
}
Output:
42^ 0 =                  1(x000000000000001): MSB( 0) LSB( 0)
42^ 1 =                 42(x00000000000002a): MSB( 5) LSB( 1)
42^ 2 =               1764(x0000000000006e4): MSB(10) LSB( 2)
42^ 3 =              74088(x000000000012168): MSB(16) LSB( 3)
42^ 4 =            3111696(x0000000002f7b10): MSB(21) LSB( 4)
42^ 5 =          130691232(x000000007ca30a0): MSB(26) LSB( 5)
42^ 6 =         5489031744(x0000001472bfa40): MSB(32) LSB( 6)
42^ 7 =       230539333248(x0000035ad370e80): MSB(37) LSB( 7)
42^ 8 =      9682651996416(x00008ce6b086100): MSB(43) LSB( 8)
42^ 9 =    406671383849472(x00171dd8f5fea00): MSB(48) LSB( 9)
42^10 =  17080198121677824(x03cae5985bc6400): MSB(53) LSB(10)
42^11 = 717368321110468608(x9f49aaff0e86800): MSB(59) LSB(11)