How can I do an integer log2() in Fortran?

Question

An obvious way to do this would be the following:

integer function log2_i(val) result(res)
    implicit none
    integer, intent(IN) :: val

    if (val<0) then
        print *, "ERROR in log2_i(): val cannot be negative."
    else if (val==0) then
        print *, "ERROR in log2_i(): todo: return the integer equivalent of (-inf)..."
    else if (val==1) then
        res = 0
    else
        res = FLOOR( LOG(val+0.0d0)/LOG(2.0d0) )
    endif
end function log2_i

Is there a better way using Fortran's bitshifting operators?

This question is almost the same, but uses unsigned integers. Unfortunately, the sign bit would prohibit using the same algorithm.

RSHIFT on a non-negative operand is equivalent to a logical right shift, so I don't see any problem — harold, Nov 19 '15 at 16:32
Take a look at the standard function `ILEN`, it should be very close to what you need (+/- 1). — njuffa, Nov 19 '15 at 16:36
@njuffa That's the HPF intrinsic, rather a Fortran one, though? So it may not be widely supported. — francescalus, Nov 19 '15 at 16:42
@francescalus Good point. I don't use Fortran often and thought that this is part of Fortran 2003, but maybe it is an HPF extension only. It has been available with all the Fortran compilers I have used in recent years, so if it is an extension it seems to be a common one (may need to check compiler flag settings for enabling HPF features). — njuffa, Nov 19 '15 at 16:55
There is no `ILEN` in gfortran https://gcc.gnu.org/onlinedocs/gfortran/Intrinsic-Procedures.html — Vladimir F Героям слава, Nov 19 '15 at 17:04

score 5 · Answer 1 · edited May 23 '17 at 11:51

As @harold mentioned, this shouldn't be a problem: since the logarithm is only defined for positive numbers, the sign bit is always zero (see the corresponding Wikipedia article). Therefore, the algorithm in the linked answer can be directly ported to Fortran (2008 Standard):

module mod_test
contains
  function ilog2_b(val ) result( res )
    integer, intent(in) :: val
    integer             :: res
    integer             :: tmp

    res = -1 
    ! Negativ values not allowed
    if ( val < 1 ) return

    tmp = val
    do while (tmp > 0)
      res = res + 1
      tmp = shiftr( tmp, 1 )
    enddo
  end function
end module

program test
  use mod_test
  print *,'Bitshifting: ', ilog2_b(12345)
  print *,'Formula:     ', floor( log(real(12345) ) / log(2.) )
end program

This is a solution based on the Fortran 95 intrinsic BTEST as suggested by @agentp:

module mod_test
contains
  function ilog2_b2(val ) result( res )
    integer, intent(in) :: val
    integer             :: res
    integer             :: i

    res = -1 
    ! Negativ values not allowed
    if ( val < 1 ) return
    do i=bit_size(val)-1,0,-1
      if ( btest(val, i) ) then
        res = i
        return
      endif
    enddo

  end function
end module

program test
  use mod_test
  print *,'Testing bits:', ilog2_b2(123456)
  print *,'Formula:     ', floor( log(real(123456) ) / log(2.) )
end program

Thanks to @IanH to point me towards bit_size... If your compiler supports shiftr, I would use the first variant instead.

@IanH mentioned yet another method using leadz, which is a Fortran 2008 feature:

module mod_test
contains
  function ilog2_b3(val ) result( res )
    integer, intent(in) :: val
    integer             :: res

    res = -1 
    ! Negativ values not allowed
    if ( val < 1 ) return

    res = bit_size(val)-leadz(val)-1
  end function
end module

program test
  use mod_test
  print *,'Testing bits:', ilog2_b3(123456)
  print *,'Formula:     ', floor( log(real(123456) ) / log(2.) )
end program

How can I do an integer log2() in Fortran?

1 Answers1