# Base-2 integer logarithm of 64-bit unsigned integer

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!
• 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 Ender Jul 26 '14 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 '14 at 19:30
• @MartinBüttner — Actually, went ahead and deleted both examples. – Todd Lehman Jul 26 '14 at 19:33
• 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. – Level River St Jul 26 '14 at 19:36
• 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. – Level River St Jul 26 '14 at 21:09

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

• 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 '14 at 21:16
• @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. – Level River St Jul 26 '14 at 22:23

# 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

• 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 '14 at 23:35
• make it a ternary-recursive? return n?l(n/2)+1:-1; – A Frayed Knot Jul 27 '14 at 1:34
• Daaaayammm, guys!! That is amazing work. That's not just creative; that's sick genius right there. – Todd Lehman Jul 27 '14 at 8:21

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]

• Ah, a recursive solution! Very nice. – Todd Lehman Jul 27 '14 at 8:17
• Of course, recursion is the bread and butter of haskell – proud haskeller Jul 31 '14 at 9:36

# 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/}/,(

• 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 '14 at 0:54
• 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. – A Frayed Knot Jul 27 '14 at 1:01
• 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 '14 at 1:02
• 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. – A Frayed Knot Jul 27 '14 at 1:07
• 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 '14 at 1:10

# 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.

# APL (Dyalog Unicode), 7 bytes

⌊2⍟.5∘⌈


Try it online!

# APL (Dyalog Unicode), 13 bytes

{⍵=0:¯1⋄⌊2⍟⍵}


Try it online! (Courtesy of Adám.)

• It's 13 bytes because it uses it's own code page – lyxal Aug 17 '20 at 2:11
• Try it online! – lyxal Aug 17 '20 at 2:12
• Gotcha. I'll keep a note of that. – Razetime Aug 17 '20 at 2:13
• -6: ⌊2⍟.5∘⌈ – Adám Aug 19 '20 at 12:25
• A month late, but I'll add it in lmao – Razetime Sep 20 '20 at 10:30

# 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
$ • Ha! NICE. Wasn't expecting something like that! – Todd Lehman Jul 26 '14 at 23:18 # 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  • your solution only 9 characters according to the usual scoring rules as you can omit the braces. – FUZxxl Feb 15 '15 at 20:41 # x86_64 machine language on Linux, 11 8 bytes 0x0: 83 C8 FF or eax, -1 0x3: 48 0F BD C7 bsf rax, rdi 0x7: C3 ret  -3 thanks to @PeterCordes This uses the "bit scan reverse" instruction to put the index of the most significant 1 bit in rax. The or eax, -1 is to handle the case of zero input. This version no longer depends on ABM or BMI1 instructions and should work on all x86_64 processors. To Try it online!, compile and run the following C code (*f)()="\x83\xc8\xff" // or eax, -1 "\x48\x0f\xbd\xc7" // bsr rax, rdi "\xc3"; // ret main(){ printf("%d\n",f(0)); printf("%d\n",f(1)); printf("%d\n",f(2)); printf("%d\n",f(3)); printf("%d\n",f(4)); printf("%d\n",f(7)); printf("%d\n",f(8)); printf("%d\n",f(16)); printf("%d\n",f(65535)); printf("%d\n",f(65536)); printf("%d\n",f(18446744073709551615)); }  • You can use a global-scope asm statement to write a function in asm (instead of manually-encoded machine code), and there's no need to use an ugly hack like a function-pointer to a string literal because you're golfing the machine code, not the C representation of it; that's just a test harness. tio.run/… – Peter Cordes Sep 19 '20 at 21:04 • bsr with a zero input leaves the destination unmodified (AMD documents this; Intel implements it in practice but documents is as "undefined"; that's why bsr/bsf, and even lzcnt/tzcnt/popcnt, have false dependencies on the output register), and otherwise 63-lzcnt = bsr, the bit-index of the highest set bit. Alternatively; gcc's trick of "xor$0x3f, %eax\n" bit-scan result instead of 63-x almost works, but not for EAX=64. Anyway, BSR is shorter than LZCNT, so it's a win if you don't mind de-facto standard behaviour that only AMD documents. – Peter Cordes Sep 19 '20 at 21:19
• 8 bytes: or eax,-1 / bsr rax, rdi / ret tio.run/… – Peter Cordes Sep 19 '20 at 21:21
• More about BSF/BSR output dependency: Why does breaking the "output dependency" of LZCNT matter? / VS: unexpected optimization behavior with _BitScanReverse64 intrinsic (quotes and links AMD's manual, but C intrinsics don't expose that unmodified-output functionality) – Peter Cordes Sep 19 '20 at 21:33

