introduction

Pendant le travail avec le générateur BMP (bitmap) , je suis confronté à un problème de conversion de nombre en petite chaîne hexagonale endienne. Voici la fonction que je crée en JavaScript - mais je me demande comment un petit code peut fonctionner de manière similaire

let liEnd= num => num.toString(16).padStart(8,'0').match(/../g).reverse().join``;
console.log(liEnd(304767)) // 304767 dec = 0x4a67f hex

Défi

Fonction d'écriture qui prendra un nombre entier non signé de 32 bits en entrée et produira une chaîne hexadécimale à 8 chiffres avec peu d'ordre endian. L'algorithme d'exemple qui fait le travail:

• convertir numb en chaîne hexadécimale, par exemple: 304767 -> '4a67f'
• ajoutez des zéros de remplissage pour obtenir une chaîne de 8 caractères: '0004a67f'
• fendre la chaîne en quatre morceaux de 2 caractères: '00','04','a6','7f'
• ordre inverse des pièces '7f','a6','04','00'
• joindre des pièces et retourner comme résultat: '7fa60400'

Exemple d'entrée et de sortie

Le numéro d'entrée (ou la chaîne avec le numéro de déc) est à gauche de ->, la chaîne hexadécimale de sortie est à droite

2141586432 -> 0004a67f
304767     -> 7fa60400

05AB1E , 10 9 octets

žJ+h¦2ôRJ

Essayez-le en ligne!

-1 octet par inspiration de la réponse Jelly.

žJ+   add 2^32 to input
h     convert to hex
¦     drop leading 1
2ô    split in groups of 2
R     reverse groups
J     and join them

Python 3 , 37 octets

lambda n:n.to_bytes(4,"little").hex()

Essayez-le en ligne!

Solution récursive basée sur l'arithmétique ( 50 49 octets, fonctionne également pour Python 2 ) :

f=lambda n,i=4:i*'1'and"%02x"%(n%256)+f(n>>8,i-1)

Essayez-le en ligne!

-1 octet grâce à @JonathanAllan

R , 54 53 octets

format.hexmode(scan()%/%256^(0:3)%%256%*%256^(3:0),8)

Essayez-le en ligne!

Chaque groupe de 2 caractères est en fait la représentation hexadécimale d'un chiffre dans la base 256. scan()%/%256^(0:3)%%256convertit en un nombre de base 256 avec 4 chiffres inversés, les ...%*%256^(3:0)joint comme un seul entier et format.hexmode(...,8)convertit ce nombre en sa représentation hexadécimale avec 8 chiffres.

JavaScript (ES7),  59  57 octets

Manipulation de chaînes.

n=>(n+2**32).toString(16).match(/\B../g).reverse().join``

Essayez-le en ligne!

Comment?

Nous convertissons d'abord $n + 2^{32}$ en hexadécimal pour nous assurer que tous les $0$ tête sont inclus:

(304767 + 2**32).toString(16) // --> '10004a67f'

Essayez-le en ligne!

Nous utilisons l'expression régulière /\B../gpour faire correspondre tous les groupes de 2 chiffres, en ignorant le $1$ tête grâce à \B( frontière non mot ).

'10004a67f'.match(/\B../g) // --> [ '00', '04', 'a6', '7f' ]

Essayez-le en ligne!

Nous reverse()et join()pour obtenir la chaîne finale.

JavaScript (ES6), 61 octets

Fonction récursive.

f=(n,k=4)=>k?[(x=n&255)>>4&&'']+x.toString(16)+f(n>>8,k-1):''

Essayez-le en ligne!

Zsh , 46 octets

i=$1
repeat 4 printf %02x $[j=i%256,i=i/256,j]

Essayez-le en ligne!

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

x=>$"{(x=x>>16|x<<16)>>8&16711935|(x&16711935)<<8:x8}"

4 octets enregistrés grâce à @PeterCordes

Essayez-le en ligne!

Explication

x=>                                                    //Lambda taking in an uint
     (x=x>>16|x<<16)                                   //Swap the first two and the last two bytes of the uint (0x7fa60400 -> 0x04007fa6)
                    >>8&16711935|(x&16711935)<<8       //Swap each pair of bytes in every group of 2 bytes (0x04007fa6 -> 0x0004a67f)
  $"{                                           :x8}"  //Format as hex string, padded with leading zeroes to length 8

