Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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!
share|improve this question
2  
Why the restriction to C? Language-specific challenges are generally frowned upon. Also, what's the meaning of the bonus? (And also I don't think there is any need to show two ungolfed solutions right away.) –  Martin Büttner Jul 26 at 19:28
    
@MartinBüttner — Oh, ok, I didn't realize that. I'm new here (not to SX but to CG.SX). Thanks for pointing that out. I'll remove the restriction and delete the second example, and I'll eliminate the language-specific requirement. –  Todd Lehman Jul 26 at 19:30
    
@MartinBüttner — Actually, went ahead and deleted both examples. –  Todd Lehman Jul 26 at 19:33
4  
No floating point? There goes my best idea (inspired by the famous fast inverse square root.) Assign the number to float, cast it bitwise to an integer, and extract the exponent from it by rightshifting by a constant. –  steveverrill Jul 26 at 19:36
1  
As you changed the rules for me I went ahead and posted :-) All questions on PPCG should have an objective winning criterion. My answer is not a winner under pure code golf. If it is your intention to reward creative answers, you should do so in an objective way. See this question for example: codegolf.stackexchange.com/q/23581/15599. Otherwise, you can delete your rule 3 and make it a pure code golf. I won't mind if you do that. –  steveverrill Jul 26 at 21:09

10 Answers 10

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/}/,(
share|improve this answer
1  
I would consider a log function as cheating, but not base as you've used it, as you've basically stringified it (into an array) and measured the length. It's not quite in the spirit of what I'd been thinking (which was to use integer arithmetic) but every language has peculiar magical features, and this isn't your standard straightfoward cheat. I'm guessing nobody is going to do better than this one! –  Todd Lehman Jul 27 at 0:54
1  
Thanks! I actually like my alternative solution better (and I'd understand if you want to disallow "base" type operations - feel free). My alternative collects all the divisions by 2 until it reaches 0, then takes the size and decrements. –  Kyle McCormick Jul 27 at 1:01
1  
It is interesting that Golfscript's base function returns an empty array for the value 0, rather than [0]. That gives you the –1 with no extra effort. :) –  Todd Lehman Jul 27 at 1:02
1  
Yeah I always thought that feature of GS was weird but now it makes sense - it allows you to easily calculate logs in any base. –  Kyle McCormick Jul 27 at 1:07
1  
Your 9-character looping solution is awesome. Probably my favorite so far. It's 100% within the spirit of the question, and extremely terse. (Although, technically, it's not a callable function, so it's really only 99% within the spirit of the question. It's 4 more characters to make it an actual function definition then?) –  Todd Lehman Jul 27 at 1:10

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

share|improve this answer
    
Nice. I can see how to shorten that by 1 character with either of {int r=-1;for(;n;n/=2)r++;return r;} or {int r=0;for(;n;n/=2)r++;return--r;}, but I can't see how to go any shorter than that. –  Todd Lehman Jul 26 at 23:35
3  
make it a ternary-recursive? return n?l(n/2)+1:-1; –  Kyle McCormick Jul 27 at 1:34
    
Daaaayammm, guys!! That is amazing work. That's not just creative; that's sick genius right there. –  Todd Lehman Jul 27 at 8:21

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)); 
}
share|improve this answer
    
Wicked cool. Can this method be adapted to use long double instead of __float128, assuming your compiler's long double is at least 80 bits? Because I know that at least on my compiler, which has long double of 80 bits, it works fine for all 64-bit unsigned integers to do return (int)log2l(x);. –  Todd Lehman Jul 26 at 21:16
1  
@Todd If your 80-bit long double can hold the 64-bit integer without rounding (I believe most do) you should be able to adapt this. I went with the first thing I found, some of the definitions were a bit vague, and it was guaranteed to work with 128 bits, so I didn't waste much time looking at 80 bits. You'll still need an integer larger than 64 to cast your 80-bit float into, though (unless you cast it into an array.) You might get away with casting to a 64 bit integer on big-endian machines, which are more likely to throw away the least significant bits than the most significant bits. –  steveverrill Jul 26 at 22:23

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]
share|improve this answer
    
Ah, a recursive solution! Very nice. –  Todd Lehman Jul 27 at 8:17
    
Of course, recursion is the bread and butter of haskell –  proud haskeller Jul 31 at 9:36

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
$ 
share|improve this answer
    
Ha! NICE. Wasn't expecting something like that! –  Todd Lehman Jul 26 at 23:18

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.

share|improve this answer

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
}
share|improve this answer
    
Nice. Both of these run in essentially constant time then? Given that log₂64 is constant, that is? –  Todd Lehman Jul 27 at 4:53
    
Hey, it looks like you can shave off 5 additional characters from the (original version of) body of your looping version by doing this: int i=32,r=-!n;for(;i;i/=2)n>=1LL<<i?r+=i,n>>=i:0;return r;. That gets you down under 80 characters (to 78, if I'm subtracting correctly)! –  Todd Lehman Jul 27 at 5:15
1  
@ToddLehman - thanks changed - left the bitops in the unwound version (compiler normally does this for factors of 2 anyhow). I added the lookup table versions for systems where jumps are expensive compared to memory access. It will vary with architecture. Putting them as an inline const vs using a local variable helps with locality to try to prevent cache misses. –  technosaurus Jul 27 at 5:28
1  
@ToddLehman nice, I used it to put together this macro that optimizes well for any integer type #define MSB(x) do{int i=(sizeof(x)*8),r=-!x;while(i>>=1)x>>i?x>>=i,r+=i:0;x=r;}while(0) –  technosaurus Jul 27 at 7:01
1  
@ToddLehman the compilers did not optimize /2 very well but with the sizeof part it can do any integer type without extra jumps .... oddly you can calculate the number of jumps by passing the number of bits to itself –  technosaurus Jul 27 at 17:01

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
share|improve this answer
    
This converts n to a base-2 string and measures the length? –  Todd Lehman Jul 27 at 3:21
    
@Todd Yep! Also, it has to handle 0 as a special case. –  Tim S. Jul 27 at 3:27

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%
share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.