Swap de bits en C

[Vetea]

Bonjour,

Je viens ici car j'ai besoin de faire un swap de bits en C et je n'arrive pas a trouver s'il y a un moyen de faire ceci sans créer une usine à gaz.
Je m'explique, pour l'exemple j'ai l'octet suivant : 1101 0101 et je voudrais qu'il devienne 1010 1011
Donc le premier bit passe en dernière position et le dernier en premiere, le second devient le l'avant dernier et l'avant dernier le second etc. Ce qui dit plus simplement, revient à écrire mon octet à l'envers en fin de compte.

Avez-vous une solution ou une piste pour moi ?

Merci !
-----

[albanxiii]

Bonjour,

Lu trop vite... désolé.
Oui, c'est pénible, mais on peut le faire avec une boucle, ça limite la pénibilité.
Pour cela il faut récupérer le bit à la position i et le mettre dans une nouvelle variable initialement nulle, à la position 7-i.

[umfred]

comme ça, je verrais une boucle qui vient prendre les bits 1 à 1 et les repositionner en sortie (en assembleur, ça serait plus simple, il y a souvent un décalage avec récupération du bit sortie, on sort par le bit par le lsb du 1er mot, on le rentre par le lsb du mot résultat).
En C, ça pourrait donner ça:

short mot=0b11010101;
short sortie=0;
for(int i = 0; i<8;i++){
    sortie = (sortie<<1) + (mot & (1<<i)) >> i;
}
printf("%x\n",sortie);

Explications:
v1=mot & (1<<i) => on récupère les bits de mots en commençant par le bit 0
v2=(v1 >> i) => on le décale vers la droite pour le mettre en rang b0
s1=sortie<<i => on décale le résultat précédent de 1 vers la gauche
s1+v2 => on ajoute le bit récupéré à la valeur précédente décalé de 1

Edit: j'ai répondu en donnant la solution directement, je n'aurai peut-être pas dû tout de suite

[Vetea]

Bonjour,

Merci à vous deux pour vos réponses, j'avais effectivement fait une boucle mais plus compliqué. Je me demandais surtout si je ne passais pas à coté d'une commande beaucoup plus simple.
J'ai bien compris le fonctionnement de la réponse ça va bien m'aider je vous remercie !

Vétéa

[A voir en vidéo sur Futura]

[ArchoZaure]

Non rien dit, mal compris la demande...

[pm42]

Je me demandais surtout si je ne passais pas à coté d'une commande beaucoup plus simple.

A ma connaissance, il n'existe pas de solution plus simple en effet et celles qui t'ont été données sont les bonnes.
Si tu dois le faire souvent et sur 8 bits, une technique d'optimisation est de créer un tableau qui contient pour chaque nombre de 0 à 255 celui avec ses bits dans l'autre sens. Cela revient à faire le calcul une fois et à mettre le résultat dans un cache.

[Stan_94]

Bonjour,
je me permet de greffer une petite question sur ce sujet...
Si j'ai bien compris la demande, c'est en fait un décalage circulaire sur la longueur total de l'octet.
N'y a-t-il donc pas un opérateur pour ça en C, un peu comme l'instruction SHIFT de l'ABAP qui a une option CIRCULAR ?

[ArchoZaure]

Bonjour,
je me permet de greffer une petite question sur ce sujet...
Si j'ai bien compris la demande, c'est en fait un décalage circulaire sur la longueur total de l'octet.
N'y a-t-il donc pas un opérateur pour ça en C, un peu comme l'instruction SHIFT de l'ABAP qui a une option CIRCULAR ?

Si justement.
Les instructions de rotation de bits SHR et SHL sont faites en C avec les opérateurs >> et <<, comme d'ailleurs utilisés dans les solutions données.
Voir ici : https://emmanuel-delahaye.developpez...urs-bit-bit-c/

ici, on cherche plus particulièrement à inverser l'ensemble des bits, et pour ça il n'y a pas d'instruction spécifique, il faut jouer avec ces rotations (par exemple).

[pm42]

Si j'ai bien compris la demande, c'est en fait un décalage circulaire sur la longueur total de l'octet.

