Je résolvais un problème sur les codeforces. Normalement, je vérifie d'abord si le caractère est une lettre anglaise supérieure ou inférieure, puis je soustrais ou ajoute32
pour le convertir en lettre correspondante. Mais j'ai trouvé quelqu'un ^= 32
pour faire la même chose. C'est ici:
char foo = 'a';
foo ^= 32;
char bar = 'A';
bar ^= 32;
cout << foo << ' ' << bar << '\n'; // foo is A, and bar is a
J'ai cherché une explication à cela et je ne l'ai pas trouvée. Alors pourquoi ça marche?
c++
bit-manipulation
ascii
Devon
la source
la source
@
en `en utilisant^ 32
.toupper
ettolower
changer de casse.A
àZ
. C'est très bien tant que vous ne vous souciez que de l'anglais (et n'utilisez pas d'orthographe «naïve», de mots comme «café», ou de noms avec des signes diacritiques…), mais le monde n'est pas que l'anglais.Réponses:
Jetons un œil à la table de code ASCII en binaire.
Et 32 est
0100000
la seule différence entre les lettres minuscules et majuscules. Donc, basculer ce bit bascule la casse d'une lettre.la source
{
est plus court que[
, donc c'est une casse "minuscule". Non? Ok, je vais me montrer: Dfoobar[]
etfoobar{}
sont des surnoms identiques, car les surnoms sont insensibles à la casse , et IRC a ses origines en Scandinavie :)Cela utilise le fait que les valeurs ASCII ont été choisies par des personnes vraiment intelligentes.
Cela retourne le 6e bit 1 le plus bas de
foo
(le drapeau majuscule de la sorte ASCII), transformant une majuscule ASCII en minuscule et vice-versa .Exemple
Et par la propriété de XOR,
'a' ^ 32 == 'A'
.Remarquer
C ++ n'est pas obligé d'utiliser ASCII pour représenter les caractères. Une autre variante est EBCDIC . Cette astuce ne fonctionne que sur les plates-formes ASCII. Une solution plus portable serait d'utiliser
std::tolower
etstd::toupper
, avec le bonus offert, de tenir compte des paramètres régionaux (cela ne résout pas automatiquement tous vos problèmes, voir les commentaires):1) Comme 32 est
1 << 5
(2 à la puissance 5), il retourne le 6e bit (à partir de 1).la source
tolower
en allemand n'a pas seulement besoin d'un dictionnaire, il doit être capable d'en analyser le sens.Permettez-moi de dire que c'est - même si cela semble intelligent - un hack vraiment, vraiment stupide. Si quelqu'un vous recommande cela en 2019, frappez-le. Frappez-le aussi fort que vous le pouvez.
Vous pouvez, bien sûr, le faire dans votre propre logiciel que vous et personne d'autre n'utilisez si vous savez que vous n'utiliserez de toute façon jamais aucune autre langue que l'anglais. Sinon, pas de chance.
Le piratage était discutable "OK" il y a 30 à 35 ans quand les ordinateurs ne faisaient pas grand-chose mais l'anglais en ASCII, et peut - être une ou deux langues européennes majeures. Mais ... ce n'est plus le cas.
Le hack fonctionne car les majuscules et les minuscules US-Latin sont exactement
0x20
séparées les unes des autres et apparaissent dans le même ordre, ce qui n'est qu'une petite différence. Ce qui, en fait, ce petit hack, bascule.Maintenant, les gens qui créaient des pages de code pour l'Europe occidentale, et plus tard le consortium Unicode, étaient assez intelligents pour conserver ce schéma, par exemple pour les trémas allemands et les voyelles à accent français. Pas le cas pour ß qui (jusqu'à ce que quelqu'un ait convaincu le consortium Unicode en 2017, et qu'un grand magazine imprimé Fake News ait écrit à ce sujet, convaincant en fait le Duden - pas de commentaire à ce sujet) n'existait même pas en tant que versal (se transforme en SS) . Maintenant , il ne existons en tant que Versal, mais les deux sont des
0x1DBF
positions en dehors, non0x20
.Cependant, les réalisateurs n'ont pas été suffisamment attentifs pour que cela continue. Par exemple, si vous appliquez votre hack dans certaines langues d'Europe de l'Est ou autres (je ne sais pas pour le cyrillique), vous aurez une mauvaise surprise. Tous ces caractères "hachette" en sont des exemples, les minuscules et les majuscules ne font qu'un. Le hack ne fonctionne donc pas correctement là-bas.
Il y a beaucoup plus à considérer, par exemple, certains caractères ne se transforment pas simplement de minuscules à majuscules (ils sont remplacés par des séquences différentes), ou ils peuvent changer de forme (nécessitant des points de code différents).
Ne pensez même pas à ce que ce hack fera à des trucs comme le thaï ou le chinois (cela vous donnera juste un non-sens complet).
Il y a 30 ans, il était peut-être très utile d'économiser quelques centaines de cycles de processeur, mais de nos jours, il n'y a vraiment aucune excuse pour convertir correctement une chaîne. Il existe des fonctions de bibliothèque pour effectuer cette tâche non triviale.
Le temps nécessaire pour convertir correctement plusieurs dizaines de kilo-octets de texte est aujourd'hui négligeable.
la source
Cela fonctionne car, en l'occurrence, la différence entre «a» et A »en ASCII et les codages dérivés est de 32, et 32 est également la valeur du sixième bit. Le retournement du 6ème bit avec un OU exclusif convertit donc entre supérieur et inférieur.
la source
Votre implémentation du jeu de caractères sera très probablement ASCII. Si nous regardons le tableau:
Nous voyons qu'il y a une différence d'exactement
32
entre la valeur d'un nombre minuscule et majuscule. Par conséquent, si nous le faisons^= 32
(ce qui équivaut à basculer le 6ème bit le moins significatif), cela change entre un caractère minuscule et majuscule.Notez que cela fonctionne avec tous les symboles, pas seulement les lettres. Il fait basculer un caractère avec le caractère respectif où le 6ème bit est différent, ce qui entraîne une paire de caractères qui est basculée entre les deux. Pour les lettres, les caractères majuscules / minuscules respectifs forment une telle paire. A
NUL
se transforme enSpace
et dans l'autre sens, et les@
bascule avec le backtick. Fondamentalement, tout caractère de la première colonne de ce graphique bascule avec le caractère d'une colonne, et la même chose s'applique aux troisième et quatrième colonnes.Je n'utiliserais pas ce hack, car il n'y a aucune garantie qu'il fonctionnera sur n'importe quel système. Utilisez simplement toupper et tolower à la place, et des requêtes telles que isupper .
la source
32 ^ 32
c'est 0, pas 64[a-z]
et[A-Z]
sont des «lettres». Les autres sont des coïncidences qui suivent la même règle. Si quelqu'un vous demandait de "majuscules]", quel serait-il? ce serait toujours "]" - "}" n'est pas la "majuscule" de "]".%32
limite "d'alignement" dans le système de codage ASCII. C'est pourquoi le bit0x20
est la seule différence entre les versions majuscules / minuscules d'une même lettre. Si ce n'était pas le cas, vous auriez besoin d'ajouter ou de soustraire0x20
, pas seulement de basculer, et pour certaines lettres, il y aurait un report pour inverser d'autres bits supérieurs. (Et la même opération ne pouvait pas basculer, et la vérification des caractères alphabétiques en premier lieu serait plus difficile car vous ne pouviez pas|= 0x20
forcer la case.)Beaucoup de bonnes réponses ici décrivent comment cela fonctionne, mais pourquoi cela fonctionne de cette façon est d'améliorer les performances. Les opérations au niveau du bit sont plus rapides que la plupart des autres opérations au sein d'un processeur. Vous pouvez rapidement faire une comparaison insensible à la casse en ne regardant simplement pas le bit qui détermine la casse ou en changeant la casse en majuscule / minuscule simplement en retournant le bit (les gars qui ont conçu la table ASCII étaient assez intelligents).
De toute évidence, ce n'est pas aussi important aujourd'hui qu'il l'était en 1960 (lorsque le travail a commencé sur ASCII) en raison de processeurs plus rapides et d'Unicode, mais il existe encore des processeurs à faible coût qui pourraient faire une différence significative tant que vous ne pouvez garantir que des caractères ASCII.
https://en.wikipedia.org/wiki/Bitwise_operation
REMARQUE: je recommanderais d'utiliser des bibliothèques standard pour travailler avec des chaînes pour un certain nombre de raisons (lisibilité, exactitude, portabilité, etc.). N'utilisez le retournement de bits que si vous avez mesuré les performances et qu'il s'agit de votre goulot d'étranglement.
la source
C'est ainsi que fonctionne l'ASCII, c'est tout.
Mais en exploitant cela, vous abandonnez la portabilité car C ++ n'insiste pas sur ASCII comme encodage.
C'est pourquoi les fonctions
std::toupper
etstd::tolower
sont implémentées dans la bibliothèque standard C ++ - vous devriez les utiliser à la place.la source
Voir le deuxième tableau à http://www.catb.org/esr/faqs/things-every-hacker-once-knew/#_ascii , et les notes suivantes, reproduites ci-dessous:
ASCII a été conçu de telle sorte que les touches du clavier shiftet ctrlpuissent être implémentées sans beaucoup de ctrllogique (ou peut-être aucune pour ) - shiftil ne fallait probablement que quelques portes. Il était probablement au moins aussi logique de stocker le protocole filaire que tout autre encodage de caractères (aucune conversion logicielle requise).
L'article lié explique également de nombreuses conventions de piratage étranges telles que
And control H does a single character and is an old^H^H^H^H^H classic joke.
( trouvé ici ).la source
foo ^= (foo & 0x60) == 0x20 ? 0x10 : 0x20
, bien que ce ne soit que de l'ASCII et donc imprudent pour les raisons indiquées dans d'autres réponses. Il peut probablement également être amélioré avec une programmation sans branche.foo ^= 0x20 >> !(foo & 0x40)
serait plus simple. C'est aussi un bon exemple de la raison pour laquelle un code laconique est souvent considéré comme illisible ^ _ ^.Xoring avec 32 (00100000 en binaire) définit ou réinitialise le sixième bit (à partir de la droite). Cela équivaut strictement à ajouter ou à soustraire 32.
la source
Les plages alphabétiques minuscules et majuscules ne traversent pas une
%32
limite "d'alignement" dans le système de codage ASCII.C'est pourquoi le bit
0x20
est la seule différence entre les versions majuscules / minuscules d'une même lettre.Si ce n'était pas le cas, vous auriez besoin d'ajouter ou de soustraire
0x20
, pas seulement de basculer, et pour certaines lettres, il y aurait un report pour inverser d'autres bits supérieurs. (Et il n'y aurait pas une seule opération qui pourrait basculer, et vérifier les caractères alphabétiques en premier lieu serait plus difficile car vous ne pourriez pas | = 0x20 pour forcer lcase.)Astuces connexes ASCII uniquement: vous pouvez rechercher un caractère alphabétique ASCII en forçant les minuscules avec
c |= 0x20
puis en vérifiant si (non signé)c - 'a' <= ('z'-'a')
. Donc, juste 3 opérations: OU + SUB + CMP contre une constante 25. Bien sûr, les compilateurs savent comment optimiser(c>='a' && c<='z')
en asm comme ça pour vous , donc au plus vous devriez faire lac|=0x20
partie vous-même. Il est plutôt gênant de faire tout le cast nécessaire vous-même, en particulier pour contourner les promotions entières par défaut à signéesint
.Voir aussi Convertir une chaîne en C ++ en majuscules (chaîne SIMD
toupper
pour ASCII uniquement, masquant l'opérande pour XOR à l'aide de cette vérification.)Et aussi Comment accéder à un tableau de caractères et changer les lettres minuscules en majuscules, et vice versa (C avec les intrinsèques SIMD, et scalaire x86 asm case-flip pour les caractères alphabétiques ASCII, en laissant les autres inchangés.)
Ces astuces ne sont généralement utiles que si vous optimisez manuellement certains traitements de texte avec SIMD (par exemple SSE2 ou NEON), après avoir vérifié qu'aucun des
char
s dans un vecteur n'a son ensemble de bits haut. (Et donc aucun des octets ne fait partie d'un codage UTF-8 multi-octets pour un seul caractère, qui peut avoir différents inverses majuscules / minuscules). Si vous en trouvez, vous pouvez revenir au scalaire pour ce bloc de 16 octets ou pour le reste de la chaîne.Il existe même certains paramètres régionaux où
toupper()
outolower()
sur certains caractères de la plage ASCII produisent des caractères en dehors de cette plage, notamment le turc où I ↔ ı et İ ↔ i. Dans ces paramètres régionaux, vous auriez besoin d'une vérification plus sophistiquée, ou probablement de ne pas essayer du tout d'utiliser cette optimisation.Mais dans certains cas, vous êtes autorisé à assumer ASCII au lieu de UTF-8, par exemple les utilitaires Unix avec
LANG=C
(la locale POSIX), pasen_CA.UTF-8
ou quoi que ce soit.Mais si vous pouvez vérifier que c'est sûr, vous pouvez
toupper
des chaînes de longueur moyenne beaucoup plus rapidement que d'appelertoupper()
dans une boucle (comme 5x), et pour la dernière fois, j'ai testé avec Boost 1.58 , beaucoup plus rapide queboost::to_upper_copy<char*, std::string>()
ce qui fait un stupidedynamic_cast
pour chaque caractère.la source