Japt -P , 10 octets

sG ùT8 ò w

Essayez-le

sG ùT8 ò w     :Implicit input of integer
s              :Convert to string
 G             :  In base-16
   ù           :Left pad
    T          :  With 0
     8         :  To length 8
       ò       :Split into 2s
         w     :Reverse
               :Implicitly join and output

C (gcc) , 30 octets

f(x){printf("%.8x",htonl(x));}

Essayez-le en ligne!

Python 2 , 43 octets

lambda n:[("%08x"%n)[i^6]for i in range(8)]

Essayez-le en ligne!

-4 octets grâce à benrg

Sort une liste de caractères. Calculé en récupérant, dans l'ordre, les chiffres hexadécimaux de l'entrée aux indices 6, 7, 4, 5, 2, 3, 0, 1.

C (gcc) agnostique endien, pas de bibliothèques standard, 92 91 octets

h(n)est une fonction d'aide à un chiffre entier> hexadécimal.
f(x,p)prend un entier et un char[8]pointeur. Le résultat est 8 octets de chardonnées. ( Pas de terminaison 0 sauf si l'appelant le fait.)

Hypothèses: jeu de caractères ASCII. Le complément de 2, intdonc le décalage vers la droite fait finalement baisser le bit de signe, et la conversion de a uint32_ten intne modifie pas le motif binaire si le bit haut est défini. intest au moins 32 bits. (Plus large pourrait le laisser fonctionner sur les implémentations du complément 1 ou de la magnitude du signe C).

Non-hypothèses: tout ce qui concerne l'ordre des octets de mise en œuvre ou la signature de char.

i;h(n){n&=15;return n>9?n+87:n+48;}f(x,p)char*p;{for(i=5;--i;x>>=8)*p++=h(x>>4),*p++=h(x);}

Essayez-le en ligne! y compris l'appelant de test utilisant printf("%.8s\n", buf)pour imprimer le tampon de sortie sans le terminer par 0.

Non golfé:

int h(n){n&=15;return n>9 ? n+'a'-10 : n+'0';}      // single digit integer -> hex

int i;
void ungolfed_f(x,p)char*p;{
    for(i=5; --i; x>>=8)   // LS byte first across bytes
        *p++=h(x>>4),      // MS nibble first within bytes
        *p++=h(x);
}

Faire à l' n&=15;intérieur h(x)est au seuil de rentabilité; 6 octets contre 3 chacun pour &15isoler le quartet bas sur les deux sites d'appel.

,est un point de séquence (ou équivalent dans la terminologie moderne), il est donc sûr de le faire *p++= stuffdeux fois dans une seule instruction lorsqu'il est séparé par l' ,opérateur.

>>sur un entier signé est défini par l'implémentation comme arithmétique ou logique. GNU C le définit comme complément arithmétique 2. Mais sur n'importe quelle machine complémentaire de 2, cela n'a pas vraiment d'importance car nous ne regardons jamais les 0 décalés ou les copies du bit de signe. Le MSB d'origine finira par descendre dans l'octet de poids faible inchangé. Ce n'est pas le cas sur signe / amplitude, et je ne suis pas sûr du complément de 1.

Donc, cela ne peut être portable que pour les implémentations C du complément 2. (Ou où intest plus large que 32 bits, le bit 31 n'est qu'une partie de l'ampleur.) Unsigned -> la conversion signée permet également de masquer le modèle de bits pour les nombres entiers négatifs, ainsi de &15suite un intextrait uniquement les grignotages de la valeur non signée d'origine sur le complément à 2. Encore une fois, sauf s'il intétait plus large que 32 bits, toutes les entrées sont donc non négatives.

La version golfée a UB de tomber de la fin d'une fonction non nulle. Ne pas renvoyer une valeur, juste pour éviter de la déclarer voidau lieu de la valeur par défaut int. Les compilateurs modernes briseront cela avec l'optimisation activée.

Motivation: J'envisageais une réponse asm x86 ou ARM Thumb, j'ai pensé qu'il pourrait être amusant de le faire manuellement en C, peut-être pour un asm généré par le compilateur comme point de départ. Voir /programming/53823756/how-to-convert-a-number-to-hex pour asm x86 efficace en termes de vitesse, y compris une version AVX512VBMI qui ne contient que 2 instructions (mais a besoin de vecteurs de contrôle pour vpmultishiftqb et vpshufb ne serait donc pas génial pour le golf). Normalement, il faut du travail supplémentaire pour SIMD pour inverser l'octet dans l'ordre d'impression sur le x86 peu endian, donc cette sortie hexadécimale inversée est en fait plus facile que la normale.

Autres idées

J'ai envisagé de prendre l'entier par référence et de faire une boucle sur ses octets avec char*, sur une implémentation C peu endienne (comme x86 ou ARM). Mais je ne pense pas que cela aurait sauvé beaucoup.

Utilisation sprintfde faire 1 octet à la fois, 64 octets après le golf:

int i;
void f(x,p)char*p;{
        for(i=4;sprintf(p,"%.2x",x&255),--i;x>>=8)
                p+=2;
}

Mais si nous utilisons des fonctions de type printf, nous pourrions aussi bien échanger des octets et faire un %xprintf de tout cela comme la réponse de @ JL2210 .

Code machine SIMD x86 (AVX512-VBMI), 36 octets

(Dont 16 octets sont une table de recherche hexadécimale)

Il s'agit d'une fonction qui accepte un entier xmm0et renvoie 8 octets de données de caractères ASCII xmm0, pour que l'appelant puisse les stocker où il le souhaite. (par exemple à la mémoire vidéo après entrelacement avec les octets d'attribut, ou dans une chaîne en construction, ou autre)

À partir de C, appelez-le comme __m128i retval = lehex(_mm_cvtsi32_si128(x))avec la convention d'appel x86-64 System V ou MS Windows vectorcall.

# disassembly with machine-code bytes (the answer) and NASM source code.
0000000000401000 <lehex>:
  401000:       c5 f1 72 d0 04          vpsrld      xmm1, xmm0, 4         ; AVX1
  401005:       c5 f1 60 c8             vpunpcklbw  xmm1, xmm1, xmm0      ; AVX1
  401009:    62 f2 75 08 8d 05 01 00 00 00 vpermb  xmm0, xmm1, [rel .hex_lut]
  401013:       c3                      ret    

0000000000401014 <lehex.hex_lut>:
  401014:     30 31 ...  61 62 ...     .hex_lut:  db "0123456789abcdef"

Total = 0x24 = 36 octets.

Voir Comment convertir un nombre en hexadécimal? sur SO pour savoir comment cela fonctionne. (SSE2 pour le shift / punpck, puis vpermbenregistre le travail dont nous aurions besoin pshufb. AVX1 au lieu de SSE2 / SSSE3 évite également une movapscopie de registre.)

Notez que punpcklbwles opérandes source dans cet ordre nous donneront le quartet le plus significatif de l'octet d'entrée bas dans l'élément d'octet le plus bas, puis le quartet le moins significatif de l'octet source le plus bas. (Dans cette réponse SO, un bswapest utilisé sur l'entrée pour obtenir un résultat dans l'ordre d'impression standard avec uniquement SSE2. Mais ici, nous voulons cet ordre: un quartet élevé dans l'élément inférieur de chaque octet, mais toujours un ordre d'octets peu fin).

