Logo

Programming-Idioms

  • Lisp
  • Pascal
  • Haskell

Idiom #263 Integer logarithm in base 2

Write two functions log2d and log2u, which calculate the binary logarithm of their argument n rounded down and up, respectively. n is assumed to be positive. Print the result of these functions for numbers from 1 to 12.

log2d :: Double -> Integer
log2d = floor . logBase 2

log2u :: Double -> Integer
log2u = ceiling . logBase 2

main :: IO ()
main = print $ [log2d, log2u] <*> [1..12]
function log2d(n: uint32): integer;
var
  temp: uint32;
begin
  Result := 0;
  temp := 1;
  while (temp < n) do
  begin
    Inc(Result);
    temp := 1 shl Result;
  end;
  if (temp > n) then
    Dec(Result);
end;

function log2u(n: uint32): integer;
begin
  Result := log2d(n);
  if (1 shl Result < n) then
    Inc(Result);
end;

var
  i: integer;
begin
  for i := 1 to 16 do
    writeln(i,': log2d = ',log2d(i),', log2u = ',log2u(i));
end.
program main
  implicit none
  integer :: i
  do i=1,12
     print *,i,log2d(i),log2u(i)
  end do
contains
  integer function log2d (n)
    integer, intent(in) :: n
    log2d = bit_size(n) - 1 - leadz(n)
  end function log2d

  integer function log2u (n)
    integer, intent(in) :: n
    log2u = bit_size(n) - leadz(n-1)
  end function log2u
end program main

New implementation...
< >
tkoenig