C – Échangez un peu entre deux nombres

Je viens d’essayer avec ce code:

void swapBit(unsigned char* numbA, unsigned char* numbB, short bitPosition)//bitPosition 0-x { unsigned char oneShift = 1 << bitPosition; unsigned char bitA = *numbA & oneShift; unsigned char bitB = *numbB & oneShift; if (bitA) *numbB |= bitA; else *numbB &= (~bitA ^ oneShift); if (bitB) *numbA |= bitB; else *numbA &= (~bitB ^ oneShift); } 

pour échanger la position du bit x de a et b mais à cause de if (), je pense qu’il ya quelque chose de mieux.

Aussi quand je vois ceci:

 *numbB &= (~bitA ^ oneShift); 

Je pense vraiment qu’il existe un moyen plus facile de le faire. Si vous avez quelque chose pour moi, je le prendrais 🙂

Merci d’avance

Vous devez d’abord définir la position correspondante dans un nombre sur 0 , puis sur OU avec le bit réel, en supprimant toutes les conditions:

 *numbB &= ~oneShift; // Set the bit to `0` *numbB |= bitA; // Set to the actual bit value 

La même chose pour l’autre numéro.

Former le masque

 unsigned char mask = 1u << bitPosition; 

Et gagnez ensuite la colère de votre groupe de pairs avec l' algorithme d'échange XOR .

 *numbA ^= *numbB & mask; *numbB ^= *numbA & mask; *numbA ^= *numbB & mask; 

Notez que cela échoue lorsque numbA == numbB .

Un bit n’est pas plus facile qu’un masque de bits arbitraire, alors parlons-en. Vous pouvez toujours appeler cette fonction avec 1U << bitpos .

Si une position de bit est identique dans les deux valeurs, aucune modification n'est nécessaire dans les deux cas. Si c'est le contraire, ils ont tous deux besoin d'inverser.

XOR avec 1 flips un peu; XOR avec 0 est un non-op.

Donc, ce que nous voulons, c'est une valeur qui a un 1 partout où il y a une différence de bits entre les entrées et un 0 partout ailleurs. C'est exactement ce que fait a XOR b . Masquez simplement ceci pour n’échanger que quelques-uns des bits, et nous avons un échange de bits dans 3 XOR + 1 AND.

 // call with unsigned char mask = 1U << bitPosition; if you want inline void swapBit_char(unsigned char *A, unsigned char *B, unsigned char mask) { unsigned char tmpA = *A, tmpB = *B; // read into locals in case A==B unsigned char bitdiff = tmpA ^ tmpB; bitdiff &= mask; // only swap bits matching the mask *A = tmpA ^ bitdiff; *B = tmpB ^ bitdiff; } 

( Explorateur du compilateur Godbolt avec gcc pour x86-64 et ARM , inclut une version avec unsigned au lieu de unsigned char .)

Vous pouvez envisager if(bitdiff) { ... } , mais à moins que vous if(bitdiff) { ... } salir une ligne de cache en mémoire en évitant les affectations, il ne vaut probablement pas la peine d'adopter un comportement conditionnel. Avec des valeurs dans les registres (après l’inclusion), une twig permettant de sauvegarder deux instructions xor ne vaut presque jamais la peine.

Ce n'est pas un échange xor . Il utilise un stockage temporaire. Comme le montre la réponse de @ chux, un échange xor masqué nécessite 3 opérations AND ainsi que 3 XOR. (Et supprime le seul avantage de XOR-swap en exigeant un registre temporaire ou un autre stockage pour le & résultats.)

Cette version ne nécessite que 1 ET. De plus, les deux derniers XOR étant indépendants l'un de l'autre, la latence totale des entrées vers les deux sorties n'est que de 3 opérations. (Généralement 3 cycles).


Pour un exemple x86 asm, voir la capitalisation code-golf Exchange de deux chaînes dans 14 octets de code machine x86-64 (avec la source asm commentée)