Problème:

Trouver le nombre de zéros non significatifs dans un entier signé 64 bits

Règles:

• L'entrée ne peut pas être traitée comme une chaîne; cela peut être n'importe quoi où les opérations mathématiques et au niveau des bits conduisent l'algorithme
• La sortie doit être validée par rapport à la représentation entière signée 64 bits du nombre, quelle que soit la langue
• Les règles de golf par défaut s'appliquent
• Le code le plus court en octets gagne

Cas de test:

Ces tests supposent deux entiers signés complémentaires. Si votre langue / solution manque ou utilise une représentation différente des entiers signés, veuillez l'indiquer et fournir des cas de test supplémentaires qui peuvent être pertinents. J'ai inclus quelques cas de test qui traitent de la double précision, mais n'hésitez pas à en suggérer d'autres qui devraient être répertoriés.

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

Langage machine x86_64 sous Linux, 6 octets

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

Nécessite un processeur Haswell ou K10 ou supérieur avec lzcntinstruction.

Essayez-le en ligne!

Hexagonie , 78 70 octets

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

Essayez-le en ligne!

Ce défi n'est-il pas trop banal pour un langage pratique? ;)

_{longueur de côté 6. Je ne peux pas l'adapter dans un hexagone de longueur de côté 5.}

Explication

Python , 31 octets

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

Essayez-le en ligne!

L'expresson est le bit à bit &de deux parties:

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

Le 67-len(bin(-n))donne la bonne réponse pour les entrées non négatives. Il prend la longueur en bits et soustrait 67, ce qui est 3 de plus que 64 pour compenser le -0bpréfixe. La négation est une astuce à régler pour n==0utiliser cette négation qui ne produit pas de -signe devant.

Le & ~n>>64fait que la réponse soit plutôt 0négative n. Quand n<0, ~n>>64est égal à 0 (sur des entiers 64 bits), donc -ing avec cela0 . Quand n>=0, l' ~n>>64évalue -1et l'action &-1n'a aucun effet.

Python 2 , 36 octets

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

Essayez-le en ligne!

Alternative arithmétique.

Java 8, 32 26 octets.

Long::numberOfLeadingZeros

Builtins FTW.

-6 octets grâce à Kevin Cruijssen

Essayez-le en ligne!

C (gcc) , 14 octets

__builtin_clzl

Fonctionne bien sur tio

C (gcc) , 35 29 octets

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

Essayez-le en ligne!

Que Dennis pour 6 octets

Indicateurs du compilateur C (gcc) , 29 octets par David Foerster

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

Essayez-le en ligne!

Perl 6 , 35 28 26 octets

-2 octets grâce à nwellnhof

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

Essayez-le en ligne!

Bloc de code anonyme qui prend un nombre et renvoie un nombre. Cela convertit le nombre en une chaîne binaire et compte les zéros non significatifs. Cela fonctionne pour les nombres négatifs car le premier caractère est un -exemple -00000101, donc il n'y a pas de zéros de tête.

Explication:

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

Prend l'entrée comme un littéral BigInt.

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

Essayez-le en ligne!

$0$

Python 3 , 34 octets

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

Essayez-le en ligne!

J , 18 octets

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

Essayez-le en ligne!

J , 19 octets

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

Essayez-le en ligne!

Explication:

                #:  - 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 octets

-2 octets grâce à Jo King

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

Essayez-le en ligne!

Rubis , 22 octets

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

Essayez-le en ligne!

05AB1E , 10 9 octets

·bg65αsd*

Les E / S sont deux entiers

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

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

^{Merci xnor d' avoir repéré une erreur!}

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

Pourrait allouer beaucoup de mémoire, essayez-le en ligne!

Vous souhaitez peut-être le tester avec une constante plus petite: Essayez 8 bits!

Explication

Au lieu d'utiliser mapM(pure[0,1])[1..64]pour convertir l'entrée en binaire, nous utiliserons mapM(pure[1,0])[1..64]ce qui génère essentiellement les chaînes inversées$\lbrace0,1\rbrace^{64}$dans l'ordre lexicographique. Nous pouvons donc simplement résumer la$1$préfixe s en utilisant sum.fst.span(>0).

Powershell, 51 octets

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

Script de test:

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

Production:

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 octets

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

Entrée en tant que long(entier 64 bits), sortie en tant queint (entier 32 bits).

Port de la réponse C (gcc) de @ l4m2 .

Essayez-le en ligne.

Explication:

 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: peut être de 26 octets en utilisant le module intégré Long::numberOfLeadingZeroscomme affiché dans la réponse Java 8 de @lukeg .

APL + WIN, 34 octets

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

Explication:

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 octets

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

Essayez-le en ligne!

C # (Visual C # Interactive Compiler) , 31 octets

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

Encore plus court, basé sur la réponse C (gcc) de @ l4m2. Je n'ai jamais su que tu pouvais déclarer des fonctions comme ça, merci @Dana!

Essayez-le en ligne!

Gelée ,  10  9 octets

-1 grâce à une astuce d'Erik the Outgolfer (est-non-négatif est maintenant tout simplement AƑ)

ḤBL65_×AƑ

Un lien monadique acceptant un entier (dans la plage) qui donne un entier.

Essayez-le en ligne! Ou consultez la suite de tests .

Le 10 était ḤBL65_ɓ>-×

Voici une autre solution de 10 octets, que j'aime car elle dit que c'est "BOSS" ...

BoṠS»-~%65

Test-suite ici

... BoṠS63r0¤i, BoṠS63ŻṚ¤iou BoṠS64ḶṚ¤ifonctionnerait également.

Un autre 10 octets (de Dennis) est æ»64ḶṚ¤Äċ0(encore æ»63r0¤Äċ0et æ»63ŻṚ¤Äċ0fonctionnera également)

Perl 5 , 37 octets

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

Essayez-le en ligne!

Ou ces 46 octets si la "stringification" n'est pas autorisée: sub z

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

Swift (sur une plate-forme 64 bits), 41 octets

Déclare une fermeture appelée fqui accepte et retourne un Int. Cette solution ne fonctionne que correctement sur les plates-formes 64 bits, où Intest typealiasédité Int64. (Sur une plate-forme 32 bits, Int64peut être utilisé explicitement pour le type de paramètre de fermeture, en ajoutant 2 octets.)

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

Dans Swift, même le type entier fondamental est un objet ordinaire déclaré dans la bibliothèque standard. Cela signifie Intpeut avoir des méthodes et des propriétés telles que leadingZeroBitCount(ce qui est requis sur tous les types conformes au FixedWidthIntegerprotocole de la bibliothèque standard ).

Haskell , 24 octets

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

Essayez-le en ligne!

C'est fondamentalement la même que la solution Java de Kevin Cruijssen, mais je l'ai trouvée indépendamment.

L'argument doit avoir un type Intpour une version 64 bits, ouInt64 pour n'importe quoi.

Explication

Si l'argument est négatif, le résultat est immédiatement 0. Sinon, on décale vers la gauche, en remplissant avec ceux , jusqu'à ce que nous atteignions un nombre négatif. Ce remplissage nous permet d'éviter un cas spécial pour 0.

Juste pour référence, voici le moyen évident / efficace:

34 octets

import Data.Bits
countLeadingZeros

Propre , 103 octets

Utilise le même "intégré" que la réponse de plafond.

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

Essayez-le en ligne!

Nettoyer , 58 octets

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

Essayez-le en ligne!

Stax , 10 octets

în»╧3(∞┼⌠g

Exécuter et déboguer

C'est un portage de la solution 05AB1E de Kevin.

Perl 5 -p , 42 octets

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

Essayez-le en ligne!

Plus longue qu'une solution basée sur les chaînes de bits, mais une solution basée sur les mathématiques décente.

APL (NARS), 15 caractères, 30 octets

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

testez quelques chiffres pour voir comment utiliser:

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

Rouille, 18 octets

i64::leading_zeros

Essayez-le en ligne!

K (ngn / k) , 6 octets

64-#2\

Essayez-le en ligne!

2\ encoder l'argument en binaire

# longueur

64- soustraire de 64

PHP, 50 46 octets

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

Exécuter en tant que pipe avec -Rou essayer en ligne ,

<?=$argn<0?0:0|64-log($argn+1,2);a des problèmes d'arrondi; j'ai donc pris le long chemin.

Wolfram Language (Mathematica), 41 bytes

La formule des nombres positifs est juste 63-Floor@Log2@#& . Des règles de remplacement sont utilisées pour les cas spéciaux d'entrée nulle et négative.

L'entrée n'a pas besoin d'être un entier signé 64 bits. Cela prendra effectivement la parole de l'entrée pour la transformer en un entier. Si vous entrez un nombre en dehors des limites normales pour un entier 64 bits, il indiquera retourner un nombre négatif indiquant combien de bits supplémentaires seraient nécessaires pour stocker cet entier.

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

Essayez-le en ligne!

La solution de @ LegionMammal978 est un peu plus courte avec 28 octets. L'entrée doit être un entier. Selon la documentation: " BitLength[n]est effectivement une version efficace de Floor[Log[2,n]]+1." Il gère automatiquement le cas de zéro correctement rapportant 0plutôt que -∞.

Wolfram Language (Mathematica) , 28 octets

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

Essayez-le en ligne!

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