Rosetta Code

Find first and last set bit of a long integer: Difference between revisions

Page Discussion

Find first and last set bit of a long integer (view source)

Revision as of 20:46, 10 December 2023

3,825 bytes added ,  6 months ago
Added XPL0 example.
(Added Quackery.)
(Added XPL0 example.)
 
(11 intermediate revisions by 7 users not shown)
Line 302:
18227236413148063624904752885045248| 11 |113 |111000001010101100000100010100010101100000011011010011001110101111101110010001100000011001010001101001100000000000
</pre>
 
=={{header|Arturo}}==
 
<syntaxhighlight lang="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]
]</syntaxhighlight>
 
{{out}}
 
<pre> 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</pre>
 
=={{header|AutoHotkey}}==
Line 326 ⟶ 359:
42^10 --> First : 10 , Last : 53
42^11 --> First : 11 , Last : 59</pre>
 
 
=={{header|BASIC256}}==
Line 582 ⟶ 614:
17080198121677824 0000000000111100101011100101100110000101101111000110010000000000 MSB: 53 LSB: 10
717368321110468608 0000100111110100100110101010111111110000111010000110100000000000 MSB: 59 LSB: 11</pre>
 
 
=={{header|Forth}}==
{{works with|gforth|0.7.3}}
 
<syntaxhighlight lang="Forth">: 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</syntaxhighlight>
{{out}}
<pre> 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
</pre>
 
 
 
=={{header|Fortran}}==
Line 819 ⟶ 892:
717368321110468608 0000100111110100100110101010111111110000111010000110100000000000 MSB: 59 LSB: 11
</pre>
 
 
=={{header|FutureBasic}}==
<syntaxhighlight lang="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
 
</syntaxhighlight>
{{output}
<pre>
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
</pre>
 
 
 
Line 1,145 ⟶ 1,260:
=={{header|Java}}==
 
=== Library ===
{{incorrect|Java}}
{{works with|Java|1.5+}}
Notes:
* least significant bit is bit 0 (such that bit ''i'' always has value 2<sup>i</sup>, and the result is independent of integer type width)
* when the integer 0 is given, mssb() and lssb() both return no bits set; mssb_idx() and lssb_idx() will return -1 and the integer type width, respectively
<syntaxhighlight lang="java">public class FirstLastBits {
 
<syntaxhighlight lang="java">public class FirstAndLastBits {
// most significant set bit
public static int mssb(int x) {
return Integer.highestOneBit(x);
}
 
public static long mssbLSB(longLong xaNumber) {
if ( aNumber <= 0 ) {
return Long.highestOneBit(x);
throw new IllegalArgumentException("Number must be positive");
}
}
 
return Long.numberOfTrailingZeros(aNumber);
public static int mssb_idx(int x) {
}
return Integer.SIZE - 1 - Integer.numberOfLeadingZeros(x);
}
public static long MSB(Long aNumber) {
 
if ( aNumber <= 0 ) {
public static int mssb_idx(long x) {
throw new IllegalArgumentException("Number must be positive");
return Long.SIZE - 1 - Long.numberOfLeadingZeros(x);
}
}
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);
}
}
 
public static int mssb_idx(BigInteger x) {
return x.bitLength() - 1;
}
 
// least significant set bit
public static int lssb(int x) {
return Integer.lowestOneBit(x);
}
 
public static long lssb(long x) {
return Long.lowestOneBit(x);
}
 
public static int lssb_idx(int x) {
return Integer.numberOfTrailingZeros(x);
}
 
public static int lssb_idx(long x) {
return Long.numberOfTrailingZeros(x);
}
 
public static int lssb_idx(BigInteger x) {
return x.getLowestSetBit();
}
 
