Quelle est l'idée derrière ^ = 32, qui convertit les lettres minuscules en majuscules et vice versa?

146

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 ^= 32pour 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?

Devon
la source
5
en.wikipedia.org/wiki/File:USASCII_code_chart.png Astuce: vous pouvez convertir @en `en utilisant ^ 32.
KamilCuk
112
FWIW, ça ne "marche" pas vraiment. Cela fonctionne pour ce jeu de caractères particulier, mais il existe d'autres jeux où ce ne sera pas le cas. Vous devriez utiliser toupperet tolowerchanger de casse.
NathanOliver
7
parfois avec des concours en ligne "l'idée" est d'écrire du code d'une manière si obscure qu'il ne passerait jamais un examen sérieux;)
idclev 463035818
21
^ = transforme la valeur en utilisant XOR. Les lettres ASCII majuscules ont un zéro dans le bit correspondant, tandis que les lettres minuscules en ont un. Cela dit, ne le faites pas! Utilisez des routines de caractères (Unicode) appropriées pour convertir entre minuscules et majuscules. L'ère de l'ASCII est révolue depuis longtemps.
Hans-Martin Mosner
14
Ce n'est pas seulement que cela fonctionne uniquement avec certains jeux de caractères. Même si nous supposons que tout le monde est UTF-8 (ce qui pourrait au moins être un bel objectif utopique), cela ne fonctionne également qu'avec les 26 lettres 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.
ilkkachu

Réponses:

149

Jetons un œil à la table de code ASCII en binaire.

A 1000001    a 1100001
B 1000010    b 1100010
C 1000011    c 1100011
...
Z 1011010    z 1111010

Et 32 est 0100000la seule différence entre les lettres minuscules et majuscules. Donc, basculer ce bit bascule la casse d'une lettre.

Hanjoung Lee
la source
49
"bascule le cas" * uniquement pour ASCII
Mooing Duck
39
@Mooing uniquement pour A-Za-z en ASCII. La minuscule de "[" n'est pas "{".
dbkk le
21
@dbkk {est plus court que [, donc c'est une casse "minuscule". Non? Ok, je vais me montrer: D
Peter Badida
25
Trivia Tidbit: Dans la zone 7 bits, les ordinateurs allemands avaient [] {|} remappé en ÄÖÜäöü puisque nous avions besoin de Umlauts plus que ces caractères, donc dans ce contexte, {(ä) était en fait la minuscule [(Ä).
Guntram Blohm soutient Monica le
14
@GuntramBlohm Plus de détails, c'est pourquoi les serveurs IRC considèrent foobar[] et foobar{}sont des surnoms identiques, car les surnoms sont insensibles à la casse , et IRC a ses origines en Scandinavie :)
ZeroKnight
117

Cela utilise le fait que les valeurs ASCII ont été choisies par des personnes vraiment intelligentes.

foo ^= 32;

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 .

+---+------------+------------+
|   | Upper case | Lower case |  32 is 00100000
+---+------------+------------+
| A | 01000001   | 01100001   |
| B | 01000010   | 01100010   |
|            ...              |
| Z | 01011010   | 01111010   |
+---+------------+------------+

Exemple

'A' ^ 32

    01000001 'A'
XOR 00100000 32
------------
    01100001 'a'

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::toloweret std::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):

bool case_incensitive_equal(char lhs, char rhs)
{
    return std::tolower(lhs, std::locale{}) == std::tolower(rhs, std::locale{}); // std::locale{} optional, enable locale-awarness
}

assert(case_incensitive_equal('A', 'a'));

1) Comme 32 est 1 << 5(2 à la puissance 5), il retourne le 6e bit (à partir de 1).

YSC
la source
16
EBCDIC a également été choisi par des personnes très intelligentes: fonctionne très bien sur les cartes perforées cf. ASCII qui est un gâchis. Mais c'est une bonne réponse, +1.
Bathsheba
65
Je ne sais pas sur les cartes perforées, mais ASCII a été utilisé sur du ruban adhésif. C'est pourquoi le caractère Supprimer est codé comme 1111111: Vous pouvez donc marquer n'importe quel caractère comme "supprimé" en perforant tous les trous de sa colonne sur la bande.
dan04
23
@Bathsheba en tant que personne qui n'a pas utilisé de carte perforée, il est très difficile de comprendre l'idée que EBCDIC a été conçu intelligemment.
Lord Farquaad
9
@LordFarquaad À mon humble avis, l'image Wikipédia de la façon dont les lettres sont écrites sur une carte perforée est une illustration évidente de la façon dont EBCDIC a un certain sens (mais pas total, voir / vs S) pour cet encodage. en.wikipedia.org/wiki/EBCDIC#/media/…
Peteris
11
@ dan04 Remarque pour mentionner "quelle est la forme minuscule de 'MASSE'?". Pour ceux qui ne savent pas, il y a deux mots en allemand dont la forme majuscule est MASSE; l'un est "Masse" et l'autre est "Maße". Le bon toloweren allemand n'a pas seulement besoin d'un dictionnaire, il doit être capable d'en analyser le sens.
Martin Bonner soutient Monica le
35

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 0x20sé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 0x1DBFpositions 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.

Damon
la source
2
Je suis tout à fait d'accord - même si c'est une bonne idée pour chaque programmeur de savoir pourquoi cela fonctionne - pourrait même faire une bonne question d'entrevue. Qu'est-ce que cela fait et quand doit-il être utilisé :)
Bill K
33

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.

Jack Aidley
la source
22

Votre implémentation du jeu de caractères sera très probablement ASCII. Si nous regardons le tableau:

entrez la description de l'image ici

Nous voyons qu'il y a une différence d'exactement 32entre 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 NULse transforme en Spaceet 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 .

Flamber
la source
2
Eh bien, cela ne fonctionne pas pour toutes les lettres qui ont une différence de 32. Sinon, cela fonctionnerait entre «@» et «»!
Matthieu Brucher
2
@MatthieuBrucher Ça marche, 32 ^ 32c'est 0, pas 64
NathanOliver
5
«@» et «» ne sont pas des «lettres». Seulement [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 "]".
Freedomn-m
4
@MatthieuBrucher: Une autre façon de faire valoir ce point est que les plages alphabétiques minuscules et majuscules ne traversent pas une %32limite "d'alignement" dans le système de codage ASCII. C'est pourquoi le bit 0x20est 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 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 |= 0x20forcer la case.)
Peter Cordes
2
+1 pour m'avoir rappelé toutes ces visites sur asciitable.com pour regarder ce graphique exact (et la version ASCII étendue !!) pour la dernière, je ne sais pas, 15 ou 20 ans?
AC
15

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

Sur les processeurs simples à faible coût, les opérations au niveau du bit sont généralement beaucoup plus rapides que la division, plusieurs fois plus rapides que la multiplication et parfois beaucoup plus rapides que l'addition.

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.

Brian
la source
14

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::toupperet std::tolowersont implémentées dans la bibliothèque standard C ++ - vous devriez les utiliser à la place.

Bathsheba
la source
6
Il existe cependant des protocoles qui nécessitent l'utilisation de l'ASCII, comme DNS. En fait, le "truc 0x20" est utilisé par certains serveurs DNS pour insérer une entropie supplémentaire dans une requête DNS en tant que mécanisme anti-spoofing. Le DNS est insensible à la casse, mais est également censé préserver la casse, donc si vous envoyez une requête avec une casse aléatoire et récupérez la même casse, c'est une bonne indication que la réponse n'a pas été usurpée par un tiers.
Alnitak
Il convient de mentionner que de nombreux encodages ont toujours la même représentation pour les caractères ASCII standard (non étendus). Mais quand même, si vous vous inquiétez vraiment des différents encodages, vous devez utiliser les fonctions appropriées.
Captain Man
5
@CaptainMan: Absolument. UTF-8 est une chose de toute beauté. Espérons qu'il soit "absorbé" dans le standard C ++ dans la mesure où IEEE754 a pour virgule flottante.
Bathsheba
11

Voir le deuxième tableau à http://www.catb.org/esr/faqs/things-every-hacker-once-knew/#_ascii , et les notes suivantes, reproduites ci-dessous:

Le modificateur Control de votre clavier efface essentiellement les trois premiers bits de tout caractère que vous tapez, laissant les cinq derniers et les mappant à la plage 0..31. Ainsi, par exemple, Ctrl-ESPACE, Ctrl- @ et Ctrl-`signifient tous la même chose: NUL.