Si nous avions plus de constantes de données, nous pourrions économiser de l'espace en mode d'adressage en en faisant une mov edx, imm32puis en utilisant [rdx+16]ou n'importe quel mode d'adressage. Ou vpbroadcastb xmm0, [rdx+1].

Mais je pense qu'un LUT + hexadécimal de 16 octets vpermbest toujours mieux que d'implémenter la n>9 : n+'a'-10 : n+'0'condition: cela nécessite 3 constantes et au moins 3 instructions avec le masquage d'octets AVX512BW (comparer en masque,, vpaddbfusionner-masqué vpaddb), ou plus avec AVX1 ou SSE2. (Voir Comment convertir un nombre en hexadécimal? Sur SO pour une version SSE2 de cela). Et chaque instruction AVX512BW est longue d'au moins 6 octets (EVEX 4 octets + opcode + modrm), plus longue avec un déplacement en mode d'adressage.

En fait, cela prendrait au moins 4 instructions car nous devons effacer les ordures avec andps(ou EVEX vpanddavec un opérande de mémoire de diffusion de 4 octets) avant la comparaison. Et chacun d'eux a besoin d'une constante vectorielle différente. L'AVX512 possède des opérandes de mémoire de diffusion, mais uniquement pour les éléments de 32 bits et plus. Par exemple , le dernier opérande d' EVEXvpaddb est seulement xmm3/m128, pas xmm3/m128/m8bcst. (Les ports de chargement d'Intel ne peuvent faire que des émissions 32 et 64 bits gratuitement dans le cadre d'une charge, donc Intel a conçu l'AVX512BW pour refléter cela et ne pas être en mesure de coder les opérandes de mémoire de diffusion d'octets ou de mots du tout, au lieu de leur donner la possibilité de faire des diffusions dword afin que vous puissiez toujours compresser vos constantes à 4 octets: /.)

