Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!

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 x = log(2);
    double get(double n);
}
F log2d = n -> floor(log(n) / F.x),
  log2u = n -> ceil(log(n) / F.x);
for (int i = 1; i <= 12; ++i) {
    out.printf("%f, ", log2d.get(i));
    out.printf("%f%n", log2u.get(i));
}
#include <cmath>
#include <cstdio>
using namespace std;
double x {log2(2)};
auto log2d = [&x] (double n) {
    return floor(log(n) / x);
};
auto log2u = [&x] (double n) {
    return ceil(log(n) / x);
};
for (int i {1}; i <= 12; ++i) {
    printf("%f, ", log2d(i));
    printf("%f\n", log2u(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.
use POSIX qw( log2 floor ceil );
sub log2d { floor log2 shift };

sub log2u { ceil log2 shift };
import math
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))
from math import ceil, floor, log2
def wrap(f, array):
    def wrapper(w):
        def wrapped(*args, **kwargs):
            return w(f(*args, **kwargs))
        return wrapped
    return (wrapper(f) for f in array)
log2d, log2u = wrap(log2, (floor, ceil))
for n in range(1, 13):
    print(log2d(n), log2u(n))
wrap = lambda f: lambda n: f(log2(n))
log2d, log2u = map(wrap, (floor, ceil))
for n in range(1, 13):
    print(log2d(n), log2u(n))
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));
    }
}
New implementation...
< > ⌨
tkoenig 
interface F {
    double x = log(2);
    double get(double n);
}
F log2d = n -> floor(log(n) / F.x),
  log2u = n -> ceil(log(n) / F.x);
for (int i = 1; i <= 12; ++i) {
    out.printf("%f, ", log2d.get(i));
    out.printf("%f%n", log2u.get(i));
}
using namespace std;
double x {log2(2)};
auto log2d = [&x] (double n) {
    return floor(log(n) / x);
};
auto log2u = [&x] (double n) {
    return ceil(log(n) / x);
};
for (int i {1}; i <= 12; ++i) {
    printf("%f, ", log2d(i));
    printf("%f\n", log2u(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))
def wrap(f, array):
    def wrapper(w):
        def wrapped(*args, **kwargs):
            return w(f(*args, **kwargs))
        return wrapped
    return (wrapper(f) for f in array)
log2d, log2u = wrap(log2, (floor, ceil))
for n in range(1, 13):
    print(log2d(n), log2u(n))
wrap = lambda f: lambda n: f(log2(n))
log2d, log2u = map(wrap, (floor, ceil))
for n in range(1, 13):
    print(log2d(n), log2u(n))
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));
    }
}