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.