Quelles astuces de code d'opérateur bit à bit utiles un développeur devrait-il connaître?

Utilisation d'opérations bit à bit sur des chaînes (caractères)

Convertir la lettre en minuscules :

• OR par l'espace => (x | ' ')
• Résultat est toujours en minuscules, même si la lettre est déjà en minuscules
• , par exemple. ('a' | ' ') => 'a' ; ('A' | ' ') => 'a'

Convertir la lettre en majuscules :

• AND par souligner => (x & '_')
• le résultat est toujours en majuscule même si la lettre est déjà en majuscule
• , par exemple. ('a' & '_') => 'A' ; ('A' & '_') => 'A'

Inversez le cas de la lettre:

• XOR par l'espace => (x ^ ' ')
• , par exemple. ('a' ^ ' ') => 'A' ; ('A' ^ ' ') => 'a'

Position de la lettre dans l'alphabet:

• AND par chr(31)/binary('11111')/(hex('1F') => (x & "\x1F")
• le résultat est en 1..26 gamme, lettre cas n'est pas important
• , par exemple. ('a' & "\x1F") => 1 ; ('B' & "\x1F") => 2

Me de la lettre position dans l'alphabet (pour Majuscules lettres Seulement):

• AND par ? => (x & '?') ou XOR par @ => (x ^ '@')
• , par exemple. ('C' & '?') => 3 ; ('Z' ^ '@') => 26

Récupère la position de la lettre en alphabet (pour les lettres minuscules uniquement):

• XOR par backtick/chr(96)/binary('1100000')/hex('60') => (x ^ '`')
• , par exemple. ('d' ^ '`') => 4 ; ('x' ^ '`') => 25

remarque: Utiliser autre chose que les lettres anglaises produira des ordures les résultats

• opérations binaires sur les entiers (int)

Obtenir l'entier maximum

int maxInt = ~(1 << 31);
int maxInt = (1 << 31) - 1;
int maxInt = (1 << -1) - 1;

Obtenez l'entier minimum

int minInt = 1 << 31;
int minInt = 1 << -1;

Obtenir le maximum de longue

long maxLong = ((long)1 << 127) - 1;

Multiplié par 2

n << 1; // n*2

Divisé par 2

n >> 1; // n/2

Multiplié par le m-ième puissance de 2

n << m;

Divisé par le m-ième puissance de 2

n >> m;

Vérifier bizarre nombre

(n & 1) == 1;

L'Échange de deux valeurs

a ^= b;
b ^= a;
a ^= b;

Obtenir la valeur absolue

(n ^ (n >> 31)) - (n >> 31);

Obtenir le maximum de deux valeurs

b & ((a-b) >> 31) | a & (~(a-b) >> 31);

Obtenir le minimum des deux valeurs

a & ((a-b) >> 31) | b & (~(a-b) >> 31);

Vérifier si les deux ont le même signe

(x ^ y) >= 0;

Calculer 2^n

2 << (n-1);

Si est la factorielle de 2

n > 0 ? (n & (n - 1)) == 0 : false;

Modulo 2^n à l'encontre de m

m & (n - 1);

Obtenez le moyenne

(x + y) >> 1;
((x ^ y) >> 1) + (x & y);

Obtenez le m-ième bit de n (de bas en haut)

(n >> (m-1)) & 1;

Définir le m-ième bit de n à 0 (de bas en haut)

n & ~(1 << (m-1));

N + 1

-~n

N - 1

~-n

Obtenir le nombre de contraste

~n + 1;
(n ^ -1) + 1; 

Si (x= = a) x = b; Si (x= = b) x=a;

x = a ^ b ^ x;

Il N'y en a que trois que j'ai jamais utilisés avec n'importe quelle fréquence:

1. Réglez un peu: a |= 1

2. Effacer un peu: a &= ~(1

3. Testez qu'un bit est défini: un & (1

Les Questions de Calcul: les Idées, les Algorithmes, le Code Source, par Jorg Arndt (PDF). Ce livre contient des tonnes de choses, je l'ai trouvé via un lien à http://www.hackersdelight.org/

Moyenne sans débordement

Une routine pour le calcul de la moyenne (x + y)/2 de deux les arguments x et y sont

static inline ulong average(ulong x, ulong y)
// Return floor( (x+y)/2 )
// Use: x+y == ((x&y)<<1) + (x^y)
// that is: sum == carries + sum_without_carries
{
    return (x & y) + ((x ^ y) >> 1);
}

Vous pouvez compresser des données, par exemple une collection d'entiers:

• Voir quelles valeurs entières apparaissent le plus souvent dans la collection
• Utiliser peu court-séquences pour représenter les valeurs qui apparaissent plus fréquemment (et de plus peu-séquences pour représenter les valeurs qui apparaissent moins fréquemment)
• concaténer les séquences de bits: ainsi, par exemple, les 3 premiers bits du flux de bits résultant peuvent représenter un entier, puis les 9 bits suivants un autre entier, etc.

J'ai utilisé des opérateurs binaires pour implémenter efficacement les calculs de distance pour chaînes de bits . Dans mon application, les chaînes de bits ont été utilisées pour représenter des positions dans un espace discrète (un octree , Si vous êtes intéressé, encodé avec Morton ordering). Les calculs de distance étaient nécessaires pour savoir si les points de la grille se trouvaient dans un rayon particulier.

Compter les bits de jeu, Trouver le bit de jeu le plus bas/le plus haut, trouver le nième bit de jeu de haut / bas et d'autres peuvent être utiles, et il vaut la peine de regarder le sitebit-twiddling hacks .

Cela dit, ce genre de chose n'est pas important au jour le jour. Utile d'avoir une bibliothèque, mais même alors les utilisations les plus courantes sont indirectes (par exemple en utilisant un conteneur bitset). En outre, idéalement, ce seraient des fonctions de bibliothèque standard - beaucoup d'entre elles sont mieux gérées en utilisant des instructions de CPU spécialisées sur certains plate.

1) Diviser/Multiplier par une puissance de 2

foo >>= x; (diviser par puissance de 2)

foo <<= x; (multiplier par une puissance de 2)

2) Swap

x ^= y;
y = x ^ y;
x ^= y;

Alors que multiplier / diviser en décalant semble astucieux, la seule chose dont j'avais besoin de temps en temps était de comprimer les booléens en bits. Pour cela, vous avez besoin de bit à bit et / ou, et probablement bit shifting / inversion.

Je voulais une fonction pour arrondir les nombres à la prochaine puissance la plus élevée de deux, alors j'ai visité le site Web bit Twiddling qui a été soulevé plusieurs fois et est venu avec ceci:

i--;
i |= i >> 1;
i |= i >> 2;
i |= i >> 4;
i |= i >> 8;
i |= i >> 16;
i++;

Je l'utilise sur un size_t type. Il ne jouera probablement pas bien sur les types signés. Si vous vous inquiétez de la portabilité vers des plates-formes de tailles différentes, saupoudrez votre code avec des directives #if SIZE_MAX >= (number) aux endroits appropriés.