Logo

Programming-Idioms

  • Perl
  • C++
  • Rust

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.

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));
    }
}

Alternatively, you could use n as f64 instead of f64::from(n), but that doesn't pass the Clippy pedantic lint cast_lossless.
use POSIX qw( log2 floor ceil );
sub log2d { floor log2 shift };

sub log2u { ceil log2 shift };

The POSIX module provides log2 (log base 2) as well as floor and ceil functions. The 'shift' function removes and returns the first argument from the parameter list, which then becomes the argument for log2().
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 
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));
    }
}
sub log2d { floor log2 shift };

sub log2u { ceil log2 shift };
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]
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));
}
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.
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)}" }