## 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.

• lambda x:len(bin(x))-3if x else-1 is what I came up with, but since it's so similar to yours, I'll give it as a golf tip. f=lambda x:x and len(bin(x))-3or-1 this would work, except that the output is 0 for 1, so it will incorrectly return -1. – mbomb007 Jul 2 '15 at 18:43

# 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
}

• Nice. Both of these run in essentially constant time then? Given that log₂64 is constant, that is? – Todd Lehman Jul 27 '14 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 '14 at 5:15
• @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 '14 at 5:28
• @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 '14 at 7:01
• @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 '14 at 17:01

# 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. ## 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. • This is really clever! Nice solution. Fun to see! – Todd Lehman Jan 12 '15 at 5:15 • Technically, these don't work as the calculators' floats are not precise enough to store 64 bits. If we allow them, then sum(Ans≥2^randIntNoRep(1,63 would also work. – lirtosiast Jul 2 '15 at 16:48 # Rust, 28 bytes |n|63-n.leading_zeros()as i8  Try it on the Rust Playground! An anonymous function that takes in a u64 and outputs the answer as an i8. Change 63 to 127 and it'll work for u128s too. # x87 machine code, 27 23 bytes Binary: 00000000: 9bd9 2e15 01d9 e8df 2cd9 f1df 1cad 85c0 ........,....... 00000010: 7902 f7d0 c37f 0f y......  Listing: 9B D9 2E 013F FLDCW CW ; set FPU CW register for floor rounding D9 E8 FLD1 ; 1 * multplier into ST(1) DF 2C FILD QWORD PTR[SI] ; load input into ST(0) D9 F1 FYL2X ; ST(0) = ST(1) * log2( ST(0) ) DF 1C FISTP WORD PTR[SI] ; store result into [SI] AD LODSW ; result into AX 85 C0 TEST AX, AX ; was result negative (zero divide)? 79 02 JNS OKAY ; if not, return result F7 D0 NOT AX ; otherwise, negate AX (AL = -1) OKAY: C3 RET ; return to caller 0F7F CW DW 0F7FH ; x87 control word to round down  Callable function input as 64 bit signed QWORD at [SI], output in AL. Size notes: checking for Zero and returning an explicit -1 costs 6 bytes. Also, setting FPU to floor rounding costs 7 bytes. Input/Output from test program: ## ARMv8, 24 12 bytes OakSim is technically an ARMv7 simulator, but if you want to test all test cases except for the last, you can still use it as reference. The register widths of ARMv7 are 32 bit. I haven't found a good ARMv8 simulator yet, but the instruction set is backwards compatible, and the register widths should be 64 bit long. Hexdump: 0x00010000: 10 0F 6F E1 3F 00 60 E2 1E FF 2F E1 ..o.?..../.  (If you're testing on OakSim's ARMv7, here is the respective hexdump:) 0x00010000: 10 0F 6F E1 1F 00 60 E2 1E FF 2F E1 ..o....../.  ## Explanation This is a procedure that expects the argument in r0. Output goes to r0. This expects the address of the caller in lr, as per the ATPCS (ARM Thumb Procedure Call Standard). log: /* Name of our function */ clz r0, r0 /* r0 = Count Leading Zeroes in r0 */ rsb r0, r0, 63 /* r0 = 63 - r0 */ /* change this number to 31 if you're testing on ARMv7 */ bx lr /* Branch back to caller */  Example call: b test /* Skip over this procedure */ log: /* ommitted to save space */ test: mov r0, 0 /* Set input argument to e.g. 0 */ mov lr, pc /* Set lr to address of program counter */ b log /* Jump to the procedure */  • Note that ARMv8 is an entirely different instruction set than ARMv7. The encoding is different as well. – FUZxxl Nov 24 '20 at 20:55 # K (ngn/k), 6 bytes -1+#2\  Try it online! Uses "The log base 2 of an integer is the same as the position of the highest bit set" as outlined here. • #2\ get the position of the highest bit set • -1+ subtract one If it's ok for an input of 0 to return 0 instead of -1, #1_2\ can be used to save a byte. # Risky, 5 bytes {?+0-_?:0  Try it online! Uses a built-in log2 function, but since it operates on integers, it's technically allowed. ## Explanation {?+0-_?:0 { log2( ? input + + 0 0 ) - - _ ( ? input : = 0 0 )  # Risky, 7 bytes !_?}_2-__2-:?  Try it online! Doesn't use a built-in log2 function. ## Explanation !_?}_2-__2-:? ! length( _ ( ? input ) } base-convert _ ( 2 2 ) ) - - _ ( _ ( 2 2 ) - - : (0 ≠ ? input ) )  ## 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  • This converts n to a base-2 string and measures the length? – Todd Lehman Jul 27 '14 at 3:21 • @Todd Yep! Also, it has to handle 0 as a special case. – Tim S. Jul 27 '14 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%  # 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;}


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. # MMIX, 16 bytes (4 instrs) Essentially the same as the C answer, except it forces round-down and therefore can use a 64-bit float. 00000000: 0a000300 e400c010 3d000034 f8010000 ½¡¤¡ỵ¡ĊÑ=¡¡4ẏ¢¡¡  log2 FLOTU$0,ROUND_DOWN,$0 INCH$0,#C010
SR     $0,$0,52
POP    1,0


