Discussion :

[christophe_halgand]

Bonsoir à tous,

Je voudrais inverser un nombre binaire de manière optimale (obtenir son palindrome). J'ai déjà vu la discussion "inverser nombre binaire" avec deux bouts de code mais je ne sais pas s'ils sont optimaux.

Voici un exemple de nombre binaire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

value = 0b10000011

Merci de votre aide

Christophe

[Sve@r]

Salut
Si ton nombre ne dépasse pas l'octet de ton exemple, le plus rapide est de passer par un tableau...

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
char tab[256]={
    0b00000000,
    0b10000000,
    0b01000000,
    0b11000000,
    0b00100000,
    ...
}
printf("Inverse de 0b10000011 est %x\n", tab[0b100000011]);

[christophe_halgand]

Merci pour votre réponse, effectivement, je ne dépasse pas l'octet.

Cependant, je ne comprends pas complètement l'idée du tableau. A ce que je vois, il contient tout les cas possibles de palindrome correspondant à la valeur de mon binaire à la position de la valeur de mon binaire ?

Merci encore,

Christophe

[Bktero]

C'est exactement ça. C'est le principe d'une lookup table (que Wikipedia traduit par table de correspondance, donc c'est bien ce que Svr@r te propose ^^). Ton nombre binaire donne un indice du tableau, et à cet indice tu stockes le résultat.

Idem si tu voulais trouver la correspondance entre un chiffre (0, 1, 2....) et la chaine de caractère correspondante ("un", "deux", "trois"), tu ferais :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
    const char * lookup[] = {"Zero", "Un", "Deux", "Trois"};
    printf("%d = %s\n\n", 2, lookup[2]);

Et ben là, c'est pareil ^^

C'est optimal dans ton cas car il n'y a quasiment rien à faire (une addition, une lecture).

Au passage, je crois que l'écriture 0b00000000 n'est pas standard (c'est une extension de GCC, p-e faite par d'autres compilateurs).

[Neckara]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
char octet = 14;
char palindromeDeOctet = tab[octet];

A chaque valeur de "octet" possible, on associe son palindrome.
On a donc tous les couples "octet"-palindrome possibles.
"octet" est donc la clé et palindrome la valeur, ce qui permet d'accéder directement au palindrome en connaissant "octet".

On peut aussi accéder à "octet" directement en connaissant son palindrome vu que "octet" est le palindrome de son palindrome.



Pour un octet, la solution du tableau est la plus efficace.
Si ensuite tu as plusieurs octets "entiers" il vaudra mieux alors utiliser ce même tableau pour calculer les palindrome de chaque octet puis faire un parcours à partir de la fin ET du début de ton tableau de palindrome ainsi obtenu en intervertissant tabResultat[i] et taResultat[Taille - i] et tu arrêteras le parcours lorsque i >= Taille - i.


Si tu as un nombre de bit non divisible par 8, je pense que le plus simple est de jouer avec les décalages et les masques pour obtenir "à droite" et "à gauche" un maximum d'octets complet pour utiliser la méthode précédente.

Exemple, si tu as 20 bits, ceci te fait 2,5 octet. Il te manque 4 bits pour avoir un octet complet.
Tu va donc décaler tous les bits de la moitié "droite" de 4 bits.
Pour obtenir quelque chose comme ceci :
8 | <= partie gauche | 4 | <= milieu | 8 | <= partie droite

On ignore donc la partie du milieu et on calcule le palindrome de la partie gauche + partie droite.
Ensuite on calcule le palindrome de la partie du milieu bit après bit ou on utilise un tableau de palindrome Palindrome = tab[nbBit][Valeur].
Et enfin, on fusionne le tout.

Si au milieu, on se retrouve avec un nombre de bit > 8 pair, on va effectuer le palindrome des 8 bits au milieu et on calculera les palindromes des bits restants.

Si le nombre de bit est impair et > 8, on va enlever le bit au milieu pour utiliser la solution précédente puis on le réinjectera par la suite.

[gangsoleil]

Bonjour,

Je voudrais inverser un nombre binaire de manière optimale (obtenir son palindrome). J'ai déjà vu la discussion "inverser nombre binaire" avec deux bouts de code mais je ne sais pas s'ils sont optimaux.

Tu ne trouveras pas meilleur que l'acces au tableau - mais celui-ci impose de connaitre la taille maximale des donnees.

Sinon, le code le plus simple doit etre le xor avec le meme nombre de bits que ton nombre, mais a 1 :
001100 ^ 111111 = 110011

Moins optimal car necessite des calculs.

[Neckara]

Bonjour,



Tu ne trouveras pas meilleur que l'acces au tableau - mais celui-ci impose de connaitre la taille maximale des donnees.

Sinon, le code le plus simple doit etre le xor avec le meme nombre de bits que ton nombre, mais a 1 :
001100 ^ 111111 = 110011

Moins optimal car necessite des calculs.

Il souhaite obtenir un palindrome :
110001 -> 100011

Or tu lui proposes :
110001 -> 001110

[Trademark]

@gangsoleil: on veut le palindrome, pas l'inverse

Trouver le palindrome d'un nombre binaire à exactement la même complexité que trouver le palindrome d'un string, c'est-à-dire O(n/2) = O(n) sur le nombre caractère (ou bit).

L'algo basique c'est partir des deux bout et d'inverser à chaque fois les deux bit jusqu'à ce qu'on arrive au milieu. Tu peux le faire avec les opérateurs ">>", "<<", et "|".

[diogene]

Voir aussi la discussion Inversion de bits d'un octet

Notamment ce message, qui présente une méthode qui peut s'étendre avantageusement et facilement à des données plus grosses qu'un octet.

[gangsoleil]

Effectivement, je me suis laisse abuser par la phrase suivante et ai un peu zappe ce qui etait entre paretheses. Mea culpa.

Je voudrais inverser un nombre binaire de manière optimale (obtenir son palindrome).