Find first and last set bit of a long integer: Difference between revisions
Find first and last set bit of a long integer (view source)
Revision as of 21:45, 30 March 2022
, 2 years ago→{{header|Fortran}}
(→{{header|Wren}}: Now uses new core library method.) |
|||
Line 605:
</pre>
=== 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.
<lang fortran>! As was already pointed out, Fortran already 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 full task description, and also by other methods.
! 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
! The task restricts itself to positive integers, but I shall do a
! branch for negative numbers.
if (n < 0) then
i = 0_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</lang>
{{out}}
<pre>$ 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</pre>
=={{header|FreeBASIC}}==
| |||