# Pxem, 56 bytes (content)

Unprintables are as backslash followed by its code point in octal.

.c.w\000\001\001.v.c.t.y\002.!.c.m.v\001.+.v.a.m.z\001.-XX.a.v.n.d.a.s-1.p


## Usage

• Call this subroutine after setting only one item as input.
• Outputs the result to STDOUT instead of returning, as Pxem cannot have negative values unless given from STDIN.
• Some garbages may return.

XX.z
# if top is not zero; then
.c.wXX.z
# stack usage: input, 2^counter, counter(initially zero)
.a\000\001\001.v.c.tXX.z
# while input is greater than 2^counter; do
.a.yXX.z
# increment counter; done
.a\002.!.c.m.v\001.+.v.aXX.z
# if input differs from 2^counter; then decrement counter; fi
.a.m.z\001.-XX.aXX.z
# output counter; return
.a.v.n.dXX.z
# done; output minus one
.a.a.s-1.p


Try it online!

# Jelly, 5 bytes

BL’_¬


Try it online!

## Explanation

BL’_¬ Main monadic link
B     Convert to binary
L    Length
’   Decrement
_  Subtract
¬   the argument negated

• Clever solution! Nice! – Todd Lehman Jun 16 at 17:44

# JavaScript (Node.js), 17 bytes

n=>n?1+f(n/2n):-1


Try it online!

Similar

• Holy crap, that's brilliant! – Todd Lehman Jun 16 at 17:44

# PowerShell Core, 38 bytes

param($a)for(;$a){$a=$a-shr1;$i++}$i-1


Try it online!

With a filter for 39 bytes

Longer and incorrect results with the built-ins :eyes:

## Explanation

param($a)for(;$a){ # while a is not 0
$a=$a-shr1         # shift right by 1 the bits of a
$i++} # increases the counter i by 1$i-1               # outputs the counter minus one


# Julia, 23 bytes

!x=ndigits(2x,base=2)-2


Try it online!

If[#<1,-1,#0[#/2]+1]&