Non, on ne fait pas une rotation, on inverse l'ordre.

N'y a-t-il donc pas un opérateur pour ça en C, un peu comme l'instruction SHIFT de l'ABAP qui a une option CIRCULAR ?

Il n'y a pas d'option Circular en C sur les opérateurs << et >>.

Si on veut le faire, on utilise un bout de code simple qui est éventuellement compilé vers la bonne instruction si l'assembleur de la machine le supporte et sinon est un poil plus lent.

https://stackoverflow.com/questions/...perations-in-c

[Ultimatom]

comme ça, je verrais une boucle qui vient prendre les bits 1 à 1 et les repositionner en sortie (en assembleur, ça serait plus simple, il y a souvent un décalage avec récupération du bit sortie, on sort par le bit par le lsb du 1er mot, on le rentre par le lsb du mot résultat).
En C, ça pourrait donner ça:

short mot=0b11010101;
short sortie=0;
for(int i = 0; i<8;i++){
    sortie = (sortie<<1) + (mot & (1<<i)) >> i;
}
printf("%x\n",sortie);

Explications:
v1=mot & (1<<i) => on récupère les bits de mots en commençant par le bit 0
v2=(v1 >> i) => on le décale vers la droite pour le mettre en rang b0
s1=sortie<<i => on décale le résultat précédent de 1 vers la gauche
s1+v2 => on ajoute le bit récupéré à la valeur précédente décalé de 1

Edit: j'ai répondu en donnant la solution directement, je n'aurai peut-être pas dû tout de suite

Il y a une erreur dans le code. Soit il faut remplacer le "+" par un "|" ou bien mettre des parenthèses :

sortie = (sortie<<1) + ((mot & (1<<i)) >> i)

A mon humble avis, quand on travaille sur des bits ou utilise plus les opérateurs booléens.

Version plus détaillée. On m'a toujours appris de faire en plusieurs lignes plutôt qu'en une seule C'est souvent plus simple à lire et à débuguer.

for(int i = 0; i<8;i++){
        bit = (mot >> i) & 0b00000001;
        sortie = sortie | (bit << (7-i));
    }

[umfred]

+ ou | ça revient au même ici.
Dans la logique d'opération binaire, effectivement, utiliser le OU est plus cohérent, peut-être plus rapide aussi, à voir comment le compilateur transpose ça.

[aeroman00]

Bonjour,
Réponse tardive ...
Il y a aussi l'opérateur EXOR :

// 
// Demonstrate bitwise exclusive OR
#include <iostream>
using namespace std;
int main() {
   unsigned short a = 0x5555;      // pattern 0101 ...
   unsigned short b = 0xFFFF;      // pattern 1111 ...

   cout  << hex << ( a ^ b ) << endl;   // prints "aaaa" pattern 1010 ...
}

[pm42]

En général, on l'appelle XOR et j'ai du mal à voir comment le code donné fait une rotation

[Jack]

En effet, en l'occurrence, ça fait une inversion de tous les bits de a.

[jiherve]

bonsoir
là solution c'est un processeur qui possède l'instruction!
JR

[pm42]

là solution c'est un processeur qui possède l'instruction!

Ce qui ne répond pas à la question justement.

[Jack]

Ce qui ne répond pas à la question justement.

D'où le smiley ...

[Gyrocompas]

Bonjour,
La solution donnée en #3 est la bonne, aucun intérêt à aller plus loin, le demandeur doit avoir répondu à son problème depuis le 3-10-23.
Certains processeur permettent effectivement des inversions de bit.
Ensuite, ne pas négliger comment c'est réalisé dans un programme, selon la solution, le temps machine peut varier.

[aeroman00]

C'est vrai : pourquoi faire simple quand on peut faire compliqué ...

[Bounoume]

+ expéditif:
multiplier par 2(10) .... c.a.d. multiplier par 10 en binaire : ça va décaler tous les bits vers la gauche et ça va rajouter 0 en position zéro...
puis récupérer et ajouter l'overflow au résultat (donc le 1 éventuel viendra en position zéro)


vieux souvenirs.... sans avoir pris le temps de vérifier...
vrai? faux?

