Tous les défis
Moyen 0 résolus 0 % de réussite

Inverser les bits

Inverser l'ordre des width bits de poids faible d'un nombre.

Ce que vous allez apprendre

  • Lire le bit de poids faible avec un ET 1
  • Construire un nombre bit par bit avec des décalages
  • Respecter une largeur fixe en bits

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

Exemple 1
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.

Exemple 2
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.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.