Logo

Programming-Idioms

  • Go
  • Java

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.

import static java.lang.Math.ceil;
import static java.lang.Math.floor;
import static java.lang.Math.log;
import static java.lang.System.out;
interface F {
    double log2 = log(2);
    double f(double n);
}
F log2d = x -> floor(log(x) / F.log2),
  log2u = x -> ceil(log(x) / F.log2);
for (int i = 1; i <= 12; ++i) {
    out.printf("log2d(%s) = %s%n", i, log2d.f(i));
    out.printf("log2u(%s) = %s%n", i, log2u.f(i));
}
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 
interface F {
    double log2 = log(2);
    double f(double n);
}
F log2d = x -> floor(log(x) / F.log2),
  log2u = x -> ceil(log(x) / F.log2);
for (int i = 1; i <= 12; ++i) {
    out.printf("log2d(%s) = %s%n", i, log2d.f(i));
    out.printf("log2u(%s) = %s%n", i, log2u.f(i));
}
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
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.
sub log2d { floor log2 shift };

sub log2u { ceil log2 shift };
def log2d(n):
    return math.floor(math.log2(n))

def log2u(n):
    return math.ceil(math.log2(n))

for n in range(1, 13):
    print(n, log2d(n), log2u(n))
log2d = lambda x: floor(log2(x))
log2u = lambda x: ceil(log2(x))
for i in range(1, 13):
    print(i, log2d(i), log2u(i))
def log2d(n) =  n.bit_length - 1

def log2u(n) = 2 ** log2d(n) == n ? log2d(n) : log2d(n) + 1

(1..12).each{|n| puts "#{n}  #{log2d(n)}  #{log2u(n)}" }
fn log2d(n: f64) -> f64 {
    n.log2().floor()
}

fn log2u(n: f64) -> f64 {
    n.log2().ceil()
}

fn main() {
    for n in 1..=12 {
        let f = f64::from(n);
        println!("{} {} {}", n, log2d(f), log2u(f));
    }
}