[pm42]

+ expéditif:
multiplier par 2(10) .... c.a.d. multiplier par 10 en binaire : ça va décaler tous les bits vers la gauche et ça va rajouter 0 en position zéro...

Pourquoi faire ça quand en C, on a déjà un opérateur de décalage ?

puis récupérer et ajouter l'overflow au résultat (donc le 1 éventuel viendra en position zéro)

Et comment on récupère l'overflow ?

vieux souvenirs.... sans avoir pris le temps de vérifier...

Pourquoi ne pas avoir simplement lu le fil qui donne des solutions qui elles marchent et explique pourquoi la tienne ne marche pas ?

[Bounoume]

quel est l'opérateur de décalage, appliqué à un nombre écrit en binaire? j'ai oublié...
et pour récupérer l'overflow.. un AND entre les bits de l'expression binaire de 100000000 et ceux du 'nombre-décalé' déjà décalé de 1 position

et la fonction de conversion trouvée sur c++.com (je croyais que c'était une fonction standard... ben non
string intToBin( int n ) { return n > 0 ? intToBin( n / 2 ) + (char)( '0' + n % 2 ) : ""; }
moi, les ops sur les bits, ça date de avec ASM du 6809, il y a 30-4O ans.... alors....

[pm42]

Comme je disais faire l'effort de lire le fil au lieu de poser des questions qui y ont déjà été répondues serait une forme de politesse.
Eviter de réinventer l'eau tiède aussi.

[Jack]

On peut aussi ajouter que le C est sensé être portable à la base, donc il ne faut pas compter exploiter un bit du registre d'état (la "carry" d'un 6809 puisque tu cites ce microprocesseur) puisque ce registre est spécifique à chaque processeur.

[Bounoume]

désolé, j'avais zappé les opérateurs SHR et SHL....
https://emmanuel-delahaye.developpez...urs-bit-bit-c/
et je ne comprenais rien aux << et >> et alors à la suite aussi......

[Gyrocompas]

Bonjour,

Eviter de réinventer l'eau tiède aussi

Disons que ceux qui ont eu à un moment besoin de coder en assembleur possèdent un avantage certain quand une manipulation sur les bits est nécessaire,
dont l'inversion du poids des bits d'un octet, d'un mot à concurrence de leur longueur.
Ce qui permet de rappeler que l’algorithmique s'intéresse à l'opération à réaliser sans se préoccuper du support matériel.

[pm42]

Disons que ceux qui ont eu à un moment besoin de coder en assembleur possèdent un avantage certain quand une manipulation sur les bits est nécessaire

C'est une évidence mais comme le fil parle du C, on vient d'avoir l'illustration du contraire : quelqu'un qui a fait de l'assembleur mais ne connait pas le C ne répond pas de façon pertinente.

Ce qui permet de rappeler que l’algorithmique s'intéresse à l'opération à réaliser sans se préoccuper du support matériel.

Ce n'est pas contradictoire avec la phrase au dessus ?
Parce que dans le cas présent, c'est précisément le support ou non d'opérations matérielles qui joue : est ce qu'on a des opérateurs directs de décalage ou non ? Donnent ils accès à l'overflow ou non ? As t'on même des opérateurs de rotation ?

Quand on veut faire de l'algorithmique pure sans se préoccuper du support matériel, on est en général assez loin de l'assembleur et du C qui est juste un niveau d'abstraction au dessus.

[bobflux]

La solution est évidente : c'est comme pour la FFT, il faut faire des papillons.

uint32_t bit_reverse_4bytes(uint32_t x)

{
    x = ((x & 0xF0F0F0F0) >> 4) | ((x & 0x0F0F0F0F) << 4);    x = ((x & 0xCCCCCCCC) >> 2) | ((x & 0x33333333) << 2);    return ((x & 0xAAAAAAAA) >> 1) | ((x & 0x55555555) << 1); 
}

[pm42]

Sauf erreur de ma part, si on donne 1 comme argument, on récupère 128 en retour.
Ce qui n'est pas l'inversion sur 32 bits attendue.

[bobflux]

Oui il a demandé une inversion octet par octet.