CODEWITHSUNDEEP
performancefortranbit-manipulationfortran90logarithm
jvriesem
jvriesem

Reputation: 1972

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

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.

Upvotes: 2

Views: 1421

Answers (1)

Alexander Vogt
Alexander Vogt

Reputation: 18118

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

Upvotes: 5

Related Questions