public static void main(String[] args) {
System.out.println("int:");
int n1 = 1;
for (int i = 0; ; i++, n1 *= 42) {
System.out.printf("42**%d = %10d(x%08x): M x%08x(%2d) L x%03x(%2d)\n",
i, n1, n1,
mssb(n1), mssb_idx(n1),
lssb(n1), lssb_idx(n1));
if (n1 >= Integer.MAX_VALUE / 42)
break;
}
System.out.println();
System.out.println("long:");
long n2 = 1;
for (int i = 0; ; i++, n2 *= 42) {
System.out.printf("42**%02d = %20d(x%016x): M x%016x(%2d) L x%06x(%2d)\n",
i, n2, n2,
mssb(n2), mssb_idx(n2),
lssb(n2), lssb_idx(n2));
if (n2 >= Long.MAX_VALUE / 42)
break;
}
System.out.println();
System.out.println("BigInteger:");
BigInteger n3 = BigInteger.ONE;
BigInteger k = BigInteger.valueOf(1302);
for (int i = 0; i < 10; i++, n3 = n3.multiply(k)) {
System.out.printf("1302**%02d = %30d(x%28x): M %2d L %2d\n",
i, n3, n3,
mssb_idx(n3),
lssb_idx(n3));
}
}
}</syntaxhighlight>
{{out}}
<pre>
42 ^ 0 = 0000000000000000000000000000000000000000000000000000000000000001 -> LSB: 0 , MSB: 0
int:
42 ^ 1 = 0000000000000000000000000000000000000000000000000000000000101010 -> LSB: 1 , MSB: 5
42**0 = 1(x00000001): M x00000001( 0) L x001( 0)
42 ^ 2 = 0000000000000000000000000000000000000000000000000000011011100100 -> LSB: 2 , MSB: 10
42**1 = 42(x0000002a): M x00000020( 5) L x002( 1)
42 ^ 3 = 0000000000000000000000000000000000000000000000010010000101101000 -> LSB: 3 , MSB: 16
42**2 = 1764(x000006e4): M x00000400(10) L x004( 2)
42 ^ 4 = 0000000000000000000000000000000000000000001011110111101100010000 -> LSB: 4 , MSB: 21
42**3 = 74088(x00012168): M x00010000(16) L x008( 3)
42 ^ 5 = 0000000000000000000000000000000000000111110010100011000010100000 -> LSB: 5 , MSB: 26
42**4 = 3111696(x002f7b10): M x00200000(21) L x010( 4)
42 ^ 6 = 0000000000000000000000000000000101000111001010111111101001000000 -> LSB: 6 , MSB: 32
42**5 = 130691232(x07ca30a0): M x04000000(26) L x020( 5)
42 ^ 7 = 0000000000000000000000000011010110101101001101110000111010000000 -> LSB: 7 , MSB: 37
 
42 ^ 8 = 0000000000000000000010001100111001101011000010000110000100000000 -> LSB: 8 , MSB: 43
long:
42 ^ 9 = 0000000000000001011100011101110110001111010111111110101000000000 -> LSB: 9 , MSB: 48
42**00 = 1(x0000000000000001): M x0000000000000001( 0) L x000001( 0)
42 ^ 10 = 0000000000111100101011100101100110000101101111000110010000000000 -> LSB: 10, MSB: 53
42**01 = 42(x000000000000002a): M x0000000000000020( 5) L x000002( 1)
42 ^ 11 = 0000100111110100100110101010111111110000111010000110100000000000 -> LSB: 11, MSB: 59
42**02 = 1764(x00000000000006e4): M x0000000000000400(10) L x000004( 2)
42**03 = 74088(x0000000000012168): M x0000000000010000(16) L x000008( 3)
42**04 = 3111696(x00000000002f7b10): M x0000000000200000(21) L x000010( 4)
42**05 = 130691232(x0000000007ca30a0): M x0000000004000000(26) L x000020( 5)
42**06 = 5489031744(x00000001472bfa40): M x0000000100000000(32) L x000040( 6)
42**07 = 230539333248(x00000035ad370e80): M x0000002000000000(37) L x000080( 7)
42**08 = 9682651996416(x000008ce6b086100): M x0000080000000000(43) L x000100( 8)
42**09 = 406671383849472(x000171dd8f5fea00): M x0001000000000000(48) L x000200( 9)
42**10 = 17080198121677824(x003cae5985bc6400): M x0020000000000000(53) L x000400(10)
42**11 = 717368321110468608(x09f49aaff0e86800): M x0800000000000000(59) L x000800(11)
 
