Base-2 integer logarithm of 64-bit unsigned integer

Question

Problem:

In your choice of language, write the shortest function that returns the floor of the base-2 logarithm of an unsigned 64-bit integer, or –1 if passed a 0. (Note: This means the return type must be capable of expressing a negative value.)

Test cases:

Your function must work correctly for all inputs, but here are a few which help illustrate the idea:

               INPUT ⟶ OUTPUT

                   0 ⟶ -1
                   1 ⟶  0
                   2 ⟶  1
                   3 ⟶  1
                   4 ⟶  2
                   7 ⟶  2
                   8 ⟶  3
                  16 ⟶  4
               65535 ⟶ 15
               65536 ⟶ 16
18446744073709551615 ⟶ 63

Rules:

1. You can name your function anything you like.
2. Character count is what matters most in this challenge.
3. You will probably want to implement the function using purely integer and/or boolean artithmetic. However, if you really want to use floating-point calculations, then that is fine so long as you call no library functions. So, simply saying return n?(int)log2l(n):-1; in C is off limits even though it would produce the correct result. If you're using floating-point arithmetic, you may use *, /, +, -, and exponentiation (e.g., ** or ^ if it's a built-in operator in your language of choice). This restriction is to prevent "cheating" by calling log() or a variant.
4. If you're using floating-point operations (see #3), you aren't required that the return type be integer; only that that the return value is an integer, e.g., floor(log₂(n)).
5. If you're using C/C++, you may assume the existence of an unsigned 64-bit integer type, e.g., uint64_t as defined in stdint.h. Otherwise, just make sure your integer type is capable of holding any 64-bit unsigned integer.
6. If your langauge does not support 64-bit integers (for example, Brainfuck apparently only has 8-bit integer support), then do your best with that and state the limitation in your answer title. That said, if you can figure out how to encode a 64-bit integer and correctly obtain the base-2 logarithm of it using 8-bit primitive arithmetic, then more power to you!
7. Have fun and get creative!

Answer 1

C 40 54

Edit Clever recursive trick by @Kyle - that's creative!

int l(uint64_t n){return n?l(n/2)+1:-1;}

