Problema:

Encuentre el número de ceros a la izquierda en un entero con signo de 64 bits

Reglas:

• La entrada no se puede tratar como una cadena; puede ser cualquier cosa donde las operaciones matemáticas y bit a bit conducen el algoritmo
• La salida se debe validar con la representación de número entero con signo de 64 bits del número, independientemente del idioma
• Se aplican las reglas de golf del código predeterminado
• El código más corto en bytes gana

Casos de prueba:

Estas pruebas suponen números enteros con signo de complemento a dos. Si su idioma / solución carece o utiliza una representación diferente de enteros con signo, por favor llame y proporcione casos de prueba adicionales que puedan ser relevantes. He incluido algunos casos de prueba que abordan la precisión doble, pero no dude en sugerir cualquier otro que deba enumerarse.

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

lenguaje de máquina x86_64 en Linux, 6 bytes

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

Requiere un procesador Haswell o K10 o superior con lzcntinstrucciones.

Pruébalo en línea!

Hexagonía , 78 70 bytes

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

Pruébalo en línea!

¿No es este desafío demasiado trivial para un lenguaje práctico? ;)

_{longitud lateral 6. No puedo colocarlo en un hexágono de longitud lateral 5.}

Explicación

Python , 31 bytes

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

Pruébalo en línea!

El expresson es el bit a bit &de dos partes:

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

El 67-len(bin(-n))da la respuesta correcta para entradas no negativas. Toma la longitud del bit y resta de 67, que es 3 más que 64 para compensar el -0bprefijo. La negación es un truco para ajustar para n==0usar que negarla no produce una -señal al frente.

El & ~n>>64hace que la respuesta sea 0negativa n. Cuando n<0, ~n>>64es igual a 0 (en enteros de 64 bits), por lo tanto, da como resultado 0. Cuando n>=0, se ~n>>64evalúa -1y hacer &-1no tiene efecto.

Python 2 , 36 bytes

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

Pruébalo en línea!

Alternativa aritmética.

Java 8, 32 26 bytes.

Long::numberOfLeadingZeros

Construido FTW.

-6 bytes gracias a Kevin Cruijssen

Pruébalo en línea!

C (gcc) , 14 bytes

__builtin_clzl

Funciona bien en tio

C (gcc) , 35 29 bytes

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

Pruébalo en línea!

Que Dennis por 6 bytes

Banderas del compilador C (gcc) , 29 bytes por David Foerster

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

Pruébalo en línea!

Perl 6 , 35 28 26 bytes

-2 bytes gracias a nwellnhof

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

Pruébalo en línea!

Bloque de código anónimo que toma un número y devuelve un número. Esto convierte el número en una cadena binaria y cuenta los ceros a la izquierda. Funciona para números negativos porque el primer carácter es un -eg -00000101, por lo que no hay ceros a la izquierda.

Explicación:

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

JavaScript (Node.js) , 25 bytes

Toma la entrada como un literal BigInt.

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

Pruébalo en línea!

$0$

Python 3 , 34 bytes

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

Pruébalo en línea!

J , 18 bytes

