Problème
Écrivez n en binaire sur exactement width bits, en ajoutant des zéros en tête si besoin, puis lisez ces bits à l'envers. Pour n = 6 et width = 4, 6 s'écrit 0110 ; à l'envers, on retrouve 0110, donc le résultat est 6. Avec width = 8, on a 00000110, qui devient 01100000 à l'envers, soit 96. L'inversion de bits sert notamment dans la transformée de Fourier rapide et dans certaines astuces de hachage.
Implémentez reverse_the_bits(n, width).
Entrée
n : un entier positif ou nul qui tient sur width bits.
width : le nombre de bits à inverser.
Sortie
Renvoyez la valeur du motif de width bits inversé.
Contraintes
1 ≤ width ≤ 63
0 ≤ n < 2^width
Exemples
Entrée :
n = 6
width = 8
Sortie attendue :
expected = 96
Entrée :
long long n = 6;
long long width = 8;
Sortie attendue :
long long expected = 96;
Entrée :
long n = 6;
long width = 8;
Sortie attendue :
long expected = 96;
Explication
Sur 8 bits, 6 s'écrit 00000110 ; à l'envers, cela donne 01100000, soit 96.
Entrée :
n = 1
width = 3
Sortie attendue :
expected = 4
Entrée :
long long n = 1;
long long width = 3;
Sortie attendue :
long long expected = 4;
Entrée :
long n = 1;
long width = 3;
Sortie attendue :
long expected = 4;
Explication
1 s'écrit 001 ; à l'envers, cela donne 100, soit 4.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Répétez width fois : prenez le bit de poids faible de n, puis décalez n vers la droite.
Indice 2
Décalez le résultat d'un cran vers la gauche avant d'y ajouter le bit que vous venez de prendre.
Indice 3
Les zéros en tête de n deviennent les zéros de fin du résultat, ce que le nombre fixe de tours de boucle prend en charge.
Complexité attendue
temps O(width), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.