Discussion :

[Raikyn]

Salut

J'ai très recemment commencé les manipulations de bits en C.

Je recontre quelques problèmes sur un exercice qui me demande de reverser les bits d'un int (effet mirroir).

Quelqu'un pourrait-il m'indiquer comment faire ?

Merci d'avance.

[kwariz]

Salut,
En fait l'algo est simple : soit N la longueur en bit d'un int, n le nombre d'origine et m sont miroir :

Code :

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

1
2
3
4
5
6
7
 
m=0
pour i de 0 à n-1 faire
  si bit(n,i)=1 alors
    positionner bit(m,n-1-i)
  fin si
fin pour

En c tester le ième bit d'un entier n se fait avec (n & (1<<i))==1, pour positionner le ième bit d'un entier m on fait m=(m | (1<<i))

Tu obtiens la longueur d'un int en bit avec 8*sizeof(int).

Il s'agit d'une implémentation naive, des bit tricks permettent certainement de faire mieux ... par exemple sur : http://graphics.stanford.edu/~seande...everseParallel

tu trouveras :

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
 
Reverse an N-bit quantity in parallel in 5 * lg(N) operations:
 
unsigned int v; // 32-bit word to reverse bit order
 
// swap odd and even bits
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
// swap consecutive pairs
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
// swap nibbles ... 
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
// swap bytes
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
// swap 2-byte long pairs
v = ( v >> 16             ) | ( v               << 16);

ou

Code :

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

1
2
3
4
5
6
7
8
 
unsigned int s = sizeof(v) * CHAR_BIT; // bit size; must be power of 2 
unsigned int mask = ~0;         
while ((s >>= 1) > 0) 
{
  mask ^= (mask << s);
  v = ((v >> s) & mask) | ((v << s) & ~mask);
}

[Raikyn]

Merci pour cette réponse très détaillée kwariz.

J'avais bien le bon algo, je sais maintenant comment procéder même si je dois l'avouer les opérateurs de bits sont encore un peu flou pour moi (surtout leurs utilisations).

Encore merci et à bientôt (j'aurais très certainement d'autres questions x) )

[Raikyn]

Je viens d'essayer en rentrant chez moi, et ça ne marche pas.

J'ai créer une fonction mirroir telle que :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
int mirroir(int x){
  int r=0;
  int i=0;
  int n = 8*sizeof(int);
  for(i=0; i>n-1; i++){
    if(x&(1<<i)==1){
      r=(r|(1<<i));
    }
  }
  return r;
  }

Je la teste :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
int main(){
  int x=35;
  affiche_binaire(x);
  int r=mirroir(x);
  printf("\n");
  affiche_binaire(r);
 
 
 
  return 0;
}

Après compilation :

Code :

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

1
2
3
 
00000000000000000000000000100011
00000000000000000000000000000000

L'instruction pour stocker les bits dans un nouveau int ne doit pas être juste, ou alors j'ai mal fais quelque chose.

[kwariz]

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
int mirroir(int x){
  int r=0;
  int i=0;
  int n = 8*sizeof(int);
  for(i=0; i>n-1; i++){
    if(x&(1<<i)==1){
      r=(r|(1<<i));
    }
  }
  return r;
  }

Humm ... il y a plusieurs erreurs dans ton code ...

Code :

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

1
2
3
4
5
6
7
m=0
pour i de 0 à n-1 faire
  si bit(n,i)=1 alors
    positionner bit(m,n-1-i)
  fin si
fin pour

Tu as essayé de dérouler tout ça à la main ? dans un debugger ? C'est vraiment utile pour trouver les erreurs.

Une fonction qui renvoie toujours 0 devrait te mettre la puce à l'oreille.

[Raikyn]

J'ai corrigé mes erreurs mais ça ne marche toujours pas.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
int mirroir(int x){
  int r=0;
  int i=0;
  int n = 8*sizeof(int);
  for(i=0; i<=n-1; i++){
    if(x&(1<<i)==1){
      r=(r|(1<<(n-1-i)));
    }
  }
  return r;
  }

Ca me donne un -1 comme bit tout à gauche (quand i=31, dans l'int mirroir) et que des 0 ensuite. J'ai fais quelques tests à part pour voir si je pouvais placer un bit tout à gauche et là aussi ça me met un -1 tout à gauche.

[kwariz]

Au temps pour moi ... tester si le bit en position i est mis se fait par un (x&(1<<i))!=0 en c.

Tu vois ce que font les opérations bitwise comme & ou | en c ?
Attention si tu manipules des entiers signés.

[Obsidian]

J'ajoute que pour retourner les bits d'un entier, qui est une suite de bits consécutifs, il suffit de les « faire sortir » d'un côté et « rentrer » par ce même côté dans un autre registre. Le code ci-dessous est loin d'être le plus optimisé, mais il a le mérite d'être simple :

Code :

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

1
2
3
4
5
6
7
8
#include <limits.h>
 
unsigned int reverse (unsigned int i)
{
    unsigned int o=0, c=CHAR_BIT*sizeof i;
    while (c--) { o <<=1; o |= (i & 1); i >>=1; }
    return o;
}

[Raikyn]

La modification que j'ai apporté sur le test du bit ne fonctionne pas, ça me revois des -1.
Je connais les opérateurs & et | mais j'avoue ne pas comprendre parfaitemment leurs utilisations avec les opérateurs de décalage.
Quel est le problème au niveau des entiers signés ?

Ta méthode, Obsidian marche mais je ne la comprend pas

o <<=1; décale tout les bits vers la gauche

o |= (i & 1); je ne vois pas ce que ça fait mais j'imagine que ça place un bit 1 dans o (mais à quel endroit dans o ?)

i >>=1; décale i vers la droite d'un cran

Ces opérateurs bitewise me donnent vraiment mal au crâne ><


EDIT : C'est bon j'ai compris comment se faisait la manip du placement de bit dans o. Je vais étudier les combinaisons des op bitewise pour me familiarisé car là ... je n'y aurait jamais pensé ^^

Merci pour vos réponses et à bientôt.