0{[:I.1,~(64$2)#:]

Pruébalo en línea!

J , 19 bytes

1#.[:*/\0=(64$2)#:]

Pruébalo en línea!

Explicación:

                #:  - convert 
                  ] - the input to
          (64$2)    - 64 binary digits
         =          - check if each digit equals 
        0           - zero
   [:*/\            - find the running product
1#.                 - sum

Perl 6 , 18 bytes

-2 bytes gracias a Jo King

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

Pruébalo en línea!

Ruby , 22 bytes

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

Pruébalo en línea!

05AB1E , 10 9 bytes

·bg65αsd*

I / O son ambos enteros

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

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

^{Gracias xnor por detectar un error!}

f n|n<0=0|1>0=sum.fst.span(>0)$mapM(pure[1,0])[1..64]!!n

Podría asignar bastante memoria, ¡ pruébelo en línea!

Tal vez quieras probarlo con una constante más pequeña: ¡ Prueba 8 bits!

Explicación

mapM(pure[0,1])[1..64]mapM(pure[1,0])[1..64]$\lbrace0,1\rbrace^{64}$$1$sum.fst.span(>0)

Powershell, 51 bytes

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

Script de prueba:

$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"
}

Salida:

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

Entrada como long(entero de 64 bits), salida como int(entero de 32 bits).

Puerto de respuesta de @ l4m2 C (gcc) .

Pruébalo en línea.

Explicación:

 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

EDITAR: puede tener 26 bytes utilizando el valor incorporado Long::numberOfLeadingZeroscomo se muestra en la respuesta Java 8 de @lukeg .

APL + WIN, 34 bytes

+/×\0=(0>n),(63⍴2)⊤((2*63)××n)+n←⎕

Explicación:

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 # (compilador interactivo de Visual C #) , 42 bytes

x=>x!=0?64-Convert.ToString(x,2).Length:64

Pruébalo en línea!

C # (compilador interactivo de Visual C #) , 31 bytes

int c(long x)=>x<0?0:c(x-~x)+1;

Incluso más corto, basado en la respuesta C (gcc) de @ l4m2. Nunca supe que podría declarar funciones como esa, ¡gracias @Dana!

Pruébalo en línea!

Jalea ,  10  9 bytes

-1 gracias a un buen truco de Erik the Outgolfer (ahora no es negativo simplemente AƑ)

ḤBL65_×AƑ

Un enlace monádico que acepta un número entero (dentro del rango) que produce un número entero.

Pruébalo en línea! O vea el conjunto de pruebas .

El 10 fue ḤBL65_ɓ>-×

Aquí hay otra solución de 10 bytes, que me gusta ya que dice que es "BOSS" ...

BoṠS»-~%65

Test-suite aquí

... BoṠS63r0¤i, BoṠS63ŻṚ¤io BoṠS64ḶṚ¤itambién funcionaría.

Otro 10 byter (de Dennis) es æ»64ḶṚ¤Äċ0(nuevamente æ»63r0¤Äċ0y æ»63ŻṚ¤Äċ0también funcionará)

Perl 5 , 37 bytes

sub{sprintf("%064b",@_)=~/^0*/;$+[0]}

Pruébalo en línea!

O esto 46 bytes si la "cadena" no está permitida: sub z

sub{my$i=0;$_[0]>>64-$_?last:$i++for 1..64;$i}

Swift (en una plataforma de 64 bits), 41 bytes

Declara un cierre llamado fque acepta y devuelve un Int. Esta solución solo funciona correctamente en plataformas de 64 bits, donde Intse typealiasedita Int64. (En una plataforma de 32 bits, Int64se puede usar explícitamente para el tipo de parámetro de cierre, agregando 2 bytes).

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

En Swift, incluso el tipo entero fundamental es un objeto ordinario declarado en la biblioteca estándar. Esto significa que Intpuede tener métodos y propiedades, como leadingZeroBitCount(que se requiere en todos los tipos que se ajustan al FixedWidthIntegerprotocolo de la biblioteca estándar ).

Haskell , 24 bytes

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

Pruébalo en línea!

Esto es básicamente lo mismo que la solución Java de Kevin Cruijssen, pero la encontré de forma independiente.

El argumento debe tener tipo Intpara una compilación de 64 bits, o Int64para cualquier cosa.

Explicación

Si el argumento es negativo, el resultado es inmediatamente 0. De lo contrario, nos desplazamos a la izquierda, rellenando con unos , hasta llegar a un número negativo. Ese relleno nos permite evitar un caso especial para 0.

Solo como referencia, esta es la forma obvia / eficiente:

34 bytes

import Data.Bits
countLeadingZeros

Limpio , 103 bytes

Utiliza el mismo "incorporado" que la respuesta del techo.

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

Pruébalo en línea!

Limpio , 58 bytes

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

Pruébalo en línea!

Stax , 10 bytes

în»╧3(∞┼⌠g

Ejecutar y depurarlo

Es un puerto de la solución 05AB1E de Kevin.

Perl 5 -p , 42 bytes

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

Pruébalo en línea!

Más largo que una solución basada en cadenas de bits, pero una solución basada en matemáticas decente.

APL (NARS), 15 caracteres, 30 bytes

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

prueba para algunos números para ver cómo usar:

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

Óxido, 18 bytes

i64::leading_zeros

Pruébalo en línea!

K (ngn / k) , 6 bytes

64-#2\

Pruébalo en línea!

2\ codificar el argumento en binario

# longitud

64- restar de 64

PHP, 50 46 bytes

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

Ejecutar como tubería -Ro probarlo en línea ,

<?=$argn<0?0:0|64-log($argn+1,2);tiene problemas de redondeo; Así que tomé el camino largo.

Wolfram Language (Mathematica) , 41 bytes

La fórmula para los números positivos es justa 63-Floor@Log2@#&. Las reglas de reemplazo se usan para los casos especiales de entrada cero y negativa.

La entrada no necesita ser un entero con signo de 64 bits. Esto efectivamente tomará el piso de la entrada para convertirlo en un número entero. Si ingresa un número fuera de los límites normales para un entero de 64 bits, le indicará que devuelva un número negativo que indica cuántos bits más se necesitarían para almacenar este entero.

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

Pruébalo en línea!

La solución de @ LegionMammal978 es bastante más corta con 28 bytes. La entrada debe ser un número entero. Según la documentación: " BitLength[n]es efectivamente una versión eficiente de Floor[Log[2,n]]+1". Maneja automáticamente el caso de informe correcto de cero en 0lugar de -∞.

Wolfram Language (Mathematica) , 28 bytes

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

Pruébalo en línea!

bitNumber - math.ceil (math.log (número) / math.log (2))

por ejemplo, NÚMERO de 64 bits: 9223372036854775807 math.ceil (math.log (9223372036854775807) / math.log (2)) ANS: 63