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

=={{header|11l}}==

 

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)

 

{{out}}

 

=={{header|Ada}}==

with Ada.Integer_Text_IO;

with Ada.Unchecked_Conversion;

Put_Result (Value => 42 ** A);

end loop;

{{out}}

<pre>

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.3.5 algol68g-2.3.5].}}

{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}

 

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

# WHILE # out bit /= 2r0 DO SKIP OD;

ABS out # EXIT #

 

MODE LBITS = LONG BITS;

prod *:= zoom

OD

{{out}}

<pre>

18227236413148063624904752885045248| 11 |113 |111000001010101100000100010100010101100000011011010011001110101111101110010001100000011001010001101001100000000000

</pre>

 

=={{header|AutoHotkey}}==

First := Last := ""

n:=42**(A_Index-1)

Res .= 42 "^" A_Index-1 " --> First : " First " , Last : " Last "`n"

}

{{out}}

<pre>42^0 --> First : 0 , Last : 0

42^10 --> First : 10 , Last : 53

42^11 --> First : 11 , Last : 59</pre>

 

=={{header|C}}==

#include <stdint.h>

 

 

return 0;

{{out}}

<pre>

===GCC extension===

{{works with|GCC}}

#include <limits.h>

 

 

return 0;

{{out}}

<pre>

=={{header|D}}==

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

 

void main() {

x, size_t.sizeof * 8, x, bsr(x), bsf(x));

}

{{out}}

On a 32 bit system:

{{libheader| System.SysUtils}}