La raison pour laquelle j'ai utilisé AVX512VBMIvpermb au lieu de SSSE3 / AVX1 pshufbest double:

• vpermbignore les bits hauts des sélecteurs. (v)pshufbzéros octets en fonction du bit élevé du vecteur de contrôle et aurait eu besoin d'un supplément pandou andpsd'isoler réellement les quartets. Avec une taille XMM / 16 octets, vpermbne regarde que les 4 bits bas des éléments de contrôle aléatoire, c'est-à-dire les bits [3:0]en notation Intel dans la section Operation .
• vpermbpeut prendre les données à mélanger (la table de recherche) comme opérande mémoire. (v)pshufbL'opérande xmm / mem est le vecteur de contrôle aléatoire.

Notez que l'AVX512VBMI n'est disponible que sur CannonLake / Ice Lake, vous avez donc probablement besoin d'un simulateur pour le tester, comme le SDE d'Intel.

Scala , 58 40 36 octets

"%08X"format Integer.reverseBytes(_)

Essayez-le en ligne!

Utilise toujours la fonction intégrée pour inverser les octets d'un Int, mais utilise formatpour formater le Intcomme un hexadécimal. Pas besoin d'appeler toHexString.

Suppression des parens format. Cela signifie maintenant que l'argument peut être pris implicitement en utilisant _.

Forth (gforth) , 52 51 40 octets

: f hex 0 4. do <# # # 0. #> type loop ;

Essayez-le en ligne!

Explication du code

: f           \ start a new word definition
  hex         \ set the current base to base 16
  0           \ convert the input number to a double-cell integer
  4. do       \ start a counted loop from 0 to 3
    <# # #    \ start a formatted numeric string and move last 2 digits to format area
    0.        \ move remaining digits down the stack
    #>        \ delete top two stack value and convert format area to string
    type      \ output string
  loop        \ end loop
;             \ end word definition

Gelée , 13 octets

+Ø%b⁴Ḋs2Ṛ‘ịØh

Essayez-le en ligne!

Un programme complet qui prend un entier comme argument et imprime une chaîne.

APL + WIN, 36 34 octets

2 octets enregistrés en convertissant l'index zéro

Invite pour un entier:

'0123456789abcdef'[,⊖4 2⍴(8⍴16)⊤⎕]

Essayez-le en ligne! Courtoisie Dyalog Classic

Excel, 91 octets

=RIGHT(DEC2HEX(A1,8),2)&MID(DEC2HEX(A1,8),5,2)&MID(DEC2HEX(A1,8),3,2)&LEFT(DEC2HEX(A1,8),2)

K4 , 12 11 octets

Solution:

,/$|4_0x0\:

Exemples:

q)k),/$|4_0x0\:304767
"7fa60400"
q)0W
"0004a67f"

Explication:

À peu près exactement ce que la question demande:

,/$|4_0x0\: / the solution
      0x0\: / split to bytes
    4_      / drop first 4 bytes
   |        / reverse
  $         / convert to string
,/          / flatten

Remarques:

• -1 octet car les nombres K4 sont longs (64 bits) par défaut, ce qui fait chuter 4 octets (32 bits)

PHP , 31 octets

<?=unpack(H8,pack(V,$argn))[1];

Essayez-le en ligne!

Profitant du pack et du décompactage de PHP, j'emballe l'entrée non signée avec le format (32 bit little endian byte order V) ( ) dans une chaîne binaire, puis la décompresse avec le format "hex string, high nibble first" ( H) et j'imprime le résultat.

Cela semble être l'un des rares cas où les fonctionnalités intégrées de PHP sont en fait plus courtes que l'implémentation d'un algorithme simple!

Fusain , 11 octets

⪫⮌⪪﹪%08xＮ²ω

Essayez-le en ligne! Le lien est vers la version détaillée du code. Explication:

        Ｎ   Input as a number
   ﹪%08x    Format using literal string
  ⪪      ²  Split into pairs of characters
 ⮌          Reverse
⪫         ω Join
            Implicitly print

19 octets sans recourir au formatage Python:

⪫…⮌⪪⍘⁺Ｘ²¦³⁶Ｎ¹⁶¦²¦⁴ω

Essayez-le en ligne! Le lien est vers la version détaillée du code. Explication:

           Ｎ        Input as a number
     ⁺              Plus
       ²            Literal 2
      Ｘ             To power
         ³⁶         Literal 36
    ⍘               Convert to base
            ¹⁶      Literal 16
   ⪪           ²    Split into pairs of digits
  ⮌                 Reverse the list
 …               ⁴  Take the first 4 pairs
⪫                 ω Join together
                    Implicitly print

Perl 5 (-p), 22 octets

$_=unpack H8,pack V,$_

Essayez-le en ligne!

J , 10 octets

