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>

 

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

 

=={{header|BASIC256}}==

p = 1

for j = 0 to 5

return (i & -i)

end function

{{out}}

<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

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>

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.

 

! should compile to efficient code, such as a single machine

! instruction. But it seems profitable to have written implementations

end do

 

 

{{out}}

=={{header|FreeBASIC}}==

{{trans|Python}}

Return Len(Bin(i))-1

End Function

p *= 42

Next j

{{out}}

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

* least significant bit is bit 0 (such that bit ''i'' always has value 2ⁱ, 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

 

// most significant set bit

}

}

{{out}}

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

 

=={{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.*/

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

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

 

=={{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}}

import "/fmt" for Fmt

 

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

x = x * 1302

 

{{out}}

=={{header|Yabasic}}==

{{trans|FreeBASIC}}

p = 1

for j = 0 to 5

sub LSB(i)

return MSB(and(i,-i))

{{out}}

<pre>

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. <code>%76543210</code> (where those numbers are bit positions rather than literals)

 

read "\SrcCPC\winape_macros.asm"

read "\SrcCPC\MemoryMap.asm"

 

read "\SrcCPC\winape_stringop.asm"

{{out}}

<pre>00

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