{{libheader| Velthuis.BigIntegers}} Thanks for Rudy Velthuis for Velthuis.BigIntegers[https://github.com/rvelthuis/DelphiBigNumbers].

program Find_first_and_last_set_bit_of_a_long_integer;

 

 

readln;

{{out}}

<pre> 1 0000000000000000000000000000000000000000000000000000000000000001 MSB: 0 LSB: 0

17080198121677824 0000000000111100101011100101100110000101101111000110010000000000 MSB: 53 LSB: 10

717368321110468608 0000100111110100100110101010111111110000111010000110100000000000 MSB: 59 LSB: 11</pre>

 

=={{header|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.

 

implicit none

integer :: n = 1, i

n = 42 * n

end do

{{out}}

<pre>

111110010100011000010100000 5 26

</pre>

 

=={{header|Go}}==

{{trans|ALGOL 68}}

 

import (

n.Mul(n, base)

}

{{out}}

<pre>

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.

 

 

procedure main()

}

return mask # return pre-built data

 

{{libheader|Icon Programming Library}}

Implementation:

 

upb=: (#: i: 1:)"0

rlwb=: #@#:"0 - 1:

 

Notes:

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

 

1 1 1

#: 8

1 1 0 0 0 1 0 1 0 1

#:123456789123456789123456789x

 

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.

Example use:

 

1 0 0 0 0

42 0 4 5 1

13999413527763489727269395457024 0 93 103 10

18227236413148063624904752885045248 0 102 113 11

 

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 ...

=={{header|Java}}==

 

{{works with|Java|1.5+}}

 

 

 

{{out}}

<pre>

 

</pre>

 

 

'''Module''':

 

export lwb, upb

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

 

 

'''Main''':

 

# Using the built-in functions `leading_zeros` and `trailing_zeros`

for n in int128"1302" .^ (0:11)

@printf(" %-40i | %-3i | %-3i\n", n, lwb(n), upb(n))

 

{{out}}

=={{header|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:

 

import java.math.BigInteger

pow1302 *= big1302

}

 

{{out}}

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

 

<pre>Map[{#,"MSB:",MSB[#],"LSB:",LSB[#]}&,

=={{header|PARI/GP}}==

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

msb(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 <code>vecsmall</code>.

 

=={{header|Perl}}==

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

my ($n, $base) = (shift, 0);

$base++ while $n >>= 1;

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.

length(shift->as_bin)-3;

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

my($n, $pos) = (shift, 0);

die "n must be a 64-bit integer)" if $n > ~0;

if (($n & 0x8000000000000000) == 0) { $pos += 1; $n <<= 1; }

63-$pos;

 

=={{header|Phix}}==

There is nothing like this already built in, so we will roll our own, in low-level assembly. <br>

Of course you would normally hide this sort of stuff out of sight, far away from the usual day-to-day code.

<span style="color: #008080;">without</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">msb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #004080;">integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

=== mpfr/gmp ===

{{libheader|Phix/mpfr}}

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>

<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1302</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

 

=={{header|PicoLisp}}==

(dec (length (bin (abs N)))) )

 

(de lsb (N)

Test:

{{out}}

<pre> 1 0 0

=={{header|Python}}==

{{works with|Python|2.7+ and 3.1+}}

return x.bit_length() - 1

 

for i in range(6):

x = 1302 ** i

{{out}}

<pre>

3741579015304032 MSB: 51 LSB: 5

</pre>

 

=={{header|Racket}}==

#lang racket

(require rnrs/arithmetic/bitwise-6)

(define x (expt 42 n))

(list n (bitwise-first-bit-set x) (- (integer-length x) 1)))

{{out}}

'((0 0 0)

(1 1 5)

(18 18 97)

(19 19 102))

 

=={{header|Raku}}==

 

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

my $digits = ($base ** $power).chars;

printf "%{$digits}s lsb msb\n", 'number';

 

table 42, 20;

{{out}}

<pre> number lsb msb

 

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

parse arg digs . /*obtain optional argument from the CL.*/

if digs=='' | digs=="," then digs= 40 /*Not specified? Then use the default.*/

@d= copies(@, d) /*build part of the separator line. */

call sep '─┬─' /* ─┬─ is part of the separator line.*/

call sep '─┼─' /* ─┼─ is part of the separator line.*/

call sep '─┴─' /* ─┴─ is part of the separator line.*/

end /*cycle*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

n2b: bits= word( strip( x2b( d2x( arg(1))), 'L', 0) 0, 1); L= length(bits); return bits

{{out|output|text=&nbsp; when using the internal default inputs:}}

 

<pre style="font-size:75%">

─────────────────────────────────────────┬──────┬──────┬──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────

─────────────────────────────────────────┼──────┼──────┼──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────

0 │ 0 │ -1 │ 0

 

─────────────────────────────────────────┬──────┬──────┬──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────

─────────────────────────────────────────┼──────┼──────┼──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────

0 │ 0 │ -1 │ 0

23731861809918778839625988256328912896 │ 12 │ 124 │ 10001110110101001011100011111110101101101100001101011011001001101111110110111011000001001000010001101000010010001000000000000

─────────────────────────────────────────┴──────┴──────┴──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────

</pre>

 

=={{header|Ruby}}==

{{trans|Python}}

x.bit_length - 1

end

x = 1302 ** i

puts "%20d MSB: %2d LSB: %2d" % [x, msb(x), lsb(x)]

 

{{out}}

most- and least-significant set bit in a binary value expressed in LSB 0 bit numbering.

 

include "bigint.s7i";

 

" MSB: " <& rupb(bigNum) lpad 2 <& " LSB: " <& rlwb(bigNum) lpad 2);

end for;

 

{{out}}

Sidef has arbitrary sized integers.

{{trans|Perl}}

var b = 0

while(n >>= 1) { ++b }

func lsb(n) {

msb(n & -n)

 

Test cases:

{{trans|Raku}}

var digits = length(base**power)

printf("%#{digits}s lsb msb\n", 'number')

 

table(42, 20)

 

=={{header|Tcl}}==

if {$x == 0} {return -1}

set n 0

}

return $n

Code to use the above:

 

proc powsTo {pow bits} {

printPows 42 [powsTo 42 [expr {$tcl_platform(wordSize) * 8}]]

puts "Powers of 1302 up to 128 bits"

{{out}}

<pre>

{{libheader|Wren-big}}

{{libheader|Wren-fmt}}

 

var rlwb = Fn.new { |x| rupb.call(x & -x) }

 

Fmt.print("1302^$d = $,25s rupb: $2s rlwb: $2s", i, x, rupb.call(x), rlwb.call(x))

x = x * 1302

 

{{out}}

1302^6 = 4,871,535,877,925,849,664 rupb: 62 rlwb: 6

</pre>

 

=={{header|zkl}}==

{{trans|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 msb(n){ n.log2() }

 

p,n,n, msb(n), lsb(n)));

if (n>=(1).MAX / 42) break;

{{out}}

<pre>