8{._1{3!:3

Essayez-le en ligne!

Comment

3!:3est une J "conjonction étrangère" pour la représentation hexadécimale, documentée ici . C'est-à-dire que c'est une fonction intégrée pour convertir en hexadécimal. Cependant, ce n'est pas tout à fait ce que nous voulons. Par exemple, en cours d'exécution:

3!:3 (304767)

produit:

e300000000000000
0400000000000000
0100000000000000
0000000000000000
7fa6040000000000

La signification des autres lignes est expliquée sur la page doc que j'ai liée à ci-dessus. En tout cas, il est clair que nous voulons les 8 premiers caractères de la dernière ligne.

_1{ obtenez la dernière ligne.

8{. obtient les 8 premiers caractères de celui-ci.

Rubis , 31 27 octets

A fini par être un port de la réponse PHP de Night2 parce que Ruby a la même fonctionnalité de pack / unpack.

->*i{i.pack(?V).unpack'H8'}

Essayez-le en ligne!

Ma réponse originale de 31 octets qui n'a pas profité du mode de décompression H8 parce que je ne le savais pas:

->*i{'%02x'*4%i.pack(?V).bytes}

Essayez-le en ligne!

Windows Batch, 90 octets

@for /l %%x in (24,-8,0)do @set/aa=%1^>^>%%x^&255&cmd/cexit !a!&<nul set/p=!=exitcode:~-2!

Exécutez la ligne de commande avec / v pour activer l'expansion retardée.

Code machine x86 32 bits, 24 21 octets

changelog: -3 octets: remplacez add / cmp / jbe / add standard par un hack DAS par @peter ferrie

64 bits: toujours 24 octets. Le mode long a supprimé l'opcode DAS.
Mode 16 bits: la taille d'opérande par défaut est 16 bits mais la spécification du problème est intrinsèquement 32 bits. Y compris 8 chiffres hexadécimaux codés en dur.

Inverse-octet avec bswapensuite manuel int-> hex dans l'ordre standard (le quartet le plus significatif en premier, écrit les chiffres hexadécimaux dans un tampon de sortie de caractères dans l'ordre croissant). Cela évite d'avoir à dérouler la boucle pour changer l'ordre entre les quartets dans un octet vs. sur plusieurs octets.

Appelable void lehex(char buf[8] /*edi*/, uint32_t x /*esi*/);comme le x86-64 System V, sauf que cela ne fonctionne pas en mode 64 bits. (Il a besoin du pointeur de sortie en EDI pour stosb. Le numéro d'entrée peut être dans n'importe quel registre autre que ECX ou EAX.)

     1                             lehex:
     2 00000000 0FCE                   bswap  esi
     3 00000002 6A08                   push   8            ; 8 hex digits
     4 00000004 59                     pop    ecx
     5                             .loop:                ;do{
     6 00000005 C1C604                 rol    esi, 4       ; rotate high nibble to the bottom
     7                             
     8 00000008 89F0                   mov    eax, esi
     9 0000000A 240F                   and    al, 0x0f     ; isolate low nibble
    10 0000000C 3C0A                   cmp al, 10          ; set CF according to digit <= 9
    11 0000000E 1C69                   sbb al, 0x69        ; read CF, set CF and conditionally set AF
    12 00000010 2F                     das                 ; magic, which happens to work
    13                             
    14 00000011 AA                     stosb               ; *edi++ = al
    15 00000012 E2F1                   loop  .loop       ; }while(--ecx)
    16                             
    17 00000014 C3                     ret

taille = 0x15 = 21 octets.

Cas de test TIO FASM 32 bits x86 avec un appelant asm qui utilise un writeappel système pour écrire la sortie après l'avoir appelée deux fois pour ajouter 2 chaînes dans un tampon. Teste tous les chiffres hexadécimaux 0..F, y compris 9 et A à la frontière entre le chiffre et la lettre.

Le DAShack - x86 a un drapeau semi-porté, pour effectuer le quartet bas. Utile pour les trucs BCD compressés comme l'instruction DAS, destinés à être utilisés après soustraction de deux entiers BCD à 2 chiffres. Le faible quartet de AL étant en dehors de la plage 0-9, nous en abusons certainement ici.

Remarquez la partie if (old_AL > 99H) or (old_CF = 1)ALORS AL ← AL − 60H;de la section Fonctionnement du manuel; sbb définit toujours CF ici pour que la partie se produise toujours. C'est cela et la plage ASCII pour les lettres majuscules est ce qui motive le choix desub al, 0x69

• cmp 0xD, 0xA ne définit pas CF
• sbb 0xD - 0x69encapsule AL = 0xA4comme entrée dans DAS. (Et définit CF, efface AF)
• pas d'AL - = 6 dans la première partie du DAS (car 4> 9 est faux et AF = 0)
• AL - = 0x60 dans la deuxième partie, en laissant 0x44le code ASCII pour'D'

contre un chiffre:

• cmp 0x3, 0xA définit CF
• sbb 3 - 0x69 - 1= AL = 0x99 et définit CF et AF
• pas d'AL - = 6 dans la première partie de DAS (9> 9 est faux mais AF est défini), laissant 0x93
• AL - = 0x60 dans la deuxième partie, laissant 0x33, le code ASCII pour '3'.

La soustraction 0x6adans les CFF définira AF pour chaque chiffre <= 9 afin que tous les chiffres suivent la même logique. Et laissez-le effacé pour chaque chiffre hexadécimal alphabétique. c'est-à-dire en exploitant correctement le split split 9 / A du DAS.

Normalement (pour les performances), vous utiliseriez une table de recherche pour une boucle scalaire, ou éventuellement un ajout 2x sans branche leaet cmp/cmovconditionnel. Mais les al, imm8instructions sur 2 octets sont une grande victoire pour la taille du code.

Version x86-64 version : juste la partie qui est différente, entre and al, 0xfet stosb.

;; x86-64 int -> hex  in 8 bytes
    10 0000000C 0430                   add    al, '0'
    11 0000000E 3C39                   cmp    al, '9'
    12 00000010 7602                   jbe  .digit
    13 00000012 0427                     add    al, 'a'-10 - '0'     ; al =  al>9 ? al+'a'-10 : al+'0'
    14                             .digit:

Notez que le add al, '0' toujours s'exécute, et l'ajout conditionnel ajoute seulement la différence entre 'a'-10et '0', pour en faire juste un ifau lieu de if/ else.

Testé et fonctionne, en utilisant le même mainappelant que ma réponse C , qui utilise char buf[8]et printf("%.8s\n", buf).