# Find the number of leading zeroes in a 64-bit integer

Problem:

Find the number of leading zeroes in a 64-bit signed integer

Rules:

• The input cannot be treated as string; it can be anything where math and bitwise operations drive the algorithm
• The output should be validated against the 64-bit signed integer representation of the number, regardless of language
• Default code golf rules apply
• Shortest code in bytes wins

Test cases:

These tests assume two's complement signed integers. If your language/solution lacks or uses a different representation of signed integers, please call that out and provide additional test cases that may be relevant. I've included some test cases that address double precision, but please feel free to suggest any others that should be listed.

input                output   64-bit binary representation of input (2's complement)
-1                   0        1111111111111111111111111111111111111111111111111111111111111111
-9223372036854775808 0        1000000000000000000000000000000000000000000000000000000000000000
9223372036854775807  1        0111111111111111111111111111111111111111111111111111111111111111
4611686018427387903  2        0011111111111111111111111111111111111111111111111111111111111111
1224979098644774911  3        0001000011111111111111111111111111111111111111111111111111111111
9007199254740992     10       0000000000100000000000000000000000000000000000000000000000000000
4503599627370496     11       0000000000010000000000000000000000000000000000000000000000000000
4503599627370495     12       0000000000001111111111111111111111111111111111111111111111111111
2147483648           32       0000000000000000000000000000000010000000000000000000000000000000
2147483647           33       0000000000000000000000000000000001111111111111111111111111111111
2                    62       0000000000000000000000000000000000000000000000000000000000000010
1                    63       0000000000000000000000000000000000000000000000000000000000000001
0                    64       0000000000000000000000000000000000000000000000000000000000000000

• Welcome to PPCG! What's the reason behind "the input cannot be treated as string"? This disqualifies all languages that can't handle 64-bit integers and is unlikely to lead to more answers that take an integer, because this is the straightforward way when available anyway. Commented Dec 9, 2018 at 23:26
• Can we return False instead of 0?
– Jo King
Commented Dec 9, 2018 at 23:33
• @Arnauld There are already similar questions here and on other sites that specifically call for string-based solutions, but nothing that opens the question to math and logical operations. My hope is to see a bunch of different approaches to this problem that are not already answered elsewhere. Should this be opened to string solutions as well to be all-inclusive?
– Dave
Commented Dec 9, 2018 at 23:40
• Several CPUs including x86 and ARM have specific instructions for this (x86 actually have several). I've always wondered why programming languages don't expose this feature since in most programming languages today you can't invoke assembly instructions. Commented Dec 10, 2018 at 5:43
• @user202729 I think I worded this poorly: 'The output should be validated against the 64-bit signed integer representation of the number, regardless of language' What I mean by that is that this question defines the number of zeros as the number of zeros in a 64-bit signed integer. I guess I made that constraint to eliminate signed vs unsigned integers.
– Dave
Commented Dec 11, 2018 at 0:26

# x86_64 machine language on Linux, 6 bytes

0:       f3 48 0f bd c7          lzcnt  %rdi,%rax
5:       c3                      ret


Requires Haswell or K10 or higher processor with lzcnt instruction.

Try it online!

• Builtins strike again /s
– user36046
Commented Dec 10, 2018 at 2:06
• I recommend specifying the calling convention used (though you did say on Linux)
– qwr
Commented Dec 12, 2018 at 8:02
• @qwr It looks like SysV calling convention because the parameter is passed in %rdi and it is returned in %rax.
– user36046
Commented Dec 15, 2018 at 4:21

# Hexagony, 78 70 bytes

2"1"\.}/{}A=<\?>(<$\*}[_(A\".{}."&.'\&=/.."!=\2'%<..(@.>._.\=\{}:"<><$


Try it online!

Isn't this challenge too trivial for a practical language? ;)

side length 6. I can't fit it in a side length 5 hexagon.

### Explanation

• I laughed really hard at the "explanation". :D Commented Dec 10, 2018 at 18:45
• I think you may have overcomplicated handling negative numbers/zero. I managed to fit a similar program into side length 5 by not doing that hefty 2^64 calculation. It clearly isn't well golfed yet, though! Commented Dec 10, 2018 at 22:56
• @fry Ah right, negative numbers always have 0 leading zeroes... which definitely leads to shorter program because generates 2^64 is long. Commented Dec 11, 2018 at 5:39

# Python, 31 bytes

lambda n:67-len(bin(-n))&~n>>64


Try it online!

The expresson is the bitwise & of two parts:

67-len(bin(-n)) & ~n>>64


The 67-len(bin(-n)) gives the correct answer for non-negative inputs. It takes the bit length, and subtracts from 67, which is 3 more than 64 to compensate for the -0b prefix. The negation is a trick to adjust for n==0 using that negating it doesn't produce a - sign in front.

The & ~n>>64 makes the answer instead be 0 for negative n. When n<0, ~n>>64 equals 0 (on 64-bit integers), so and-ing with it gives 0. When n>=0, the ~n>>64 evaluates to -1, and doing &-1 has no effect.

Python 2, 36 bytes

f=lambda n:n>0and~-f(n/2)or(n==0)*64


Try it online!

Arithmetical alternative.

# C (gcc), 14 bytes

__builtin_clzl


Works fine on tio

# C (gcc), 35 29 bytes

f(long n){n=n<0?0:f(n-~n)+1;}


Try it online!

Than Dennis for 6 bytes

# C (gcc) compiler flags, 29 bytes by David Foerster

-Df(n)=n?__builtin_clzl(n):64

Try it online!

• Worth noting that it's only for 64-bit machines (or any others with LP64/ILP64/etc. ABI) Commented Dec 10, 2018 at 6:43
• Geez, that’s even shorter than any use of the GCC built-in __builtin_clzl with which I can come up. Commented Dec 10, 2018 at 11:49
• @Ruslan: good point, on systems where long is 32 bits (including Windows x64), you need __builtin_clzll (unsigned long long). godbolt.org/z/MACCKf. (Unlike Intel intrinsics, GNU C builtins are supported regardless of the operation being doable with one machine instruction. On 32-bit x86, clzll compiles to a branch or cmov to do lzcnt(low half)+32 or lzcnt(high half). Or bsr if lzcnt isn't available. Commented Dec 12, 2018 at 1:00
• The test cases include "0" but __builtin_clz(l)(l) is undefined behavior for zero: "If x is 0, the result is undefined." Commented Dec 12, 2018 at 13:36
• @MCCCS If it works, it counts. That's also why I keep the last answer
– l4m2
Commented Dec 12, 2018 at 13:43

# Java 8, 32 26 bytes.

Long::numberOfLeadingZeros

Builtins FTW.

-6 bytes thanks to Kevin Cruijssen

Try it online!

• Ah, completely forgot about numberOfLeadingZeros.. You can golf it to 28 bytes btw: n->n.numberOfLeadingZeros(n) Commented Dec 10, 2018 at 10:43
• Actually, Long::numberOfLeadingZeros is even shorter (26 bytes). Commented Dec 10, 2018 at 10:46
• Wow, it doesn't happen very often that Java beats Python. Congrats! Commented Dec 10, 2018 at 18:46

# JavaScript (Node.js), 25 bytes

Takes input as a BigInt literal.

f=x=>x<0?0:x?f(x/2n)-1:64


Try it online!

Or 24 bytes by returning false instead of $$\0\$$.

• Wouldn't n=>n<1?0:n.toString(2)-64 perform the same? Commented Dec 10, 2018 at 12:59
• @IsmaelMiguel I suppose you meant n=>n<1?0:n.toString(2).length-64, but that would not work anyway. This would, I think. Commented Dec 10, 2018 at 13:28
• @IsmaelMiguel No worries. :) It's indeed possible to have the .toString() approach working, but we still need a BigInt literal as input. Otherwise, we only have 52 bits of mantissa, leading to invalid results when precision is lost. Commented Dec 10, 2018 at 13:48
• The fact that the BigInt suffix is the same character as your parameter is very confusing...
– Neil
Commented Dec 11, 2018 at 9:25
• @Neil Unreadable code on PPCG?? This can't be! Fixed! :p Commented Dec 11, 2018 at 12:04

# Python 3, 34 bytes

f=lambda n:-1<n<2**63and-~f(2*n|1)


Try it online!

0{[:I.1,~(64$2)#:]  Try it online! # J, 19 bytes 1#.[:*/\0=(64$2)#:]


Try it online!

## Explanation:

                #:  - convert
] - the input to
(64$2) - 64 binary digits = - check if each digit equals 0 - zero [:*/\ - find the running product 1#. - sum  • 1#.[:*/\1-_64{.#: (17) is close but doesn't work for negative numbers :( Commented Dec 10, 2018 at 22:12 • @Conor O'Brien Nice approach too! Commented Dec 11, 2018 at 4:41 # Perl 6, 18 bytes -2 bytes thanks to Jo King 64-(*%2**64*2).msb  Try it online! # Ruby, 22 bytes ->n{/[^0]/=~"%064b"%n}  Try it online! • Could you explain? Commented Mar 10, 2019 at 6:21 • Another one that counts chars in a string🤷🏻‍♀️ Commented Jun 21, 2022 at 14:33 # 05AB1E, 10 9 bytes ·bg65αsd*  I/O are both integers Explanation: · # Double the (implicit) input # i.e. -1 → -2 # i.e. 4503599627370496 → 9007199254740992 b # Convert it to binary # i.e. -2 → "ÿ0" # i.e. 9007199254740992 → 100000000000000000000000000000000000000000000000000000 g # Take its length # i.e. "ÿ0" → 2 # i.e. 100000000000000000000000000000000000000000000000000000 → 54 65α # Take the absolute different with 65 # i.e. 65 and 2 → 63 # i.e. 65 and 54 → 11 s # Swap to take the (implicit) input again d # Check if it's non-negative (>= 0): 0 if negative; 1 if 0 or positive # i.e. -1 → 0 # i.e. 4503599627370496 → 1 * # Multiply them (and output implicitly) # i.e. 63 and 0 → 0 # i.e. 11 and 1 → 11  # Haskell, 56 bytes Thanks xnor for spotting a mistake! f n|n<0=0|1>0=sum.fst.span(>0)$mapM(pure[1,0])[1..64]!!n


Might allocate quite a lot of memory, try it online!

Maybe you want to test it with a smaller constant: Try 8-bit!

## Explanation

Instead of using mapM(pure[0,1])[1..64] to convert the input to binary, we'll use mapM(pure[1,0])[1..64] which essentially generates the inverted strings $$\\lbrace0,1\rbrace^{64}\$$ in lexicographic order. So we can just sum the $$\1\$$s-prefix by using sum.fst.span(>0).

# Powershell, 51 bytes

param([long]$n)for(;$n-shl$i++-gt0){}($i,65)[!$n]-1  Test script: $f = {

param([long]$n)for(;$n-shl$i++-gt0){}($i,65)[!$n]-1 } @( ,(-1 ,0 ) ,(-9223372036854775808 ,0 ) ,(9223372036854775807 ,1 ) ,(4611686018427387903 ,2 ) ,(1224979098644774911 ,3 ) ,(9007199254740992 ,10) ,(4503599627370496 ,11) ,(4503599627370495 ,12) ,(2147483648 ,32) ,(2147483647 ,33) ,(2 ,62) ,(1 ,63) ,(0 ,64) ) | % {$n,$expected =$_
$result = &$f $n "$($result-eq$expected): $result" }  Output: True: 0 True: 0 True: 1 True: 2 True: 3 True: 10 True: 11 True: 12 True: 32 True: 33 True: 62 True: 63 True: 64  # Java 8, 38 bytes int f(long n){return n<0?0:f(n-~n)+1;}  Input as long (64-bit integer), output as int (32-bit integer). Port of @l4m2's C (gcc) answer. Try it online. Explanation:  int f(long n){ // Recursive method with long parameter and integer return-type return n<0? // If the input is negative: 0 // Return 0 : // Else: f(n-~n) // Do a recursive call with n+n+1 +1 // And add 1  EDIT: Can be 26 bytes by using the builtin Long::numberOfLeadingZeros as displayed in @lukeg's Java 8 answer. # APL+WIN, 34 bytes +/×\0=(0>n),(63⍴2)⊤((2*63)××n)+n←⎕  Explanation: n←⎕ Prompts for input of number as integer ((2*63)××n) If n is negative add 2 to power 63 (63⍴2)⊤ Convert to 63 bit binary (0>n), Concatinate 1 to front of binary vector if n negative, 0 if positive +/×\0= Identify zeros, isolate first contiguous group and sum if first element is zero  # C# (Visual C# Interactive Compiler), 42 bytes x=>x!=0?64-Convert.ToString(x,2).Length:64  Try it online! # C# (Visual C# Interactive Compiler), 31 bytes int c(long x)=>x<0?0:c(x-~x)+1;  Even shorter, based off of @l4m2's C (gcc) answer. Never knew that you could declare functions like that, thanks @Dana! Try it online! • I think this is valid? tio.run/##ZZA/… – dana Commented Dec 11, 2018 at 13:17 # Jelly, 10 9 bytes -1 thanks to a neat trick by Erik the Outgolfer (is-non-negative is now simply AƑ) ḤBL65_×AƑ  A monadic Link accepting an integer (within range) which yields an integer. Try it online! Or see the test-suite. The 10 was ḤBL65_ɓ>-× Here is another 10 byte solution, which I like since it says it is "BOSS"... BoṠS»-~%65  Test-suite here ...BoṠS63r0¤i, BoṠS63ŻṚ¤i, or BoṠS64ḶṚ¤i would also work. Another 10 byter (from Dennis) is æ»64ḶṚ¤Äċ0 (again æ»63r0¤Äċ0 and æ»63ŻṚ¤Äċ0 will also work) • 9 bytes Commented Dec 11, 2018 at 18:18 • @EriktheOutgolfer I thought to myself "there must be a golfier way to multiply by isNonNegative" and didn't think of the Ƒ quick at all, very nice work! Commented Dec 11, 2018 at 19:11 • Actually, I've been theorizing about AƑ for quite some while now. Be warned that it doesn't vectorize! ;-) It's actually "flatten and then check if all elements are nonnegative". Commented Dec 11, 2018 at 19:14 # Perl 5, 37 bytes sub{sprintf("%064b",@_)=~/^0*/;$+[0]}


Try it online!

Or this 46 bytes if the "stringification" is not allowed: sub z

sub{my$i=0;$_[0]>>64-$_?last:$i++for 1..64;$i}  • s/length$&/$+[0]/ (-3 bytes) ;) – Dada Commented Dec 10, 2018 at 12:59 • IMO, you're not allowed to remove the sub keyword from answers containing Perl 5 functions. Commented Dec 10, 2018 at 14:36 • I've seen whats similar to removing sub in answers for other languages, perl6, powershell and more. Commented Dec 10, 2018 at 14:58 • In Perl6, I think you don't need sub{} to make a (anonymous?) sub, which explain why it's omitted from Perl6 answers. I agree with @nwellnhof that you shouldn't be allowed to remove sub. (when I was still active, like a year ago or so, that was the rule) – Dada Commented Dec 10, 2018 at 15:03 • changed now. And included $+[0]. Commented Dec 10, 2018 at 15:10

# Swift (on a 64-bit platform), 41 bytes

Declares a closure called f which accepts and returns an Int. This solution only works correctly 64-bit platforms, where Int is typealiased to Int64. (On a 32-bit platform, Int64 can be used explicitly for the closure’s parameter type, adding 2 bytes.)

# Wolfram Language (Mathematica), 41 bytes

The formula for positive numbers is just 63-Floor@Log2@#&. Replacement rules are used for the special cases of zero and negative input.

The input need not be a 64-bit signed integer. This will effectively take the floor of the input to turn it into an integer. If you input a number outside of the normal bounds for a 64-bit integer, it will tell return a negative number indicating how many more bits would be needed to store this integer.

63-Floor@Log2[#/.{_?(#<0&):>2^63,0:>.5}]&


Try it online!

@LegionMammal978's solution is quite a bit shorter at 28 bytes. The input must be an integer. Per the documentation: "BitLength[n] is effectively an efficient version of Floor[Log[2,n]]+1. " It automatically handles the case of zero correctly reporting 0 rather than -∞.

# Wolfram Language (Mathematica), 28 bytes

Boole[#>=0](64-BitLength@#)&


Try it online!

• Boole[#>=0](64-BitLength@#)& is a good bit shorter at 28 bytes. It uses the same basic concept as yours, but applies BitLength and Boole. Commented Dec 12, 2018 at 2:13
• I totally forgot about BitLength! Commented Dec 14, 2018 at 2:29

bitNumber - math.ceil (math.log(number) / math.log(2))

e.g 64 bit NUMBER : 9223372036854775807 math.ceil (math.log(9223372036854775807) / math.log(2)) ANS: 63

• If you could add the language name to this, that would be great,as people are likely to down vote answers that don't have the language name included Commented Nov 8, 2019 at 9:44

# K (ngn/k), 12 bytes

+/&\~(64#2)\


Try it online!

(64#2)\ encode the argument as 64 bits

~ bitwise not

&\ cumulative boolean and

+/ sum

• # = length ... looks string based Commented Dec 13, 2018 at 14:37
• @Titus 2\  gives a list of integers and # finds its length. no strings are involved here.
– ngn
Commented Dec 13, 2018 at 15:38

# Charcoal, 15 bytes

Ｉ⁻⁶⁴Ｌ↨﹪ＮＸ²¦⁶⁴¦²


Try it online! Link is to verbose version of code. Explanation:

    Ｌ           Length of
Ｎ        Input as a number
﹪         Modulo
²      Literal 2
Ｘ       To the power
⁶⁴   Literal 64
↨          Converted to base
² Literal 2
⁻              Subtracted from
⁶⁴            Literal 64
Ｉ               Cast to string
Implicitly print


The ¦s serve to separate adjacent integer literals. Conveniently, Charcoal's arbitrary numeric base conversion converts 0 into an empty list, however for negative numbers it simply inverts the sign of each digit, so the number is converted to the equivalent unsigned 64-bit integer first.