Comment utiliser les opérations par bit pour affecter des bits spécifiques d'un octet en fonction de deux autres octets (mélange de bits en fonction d'un masque) ?

Question

J'ai 3 octets.

• Un octet détermine quels bits du troisième octet doivent être modifiés (1 indique que le bit doit être modifié ; 0 signifie qu'aucun changement ne doit avoir lieu).
• Le deuxième octet détermine si les bits de changement sont affectés à 1 ou 0.
• Le troisième octet est celui où les changements ont lieu.

Y a-t-il un moyen d'y parvenir en utilisant des opérateurs binaires ? Si oui, comment ? Une formule ou un programme simple pour y parvenir serait le bienvenu (de préférence en C).

Exemple :

BitsToAssign:   0b01101011
ValuesToAssign: 0b01000010
ByteToAlter:    0b11110001

ExpectedResult: 0b11010010

Answer 1

BitsToAssign & ValuesToAssign | ~BitsToAssign & ByteToAlter Essayez ceci, s'il vous plaît.

Explication : Sélectionnez ValueToAssign si BitsToAssign est vrai, sinon sélectionnez ByteToAlter

Answer 2

La formule standard pour cela est " Fusionner les bits de deux valeurs en fonction d'un masque " - J'ai ajouté vos noms de variables pour les entrées aux commentaires existants de la collection de bithacks de Sean Anderson.

unsigned int a;    // (ByteToAlter)    value to merge in non-masked bits
unsigned int b;    // (ValuesToAssign) value to merge in masked bits
unsigned int mask; // (BitsToAssign)   1 where bits from b should be selected; 0 where from a.

unsigned int r;    // result of (a & ~mask) | (b & mask) goes here

r = a ^ ((a ^ b) & mask); 

Comme l'indiquent les commentaires de bithack, la méthode la plus simple consiste à (a & ~mask) | (b & mask) - effacez les bits que vous ne gardez pas dans chaque entrée, puis faites un OU entre eux.

Cómo a ^ ((a ^ b) & mask) travaux :

bitdiff = a^b est la différence binaire entre ces entrées.
Il dispose d'un 1 où ils diffèrent, et une 0 où ils sont les mêmes. (Par définition du XOR).

a ^ bitdiff retournerait chaque bit dans a qui est différent de b . En effet, b == a ^ bitdiff .
Une façon de montrer que c'est vrai est que XOR est associatif, donc a ^ (a^b) = (a ^ a) ^ b .
Et x^x = 0, tout comme x-x = 0 .
0 ^ x = x donc (a^a) ^ b = 0 ^ b = b .

Mais si nous masquons le bitdiff pour ne mettre en place que les bits de a à des bits de b à certaines positions, nous avons atteint notre objectif : mélanger les bits en fonction d'un masque. blend = a ^ (bitdiff & mask);

---

Cas particuliers de la (a & ~mask) | (b & mask) version simple

Si vos entrées sont disposées de telle sorte ValuesToAssign n'a que des 1 aux positions sélectionnées par le masque, vous pouvez optimiser l'élimination des b & mask partie, laissant juste (a & ~mask) | b . ( Réponse d'Eraklon ). Effacez les bits non sélectionnés, puis introduisez les nouvelles valeurs par OU pour activer tous les bits qui doivent l'être.

Un autre cas particulier est celui où ValuesToAssign == BitsToAssign En d'autres termes, la modification n'active que des bits, sans jamais les effacer. C'est ce que fait OR, donc bien sûr ce cas s'optimise en a | b sans qu'il soit nécessaire d'effacer les bits dans a avant de procéder à l'OR.

---

Efficacité :

r = a ^ ((a ^ b) & mask); ne comporte que 3 opérations booléennes,
contre 4 pour (a & ~mask) | (b & mask) si les trois entrées sont des variables d'exécution. (Un NOT bitwise, deux AND, plus un OR).

Si mask est une constante, alors la propagation constante en ~mask en fait une constante, et la plupart des machines peuvent faire du ET-immédiat avec au moins un masque ET de 8 bits. Vous n'auriez donc besoin que de 3 instructions : deux AND (avec des constantes inverses) et un OR.

Certaines machines (comme les x86 avec BMI1) ont même une fonction andn instruction qui fait x & ~y permettant à l (a & ~mask) | (b & mask) à faire avec 3 instructions.

Pour la latence, (a & ~mask) | (b & mask) a plus parallélisme au niveau des instructions . Si mask y ~mask sont prêts à l'avance a y b il n'y a que deux opérations ET parallèles, et une OU, de a y b Les entrées étant prêtes, la sortie l'est aussi. Sur une machine superscalaire normale (qui peut effectuer deux opérations ET indépendantes dans le même cycle), la latence entre les entrées et les sorties n'est que de 2 cycles. (Encore une fois, en supposant que mask est prête tôt, ou qu'une instruction comme andn existe pour faire a & ~mask en une seule opération).

Si le chemin critique passe par mask (c'est-à-dire qu'il n'est pas prêt tôt), et vous n'avez pas d'instruction comme andn à faire ~ y & comme une seule opération, la latence de mask a result est de 3 opérations, ~ , & et | . (En supposant que le b & mask peuvent fonctionner en parallèle sans ralentir l'un de ces trois éléments).

Latences pour (a & ~mask) | (b & mask) sur une machine moderne d'exécution d'OoO.
( Ce n'est pas la même chose que le coût du débit )

• a -> résultat : 2 cycles
• b -> résultat : 2 cycles
• masque -> résultat : 3 cycles (ou 2 sur certaines machines)

Mais la méthode de différence de bits n'a pas d'ILP. c'est une chaîne de 3 opérations. a^b exige que ces deux entrées soient prêtes pour la première étape, alors mask doit être prêt pour le & mask étape. L'étape finale a ^ ... L'étape suivante consiste à utiliser des données qui étaient déjà nécessaires auparavant. Il n'y a donc que 3 opérations, mais elles sont en série.

Latences pour a ^ ((a ^ b) & mask) sur une machine moderne d'exécution d'OoO.

• a -> résultat : 3 cycles
• b -> résultat : 3 cycles
• masque -> résultat : 2 cycles

Questions et réponses connexes :

• Fusionner les séquences de bits a et b selon un masque - Cela s'appelle un mélange dans la programmation SIMD. Je ne sais pas si quelqu'un d'autre utilise le terme "bit-blend" que j'aime utiliser pour cette opération, mais je pense que cela la décrit clairement. L'extension AVX-512 de x86 a une opération booléenne à 3 entrées vpternlog avec une table de vérité à partir d'un immédiat de 8 bits, et peut donc le faire en une seule instruction.

• permutation des bits à un point donné entre deux octets - La même idée de bithack, mais en appliquant la différence de bit masquée à les deux pour échanger des bits aux positions du masque.

• https://catonmat.net/low-level-bit-hacks - commence doucement avec une introduction aux opérateurs (comme le ^ étant XOR par bit). Inclut les bithacks qui utilisent + et - (et les effets de la propagation de la retenue en cas d'atteinte d'un 1 ou d'un 0, tels que x & (x-1) pour effacer le bit activé le plus à droite).

• https://agner.org/optimize/ pour en savoir plus sur le réglage des processeurs modernes.

Answer 3

void printbin(unsigned char val)
{
    unsigned char mask = 1 << (sizeof(mask) * 8 - 1);
    while(mask)
    {
        printf("%c", val & mask ? '1' : '0');
        mask >>= 1;
    }
}

unsigned merge(unsigned ByteToAlter, unsigned ValuesToAssign, unsigned BitsToAssign)
{
    unsigned clearMask = ~BitsToAssign;

    return (ByteToAlter & clearMask) | (ValuesToAssign & BitsToAssign);
}

int main(void)
{
    printbin(merge(0b11110001, 0b01000010, 0b01101011));

}

Answer 4

( Third & ~First ) | Second