Les très vieux claviers utilisaient le Shift simplement en basculant le 32 ou le 16 bits, selon la touche; c'est pourquoi la relation entre les lettres minuscules et majuscules en ASCII est si régulière, et la relation entre les nombres et les symboles, et certaines paires de symboles, est en quelque sorte régulière si vous plissez les yeux. L'ASR-33, qui était un terminal entièrement en majuscules, vous permettait même de générer des caractères de ponctuation pour lesquels il n'avait pas de clés en décalant le 16 bits; ainsi, par exemple, Shift-K (0x4B) est devenu un [(0x5B)

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 ).

Iiridayn
la source
1
Pourrait implémenter une bascule de décalage pour plus d'ASCII avec / 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.
Iiridayn
1
Ah, ce 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 ^ _ ^.
Iiridayn
8

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.

Yves Daoust
la source
2
Une autre façon de dire cela est que XOR est add-without-carry.
Peter Cordes
7

Les plages alphabétiques minuscules et majuscules ne traversent pas une %32limite "d'alignement" dans le système de codage ASCII.

C'est pourquoi le bit 0x20est 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 |= 0x20puis 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 la c|=0x20partie 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ées int.

unsigned char lcase = y|0x20;
if (lcase - 'a' <= (unsigned)('z'-'a')) {   // lcase-'a' will wrap for characters below 'a'
    // c is alphabetic ASCII
}
// else it's not

Voir aussi Convertir une chaîne en C ++ en majuscules (chaîne SIMD toupperpour 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 chars 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()ou tolower()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), pas en_CA.UTF-8ou quoi que ce soit.

Mais si vous pouvez vérifier que c'est sûr, vous pouvez toupperdes chaînes de longueur moyenne beaucoup plus rapidement que d'appeler toupper()dans une boucle (comme 5x), et pour la dernière fois, j'ai testé avec Boost 1.58 , beaucoup plus rapide que boost::to_upper_copy<char*, std::string>()ce qui fait un stupide dynamic_castpour chaque caractère.

Peter Cordes
la source