(Previous version: That's the bare starting point - creativity level 0)

int l(uint64_t n){int r=-1;for(;n;n>>=1)r++;return r;}

Test: Ideone

Answer 2

C,89

Per my comment on the question, here's a quirky way to do it, inspired by this famous function: http://en.wikipedia.org/wiki/Fast_inverse_square_root

f(uint64_t x){__float128 y=x;__int128_t i = *(__int128_t*)&y;return x?(i>>112)-16383:-1;}

I store the number as a float. Then to extract the exponent of the float, I cast it bitwise to an integer, rightshift the integer and subtract the bias.

Unfortunately to get the last example to run correctly, a 128 bit float is required. A 64 bit float has only 52 bits for the mantissa, so it rounds 18446744073709551615 up to 18446744073709551616 (2^64). The standard IEEE 128-bit float has a 112 bit mantissa (which we shift out and discard) and a bias of 16383 on the exponent. These are the constants you see in the function.

the requirement f(0)=-1 has to be handled with a ternary operator ?:. Otherwise it would return -16383.

Here's a complete program using type names per GCC. I can't get it to run on visual studio or ideone at the moment, will try later.

#include <stdint.h>

uint64_t a;

f(uint64_t x){
  __float128 y=x;
  __int128_t i = *(__int128_t*)&y;
  return x?(i>>112)-16383:-1;
}

main(){
  scanf("%llu",&a);
  printf("%llu %d",a,f(a)); 
}

Answer 3

Haskell, 24 bytes

Can't come remotely close to the Golfscript answer, but I think this one in Haskell has everything else beat so far...

f 0= -1;f n=f(div n 2)+1

E.g.: Running with the test cases provided gives:

> map f [0,1,2,3,4,7,8,16,65535,65536,18446744073709551615]
[-1,0,1,1,2,2,3,4,15,16,63]

Answer 4

Golfscript 7 (or 11)

2base,(

or, if you want the actual function definition:

{2base,(}:f

you can test it here.

If you consider "base" to be cheating, then add two chars for:

{}{2/}/,(

Answer 5

Python 2, 26

t=lambda n:len(bin(n+n))-4

This is similar to the Python 3 answer by Tim S. However, doubling n and then subtracting 4 from the length has the advantage of working whether n is positive or zero.

If n > 0, then doubling n adds one to the binary length, so we compensate by subtracting 4 instead of 3. On the other hand, if n = 0, then the function returns -1 as desired.

Answer 6

GNU dc, 30 bytes

[_1pq]sz?d0=z[d2/d0<m]dsmxz2-p

Takes input from STDIN. Counts the number of times we can divide by 2.

Test output:

$ for i in 0 1 2 3 4 7 8 16 65535 65536 18446744073709551615
> do echo $i | dc log.dc
> done
-1
0
1
1
2
2
3
4
15
16
63
$ 

Answer 7

J, 11 chars

Uses the length of the base2 representation but for 0 it yields 1 We add the signum of the original number and subtract 2 thus getting the desired values for all n>=0.

   (2-~*+#@#:) 18446744073709551615x  NB. x is for extended precision number
63

Answer 8

Python 3, 38 bytes

def f(n):return(-1,len(bin(n))-3)[n>0]

bin(n) produces a string like 0b100, so you have to subtract 3, not just 1. (a,b)[condition] is a trick I took from Tips for golfing in Python.

Answer 9

C, 72

Using a binary split method

int k(uint64_t x){int i=64,r=-!x;while(i/=2)x>>i?x>>=i,r+=i:0;return r;}

ungolfed, unwound version with lookup table options.

#define USETABLE256
int msb(unsigned long long x){
    char ret = -1;

    if (x>0xFFFFFFFF){ ret+=32; x>>=32; }
    if (x>0xFFFF){ ret+=16; x>>=16; }
    if (x>0xFF){  ret+=8;  x>>=8;  }
#ifdef USETABLE256
    return ret + ((const char[256]){
 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
    })[x];
#else
    if (x>0xF){        ret+=4;  x>>=4;  }
#ifdef USETABLE16
    return ret + ((const char[16]){0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4})[x];
#else
    if (x>3){        ret+=2;  x>>=2;  }
    if (x>1){        ret+=1;  x>>=1;  }
    return ret + x;
#endif
#endif
}

Answer 10

Befunge 93 - 23

1-&: v
v+1\ _$.@
>\2/:^

Limited by implementation to 2^31 or 32-bit signed ints. Given a 64 bit unsigned (128 bit signed?!) implementation this code meets criteria.

Answer 11

TI-30XB - 19 (Instructions)

I won't actually participate in this contest with the following codes, but I found out this clever solution for my TI-30XB calculator: log(x)/log(2)+10^12-10^12. First of all, I wont participate because I clearly used the log function. Second, who actually has TI calculators... Third, this one's probably gonna win because its only 19 instructions. :D (Oh wow, but look at that golfscript code...) I just want to point out that there are more ways to floor a float, if any of you are interested. (For the C programmers its probably still smaller to use int's instead). By the way I am just abusing overflow handeling here. Since the TI-30XB stores floats, adding 10^12 to it will remove everything behind the dot.

TI-BASIC - 35 bytes

This one is a actual participant, but I bet none of you can execute it... Oh well just buy a TI-84 Plus then :D

:PROGRAM:LOG
:0→X
:If N=0
:-1→X
:While N>1
:iPart(N/2→N
:X+1→X
:END
:X

You would call the function (Or programs as they are called) like this:

:PROGRAM:TEST
:65535→N
:prgmLOG

X should now contain the value 15. Also, note that the X on the end of the program can actually be removed if the program is executed using prgmLOG (As shown above), since the X at the end is only used to display the number when the function is executed via the HOME screen. Yes, While, If, End and iPart( are one instruction each.

Answer 12

Ruby, 30 bytes

f=->n{n>0?n.to_s(2).size-1:-1}

E.g.

irb(main):019:0> f[0]
=> -1
irb(main):024:0> f[65535]
=> 15
irb(main):025:0> f[65536]
=> 16

Answer 13

Batch - 82

Due to language limitations, this only supports 32-bit ints

@set a=-2&set n=%1
:1
@set /aa=%a%+1&set /an=%n%/2&if %n% GTR 0 goto 1
echo %a%

Answer 14

PHP - 50 40

My final answer* inspired by @edc65, who was inspired to do a recursive version from @Kyle

function l($n){return $n?l($n>>1)+1:-1;}

My original version before the recursive answer was this:

function l($n){while($n){$n>>=1;$r++;}return$r-1;}

*I had to use the binary shift (>>) because division (/) kept making it a floating point, yielding wildy inaccurate/large answers (doing floating division until it ran out of decimal places and "became 0").
And casting to an (int) or using floor() cost more characters than the simple right shift.