1302 ^ 0 = 0000000000000000000000000000000000000000000000000000000000000001 -> LSB: 0 , MSB: 0
BigInteger:
1302 ^ 1 = 0000000000000000000000000000000000000000000000000000010100010110 -> LSB: 1 , MSB: 10
1302**00 = 1(x 1): M 0 L 0
1302 ^ 2 = 0000000000000000000000000000000000000000000110011101110111100100 -> LSB: 2 , MSB: 20
1302**01 = 1302(x 516): M 10 L 1
1302 ^ 3 = 0000000000000000000000000000000010000011100011101000010110011000 -> LSB: 3 , MSB: 31
1302**02 = 1695204(x 19dde4): M 20 L 2
1302 ^ 4 = 0000000000000000000000101001110100010110110110110111001100010000 -> LSB: 4 , MSB: 41
1302**03 = 2207155608(x 838e8598): M 31 L 3
1302 ^ 5 = 0000000000001101010010101111001001000000000110110011001101100000 -> LSB: 5 , MSB: 51
1302**04 = 2873716601616(x 29d16db7310): M 41 L 4
1302 ^ 6 = 0100001110011011001011000001001000001010010101110100101001000000 -> LSB: 6 , MSB: 62
1302**05 = 3741579015304032(x d4af2401b3360): M 51 L 5
1302**06 = 4871535877925849664(x 439b2c120a574a40): M 62 L 6
1302**07 = 6342739713059456262528(x 157d73223c097f3a180): M 72 L 7
1302**08 = 8258247106403412053811456(x 6d4c07901d584d1176100): M 82 L 8
1302**09 = 10752237732537242494062515712(x 22be0ae76f53f17f6ce75600): M 93 L 9
</pre>
 
Line 1,609 ⟶ 1,681:
3741579015304032 MSB: 51 LSB: 5
</pre>
 
=={{header|Racket}}==
<syntaxhighlight lang="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)))
</syntaxhighlight>
{{out}}
<syntaxhighlight lang="racket">
'((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))
</syntaxhighlight>
 
=={{header|Quackery}}==
Line 1,697 ⟶ 1,737:
2873716601616 msb:41 lsb:4
3741579015304032 msb:51 lsb:5</pre>
 
=={{header|Racket}}==
<syntaxhighlight lang="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)))
</syntaxhighlight>
{{out}}
<syntaxhighlight lang="racket">
'((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))
</syntaxhighlight>
 
=={{header|Raku}}==
Line 1,851 ⟶ 1,923:
23731861809918778839625988256328912896 │ 12 │ 124 │ 10001110110101001011100011111110101101101100001101011011001001101111110110111011000001001000010001101000010010001000000000000
─────────────────────────────────────────┴──────┴──────┴──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
</pre>
 
=={{header|RPL}}==
≪ → n
≪ '''IF''' n #0 == '''THEN''' -1 '''ELSE'''
0 #1
'''WHILE''' n OVER AND #0 == '''REPEAT''' SL SWAP 1 + SWAP '''END'''
DROP '''END'''
≫ ≫ '<span style="color:blue">LWB</span>' STO
≪ → n
≪ '''IF''' n #0 == '''THEN''' -1 '''ELSE'''
63 #1 RR
'''WHILE''' n OVER AND #0 == '''REPEAT''' SR SWAP 1 - SWAP '''END'''
DROP '''END'''
≫ ≫ '<span style="color:blue">UPB</span>' STO
 
≪ { } 0 5 '''FOR''' j 42 j ^ R→B DUP <span style="color:blue">UPB</span> SWAP <span style="color:blue">LWB</span> R→C + '''NEXT''' ≫ EVAL
{{out}}
<pre>
1: { (0,0) (5,1) (10,2) (16,3) (21,4) (26,5) }
</pre>
 
Line 2,050 ⟶ 2,143:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./big" for BigInt
import "./fmt" for Fmt
 
var rupb = Fn.new { |x| (x is BigInt) ? x.bitLength - 1 : x.log2.floor }
Line 2,088 ⟶ 2,181:
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
</pre>
 
=={{header|XPL0}}==
<syntaxhighlight lang "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;
];
]</syntaxhighlight>
{{out}}
<pre>
MSB LSB
1 0 0
42 5 1
1764 10 2
74088 16 3
3111696 21 4
130691232 26 5
</pre>
 
Boreal
297

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/331601...351357"