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

Question

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

Answer 1

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!

Answer 2

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

Answer 3

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.

Answer 4

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!

Answer 5

Java 8, 32 26 bytes.

Long::numberOfLeadingZeros

Builtins FTW.

-6 bytes thanks to Kevin Cruijssen

Try it online!

Answer 6

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\$.

Answer 7

Perl 6, 35 28 26 bytes

-2 bytes thanks to nwellnhof

{to .fmt("%064b")~~/^0*/:}

Try it online!

Anonymous code block that takes a number and returns a number. This converts the number to a binary string and counts the leading zeroes. It works for negative numbers because the first character is a - e.g. -00000101, so there are no leading zeroes.

Explanation:

{                        }  # Anonymous code block
    .fmt("%064b")           # Format as a binary string with 64 digits
                 ~~         # Smartmatch against
                   /^0*/    # A regex counting leading zeroes
 to                     :   # Return the index of the end of the match

Answer 8

Python 3, 34 bytes

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

Try it online!

Answer 9

J, 18 bytes

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

Answer 10

Perl 6, 18 bytes

-2 bytes thanks to Jo King

64-(*%2**64*2).msb

Try it online!

Answer 11

Ruby, 22 bytes

->n{/[^0]/=~"%064b"%n}

Try it online!

Answer 12

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

Answer 13

05AB1E, 10 9 bytes

·bg65αsd*

I/O are both integers

Try it online or verify all test cases.

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

Answer 14

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)

Answer 15

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

Answer 16

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.

Answer 17

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

Answer 18

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!

Answer 19

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

let f:(Int)->Int={$0.leadingZeroBitCount}

In Swift, even the fundamental integer type is an ordinary object declared in the standard library. This means Int can have methods and properties, such as leadingZeroBitCount (which is required on all types conforming to the standard library’s FixedWidthInteger protocol).

Answer 20

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}

Answer 21

Haskell, 24 bytes

f n|n<0=0
f n=1+f(2*n+1)

Try it online!

This is basically the same as Kevin Cruijssen's Java solution, but I found it independently.

The argument should have type Int for a 64-bit build, or Int64 for anything.

Explanation

If the argument is negative, the result is immediately 0. Otherwise, we shift left, filling in with ones, until we reach a negative number. That filling lets us avoid a special case for 0.

Just for reference, here's the obvious/efficient way:

34 bytes

import Data.Bits
countLeadingZeros

Answer 22

Clean, 103 bytes

Uses the same "builtin" as ceilingcat's answer.

f::!Int->Int
f _=code {
instruction 243
instruction 72
instruction 15
instruction 189
instruction 192
}

Try it online!

Clean, 58 bytes

import StdEnv
$0=64
$i=until(\e=(2^63>>e)bitand i<>0)inc 0

Try it online!

Answer 23

Stax, 10 bytes

în»╧3(∞┼⌠g

Run and debug it

It's a port of Kevin's 05AB1E solution.

Answer 24

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!

Answer 25

Perl 5 -p, 42 bytes

1while$_>0&&2**++$a-1<$_;$_=0|$_>=0&&64-$a

Try it online!

Longer than a bitstring based solution, but a decent math based solution.

Answer 26

APL(NARS), 15 chars, 30 bytes

{¯1+1⍳⍨⍵⊤⍨64⍴2}

test for few numbers for see how to use:

  f←{¯1+1⍳⍨⍵⊤⍨64⍴2}
  f ¯9223372036854775808
0
  f 9223372036854775807
1

Answer 27

Rust, 18 bytes

i64::leading_zeros

Try it online!

Answer 28

K (ngn/k), 6 bytes

64-#2\

Try it online!

2\ encode the argument in binary

# length

64- subtract from 64

Answer 29

PHP, 50 46 bytes

for(;0<$n=&$argn;$n>>=1)$i++;echo$n<0?0:64-$i;

Run as pipe with -R or try it online,

<?=$argn<0?0:0|64-log($argn+1,2); has rounding issues; so I took the long way.

Answer 30

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

Answer 31

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.

Answer 32

Java 8, 49 bytes (broken)

I misread the problem, check back later for a new solution

n->{int i=0;while(n%10==0){n/=10;i++;}return i;};

Try it online!
I opted for a loop-based solution instead of recursion or built-ins.