Find first and last set bit of a long integer: Difference between revisions
Content added Content deleted
(→{{header|Wren}}: Now uses new core library method.) |
|||
Line 605: | Line 605: | ||
</pre> |
</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}}== |
=={{header|FreeBASIC}}== |