Discussion :

[fred61]

Bonjour à tous,

Je continu d'apprendre le c et je bute sur un problème de rotation de bits, en fait j'aimerai comprendre comment faire pour faire une simple rotation de bits sur la gauche (et pas seulement un décalage avec perte genre x = x << 3)
ce que je voudrai obtenir c'est :
avant : 11110000
après : 10000111

J'ai trouvé plusieurs solutions sur les forums mais honnêtement je n'ai rien compris, est ce que quelqu'un pourrait me donner une solution et surtout m'expliquer le fonctionnement pas à pas de la fonction ?

Merci.

[Invité(e)]

Bonjour,

En C, il n'existe pas de rotation sans perte... il faut donc créer une fonction pour faire ça à la main.

On a déjà une fonction qui permet de faire un décalage.

exemple,
octet à traiter = 1001 1100
décalage : 3
l'opérateur << donne : 1110 0000

On remarque qu'on perd les trois premiers bits... pourtant, ils ont aussi été décalés.
Pour les garder en mémoire, on va ruser : au lieu de stocker notre octet à traiter sur 8 bits, on va l'élargir à 16 bits

octet à traiter, stocké sur 16 bits : 0000 0000 1001 1100
l'opérateur << donne : 0000 0100 1110 0000

On remarque que les 3 bits qui étaient perdu sur 8 bits sont conservés sur 16 bits.

Pour reconstruire notre octet décalé, il suffit d'additionner les deux parties de nos 16 bits.

En C, ça donne :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* définition de deux types de données qui font 
    respectivement 8 et 16 sur une architecture wintel.*/
typedef unsigned char mot_8;
typedef unsigned short mot_16;
 
mot_8 rotate(const mot_8 octect, int decal)
{
    mot_8 result;
    /* on commence par stocker l'octet à traiter sur 16 bits */
    mot_16 data = octect;
 
    /* on applique le décalage */
    data <<= decal;
 
    /* on stocke dans le résultat les deux parties des 16 bits
        data % 256 : récupération des 8 bits de poids faible 
        data / 256 : récupération des 8 bits de poids fort
     */
    result = data%256 + data/256;
 
    /* et voilà*/
    return result;
}

/!\ Ce qui je dis n'est pas portable, sur chaque architecture, il faudrait trouver les types qui vont bien.

[fred61]

Effectivement je n'aurai jamais pensé à cette solution tout seul.

Je vais étudier ça tranquillement.

Merci

[Invité(e)]

Effectivement je n'aurai jamais pensé à cette solution tout seul.

J'ai trouvé plusieurs solutions sur les forums

Par curiosité, quel(s) autre(s) solution(s) t'avait on donné ?

[orfix]

Voici ma petite fonction personnelle :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
#include <limits.h> /* CHAR_BIT */
<...>
unsigned char shift(unsigned char byte, unsigned char i) {
	unsigned char tmp;
 
	i %= CHAR_BIT; /* eliminer les decalages multiples de CHAR_BIT */
	tmp = byte >> CHAR_BIT-i; /* recuperer la partie haute dans tmp */
 
	return byte << i%CHAR_BIT | tmp; /* decaler la partie basse + rajout tmp */
}

l'avantage c'est que tu peux spécifier des décalages supérieurs à CHAR_BIT.

[wadabush]

En plus portable (a mon sens), on pourrait imaginer un truc comme ca:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
 
static unsigned char reverse(unsigned char to_reverse)
{
    //Choppe le premier bit du char.
    unsigned char first_byte= to_reverse >> (sizeof(unsigned char) * 8) - 1 ;
    //decale a gauche
    to_reverse = to_reverse<<1;
    //recolle le premier bit a la fin.
    return to_reverse | first_byte;
}

Il me semble que certaines plateformes ne supportent pas le decalage de plusieurs bits a la fois (a verifier), auquel cas je changerai la premiere ligne par:

Code :

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

1
2
 
    unsigned char first_byte= to_reverse / (pow(2,sizeof(char) * 8) / 2) ;

A priori un truc comme ca devrait marcher. A confirmer avec des reviewers



[EDIT]: Grilled...