Permutation paire de bits dans un octet

Question

J'ai un nombre binaire 8 bits arbitraire par exemple, 11101101

Je dois échanger tous les deux de bits comme:

Avant permutation: 11-10-11-01 Après avoir échangé : 11-01-11-10

On m'a demandé cela dans une interview!

Answer 1

en pseudo-code:

x = ((x & 0b10101010) >> 1) | ((x & 0b01010101) << 1) 

Il fonctionne en traitant les bits de poids faible et les bits de poids fort de chaque paire de bits séparément, puis en combinant le résultat:

• L'expression x & 0b10101010 extrait le haut bit de chaque paire, puis >> 1 décale à la position de bit faible.
• De même, l'expression (x & 0b01010101) << 1 extrait le bit faible de chaque paire et le décale vers la position de bit haut.
• Les deux parties sont ensuite combinées en utilisant OU bit à bit.

Comme toutes les langues vous permettent d'écrire littéraux binaires directement, vous pouvez les écrire par exemple hexadécimal:

 
Binary  Hexadecimal Decimal 
0b10101010 0xaa   170 
0b01010101 0x55   85 

Answer 2

b = (a & 170 >> 1) | (a & 85 << 1) 

Answer 3

Je premier code ce longhand '- c'est-à-dire en plusieurs étapes évidentes, explicites, et l'utiliser pour valider les tests unitaires que j'avais en place fonctionnaient correctement et ne se déplacent plus solutions de manipulation de bits ésotériques si j'avais un besoin de performance (et que les performances supplémentaires ont été livrés par les améliorations)

Code pour les personnes d'abord, les ordinateurs en second lieu.

Answer 4

1. Faire deux masques de bits, l'un contenant tous les bits pairs et un contenant les bits irréguliers (10101010 et 01010101).
2. Utiliser bit à bit et de filtrer l'entrée en deux nombres, l'un ayant tous les bits pairs à zéro, l'autre ayant tous les bits inégaux mis à zéro.
3. Décalez le nombre qui contient uniquement les bits pairs d'un bit vers la gauche et l'autre d'un bit vers la droite.
4. Utilisez le bit-à-bit ou de les combiner ensemble.

Exemple de 16 bits (code non réel):

short swap_bit_pair(short i) { 
    return ((i & 0101010110101010b) >> 1) | ((i & 0x0101010101010101b) << 1)); 
} 

Answer 5

La solution la plus élégante et flexible est, comme d'autres l'ont dit, pour appliquer un masque « en peigne » à la fois les bits pairs et impairs séparément, puis, après les avoir décalés à gauche et à droite respectivement un endroit pour les combiner en utilisant bit ou.

Une autre solution à laquelle vous souhaiterez peut-être tirer avantage de la taille relativement petite de votre type de données.Vous pouvez créer une table de 256 valeurs statiquement initialisées aux valeurs que vous souhaitez en sortie à votre entrée:

const unsigned char lookup[] = { 0x02, 0x01, 0x03, 0x08, 0x0A, 0x09, 0x0B ... 

Chaque valeur est placée dans le tableau pour représenter la transformation de l'indice. Donc, si vous faites ceci:

unsigned char out = lookup[ 0xAA ]; 

out contiendra 0x55

Ceci est plus lourd et moins souple que la première approche (si vous voulez passer de 8 bits à 16?) Mais ne dispose l'approche qu'il sera sensiblement plus rapide si l'exécution d'un grand nombre de ces opérations.

Answer 6

Supposons que votre numéro soit num.

d'abord trouver le bit de position même:
num & oxAAAAAAAA

Deuxième étape trouver le bit de position étrange:
num & ox55555555

position de changement 3ème étape étrange position à peu de position même et bit de position à l'étrange bit:
Even = (num & oxAAAAAAAA)>>1
Odd = (num & 0x55555555)<<1

Dernière étape ... result = Even | Odd

Imprimer résultat