Qual é a idéia por trás de ^ = 32, que converte letras minúsculas em maiúsculas e vice-versa?

146

Eu estava resolvendo algum problema nas forças de código. Normalmente, verifico primeiro se o caractere é uma letra em inglês superior ou inferior e subtraio ou adiciono 32para convertê-lo na letra correspondente. Mas eu encontrei alguém ^= 32para fazer a mesma coisa. Aqui está:

char foo = 'a';
foo ^= 32;
char bar = 'A';
bar ^= 32;
cout << foo << ' ' << bar << '\n'; // foo is A, and bar is a

Procurei uma explicação para isso e não descobri. Então, por que isso funciona?

Devon
fonte
5
pt.wikipedia.org/wiki/File:USASCII_code_chart.png Dica: você pode converter @em `usando ^ 32.
21419 KamilCuk
112
FWIW, realmente não "funciona". Ele funciona para esse conjunto de caracteres específico, mas existem outros conjuntos em que não. Você deve usar touppere toloweralternar entre maiúsculas e minúsculas.
NathanOliver
7
em algum momento com competições online "a idéia" é escrever código de uma forma tão ofuscado que ele nunca iria passar por uma revisão séria;)
idclev 463035818
21
^ = está transformando o valor usando XOR. Letras ASCII maiúsculas têm zero no bit correspondente, enquanto letras minúsculas têm um zero. Dito isto, por favor não! Use rotinas de caracteres (unicode) adequadas para converter entre minúsculas e maiúsculas. A era de apenas ASCII se foi há muito tempo.
Hans-Martin Mosner 5/02/19
14
Não é apenas o fato de funcionar apenas com alguns conjuntos de caracteres. Mesmo se assumirmos que todo o mundo é UTF-8 (o que pode ser pelo menos um bom objetivo utópico), ele também funciona apenas com as 26 letras Apara Z. Tudo bem, desde que você se preocupe apenas com o inglês (e não use grafias "ingênuas", palavras como "café" ou nomes com diacríticos ...), mas o mundo não é apenas inglês.
ilkkachu 5/02/19

Respostas:

149

Vamos dar uma olhada na tabela de códigos ASCII em binário.

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

E 32 é 0100000a única diferença entre letras minúsculas e maiúsculas. Então, alternar esse bit alterna o caso de uma carta.

Hanjoung Lee
fonte
49
"alterna o caso" * apenas para ASCII
Mooing Duck
39
@Mooing apenas para A-Za-z em ASCII. Letras minúsculas de "[" não são "{".
dbkk 6/02/19
21
@dbkk {é menor que [, portanto, é um caso "inferior". Não? Ok, eu vou me mostrar: D
Peter Badida 06/02/19
25
Curiosidades: na área de 7 bits, os computadores alemães [] {|} remapearam para ÄÖÜäöü, pois precisávamos de Umlauts mais do que esses caracteres, portanto, nesse contexto, {(ä) na verdade era o minúsculo [(Ä).
Guntram Blohm apoia Monica
14
@GuntramBlohm Além disso trivia boato, é por isso servidores IRC considerar foobar[] e foobar{}ser apelidos idênticos, como apelidos são caso insensível , e IRC tem suas origens na Escandinávia :)
zeroknight
117

Isso usa o fato de que os valores ASCII foram escolhidos por pessoas realmente inteligentes.

foo ^= 32;

Isso inverte o sexto bit mais baixo 1 de foo(o sinalizador maiúsculo de ASCII), transformando uma maiúscula em ASCII em minúscula e vice-versa .

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

Exemplo

'A' ^ 32

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

E por propriedade de XOR 'a' ^ 32 == 'A',.

Aviso prévio

C ++ não é necessário para usar ASCII para representar caracteres. Outra variante é EBCDIC . Este truque funciona apenas em plataformas ASCII. Uma solução mais portátil seria usar std::tolowere std::toupper, com o bônus oferecido para reconhecer o código de idioma (embora não resolva automaticamente todos os seus problemas, consulte os comentários):

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) Como 32 é 1 << 5(2 à potência 5), ​​ele vira o sexto bit (contando de 1).

YSC
fonte
16
O EBCDIC também foi escolhido por algumas pessoas muito inteligentes: funciona muito bem em cartões perfurados, cf. ASCII que é uma bagunça. Mas esta é uma boa resposta, +1.
Bathsheba
65
Eu não sei sobre cartões perfurados, mas o ASCII foi usado em fita de papel. É por isso que o caractere Excluir é codificado como 1111111: Para que você possa marcar qualquer caractere como "excluído", perfure todos os furos em sua coluna na fita.
precisa saber é
23
@Bathsheba como alguém que não usou um cartão perfurado, é muito difícil entender a ideia de que o EBCDIC foi projetado de forma inteligente.
Lord Farquaad
9
@ LordFarquaad IMHO A imagem da Wikipedia de como as letras são escritas em um cartão perfurado é uma ilustração óbvia de como o EBCDIC faz algum sentido (mas não total, veja / vs S) para essa codificação. pt.wikipedia.org/wiki/EBCDIC#/media/…
Peteris
11
@ dan04 Nota para mencionar "qual é a forma minúscula de 'MASSE'?". Para quem não sabe, existem duas palavras em alemão cuja forma maiúscula é MASSE; um é "Massagista" e o outro é "Maße". Adequado tolowerem alemão não precisa apenas de um dicionário, ele deve ser capaz de analisar o significado.
Martin Bonner apoia Monica
35

Permitam-me dizer que este é - embora pareça inteligente - um hack muito, muito estúpido. Se alguém lhe recomendar isso em 2019, acerte-o. Bata nele o mais forte que puder.
Obviamente, você pode fazer isso em seu próprio software que você e mais ninguém usa se souber que nunca usará nenhum idioma além do inglês. Caso contrário, não vá.

O hack foi discutível "OK" cerca de 30 a 35 anos atrás, quando os computadores realmente não faziam muito além do inglês em ASCII, e talvez um ou dois dos principais idiomas europeus. Mas ... não é mais assim.

O hack funciona porque as maiúsculas e minúsculas latino-americanas estão exatamente 0x20separadas uma da outra e aparecem na mesma ordem, o que é apenas uma diferença. O que, de fato, este pequeno truque, alterna.

Agora, as pessoas que criaram páginas de código para a Europa Ocidental e, mais tarde, o consórcio Unicode, foram inteligentes o suficiente para manter esse esquema, por exemplo, tremados alemães e vogais com sotaque francês. Não é o caso de ß que (até alguém convencer o consórcio Unicode em 2017 e uma grande revista impressa do Fake News escrever sobre isso, convencendo o Duden - nenhum comentário sobre isso) nem existe como um versal (se transforma em SS) . Agora não existe como Versal, mas os dois são 0x1DBFposições à parte, não 0x20.

Os implementadores, no entanto, não foram atenciosos o suficiente para continuar. Por exemplo, se você aplicar o seu hack em alguns idiomas da Europa Oriental ou similares (eu não saberia sobre cirílico), você terá uma surpresa desagradável. Todos esses caracteres "machadinha" são exemplos disso, letras minúsculas e maiúsculas são uma à parte. O hack, portanto, não funciona corretamente lá.

Há muito mais a considerar, por exemplo, alguns caracteres não se transformam simplesmente de minúsculas para maiúsculas (eles são substituídos por sequências diferentes) ou podem mudar de forma (exigindo diferentes pontos de código).

Nem pense no que esse hack fará para coisas como tailandês ou chinês (isso só lhe dará um absurdo).

Salvar algumas centenas de ciclos de CPU pode ter valido muito a pena 30 anos atrás, mas hoje em dia não há realmente desculpa para converter corretamente uma string. Existem funções de biblioteca para executar esta tarefa não trivial.
O tempo necessário para converter várias dezenas de kilobytes de texto corretamente é insignificante hoje em dia.

Damon
fonte
2
Eu concordo totalmente - embora seja uma boa idéia para cada programador para saber por que ela funciona - pode até mesmo fazer uma boa pergunta da entrevista .. O que isso fazer e quando ele deve ser usado :)
Bill K
33

Isso funciona porque, por acaso, a diferença entre 'a' e A 'em ASCII e codificações derivadas é 32, e 32 também é o valor do sexto bit. Inverter o sexto bit com um OR exclusivo converte entre superior e inferior.

Jack Aidley
fonte
22

Provavelmente, sua implementação do conjunto de caracteres será ASCII. Se olharmos para a mesa:

insira a descrição da imagem aqui

Vemos que há uma diferença exata 32entre o valor de um número minúsculo e maiúsculo. Portanto, se o fizermos ^= 32(o que equivale a alternar o sexto bit menos significativo), ele muda entre um caractere minúsculo e um maiúsculo.

Observe que ele funciona com todos os símbolos, não apenas as letras. Alterna um caractere com o respectivo caractere, onde o sexto bit é diferente, resultando em um par de caracteres que é alternado entre eles. Para as letras, os respectivos caracteres maiúsculos / minúsculos formam esse par. A NULmudará para Spaceo contrário e @alternará com o backtick. Basicamente, qualquer caractere na primeira coluna deste gráfico alterna com o caractere sobre uma coluna e o mesmo se aplica à terceira e quarta colunas.

Eu não usaria esse truque, pois não há garantia de que ele funcione em qualquer sistema. Basta usar toupper e tolower , e consultas como isupper .

Chama
fonte
2
Bem, não funciona para todas as letras com diferença de 32. Caso contrário, funcionaria entre '@' e ''!
Matthieu Brucher 5/02/19
2
@MatthieuBrucher Ele está funcionando, 32 ^ 32é 0, não é 64 #
NathanOliver 5/19/19
5
'@' e '' não são "letras". Somente [a-z]e [A-Z]são "letras". O resto são coincidências que seguem a mesma regra. Se alguém lhe pedisse "maiúscula]", qual seria? ainda seria "]" - "}" não é a "maiúscula" de "]".
freedomn-m
4
@ MatthieuBrucher: Outra maneira de enfatizar esse ponto é que os intervalos alfabéticos de letras minúsculas e maiúsculas não cruzam um %32limite de "alinhamento" no sistema de codificação ASCII. Este é por isso que pouco 0x20é a única diferença entre os mais baixos versões superiores / caso da mesma carta. Se não fosse esse o caso, você precisaria adicionar ou subtrair 0x20, não apenas alternar, e para algumas letras, seria necessário realizar outros giros mais altos. (E a mesma operação poderia não alternância, e verificação de caracteres alfabéticos, em primeiro lugar seria mais difícil porque você não poderia |= 0x20a força LCase.)
Peter Cordes
2
+1 por me lembrar de todas aquelas visitas ao asciitable.com para olhar para aquele gráfico exato (e a versão ASCII estendida !!) nos últimos 12 anos, não sei, 15 ou 20 anos?
AC
15

Muitas boas respostas aqui descrevem como isso funciona, mas por que funciona dessa maneira é melhorar o desempenho. As operações bit a bit são mais rápidas que a maioria das outras operações em um processador. Você pode fazer rapidamente uma comparação sem distinção entre maiúsculas e minúsculas, simplesmente não olhando para o bit que determina maiúsculas e minúsculas para superior / inferior, simplesmente invertendo o bit (aqueles que criaram a tabela ASCII eram bastante inteligentes).

Obviamente, isso não é tão grande hoje em dia, como era em 1960 (quando o trabalho começou em ASCII) devido a processadores mais rápidos e Unicode, mas ainda existem processadores de baixo custo que podem fazer uma diferença significativa desde que você possa garantir apenas caracteres ASCII.

https://en.wikipedia.org/wiki/Bitwise_operation

Em processadores simples de baixo custo, normalmente, as operações bit a bit são substancialmente mais rápidas que a divisão, várias vezes mais rápidas que a multiplicação e algumas vezes significativamente mais rápidas que a adição.

NOTA: Eu recomendaria o uso de bibliotecas padrão para trabalhar com seqüências de caracteres por vários motivos (legibilidade, correção, portabilidade, etc.). Use apenas inversão de bits se você mediu o desempenho e esse é seu gargalo.

Brian
fonte
14

É assim que o ASCII funciona, só isso.

Mas, ao explorar isso, você está desistindo da portabilidade, pois o C ++ não insiste em ASCII como codificação.

É por isso que as funções std::touppere std::tolowersão implementadas na biblioteca padrão C ++ - você deve usá-las.

Bathsheba
fonte
6
No entanto, existem protocolos que exigem o uso de ASCII, como o DNS. De fato, o "truque 0x20" é usado por alguns servidores DNS para inserir entropia adicional em uma consulta DNS como um mecanismo antifalsificação. O DNS não diferencia maiúsculas de minúsculas, mas também deve preservar maiúsculas e minúsculas; portanto, se enviar uma consulta com maiúsculas e minúsculas e recuperar o mesmo caso, é uma boa indicação de que a resposta não foi falsificada por terceiros.
Alnitak
Vale ressaltar que muitas codificações ainda têm a mesma representação para os caracteres ASCII padrão (não estendidos). Ainda assim, se você estiver realmente preocupado com codificações diferentes, use as funções apropriadas.
Capitão Man
5
@CaptainMan: Absolutamente. UTF-8 é uma coisa de pura beleza. Espero que seja "absorvido" no padrão C ++, na medida em que o IEEE754 possui um ponto flutuante.
Bathsheba
11

Veja a segunda tabela em http://www.catb.org/esr/faqs/things-every-hacker-once-knew/#_ascii e as seguintes notas, reproduzidas abaixo:

O modificador Control no teclado limpa basicamente os três bits principais de qualquer caractere digitado, deixando os cinco inferiores e mapeando-o para o intervalo 0..31. Então, por exemplo, Ctrl-SPACE, Ctrl- @ e Ctrl-`significam a mesma coisa: NUL.

Teclados muito antigos costumavam fazer Shift apenas alternando os 32 ou 16 bits, dependendo da tecla; é por isso que o relacionamento entre letras maiúsculas e minúsculas em ASCII é tão regular, e o relacionamento entre números e símbolos e alguns pares de símbolos é um tanto regular se você olha de soslaio. O ASR-33, que era um terminal todo em maiúsculas, até permite gerar alguns caracteres de pontuação para os quais não havia chaves, deslocando o 16 bits; assim, por exemplo, Shift-K (0x4B) tornou-se um [(0x5B)

O ASCII foi projetado para que as teclas shifte do ctrlteclado pudessem ser implementadas sem muita (ou talvez nenhuma ctrl) lógica - shiftprovavelmente exigindo apenas algumas portas. Provavelmente, fazia pelo menos tanto sentido armazenar o protocolo de conexão quanto qualquer outra codificação de caracteres (não é necessária nenhuma conversão de software).

O artigo vinculado também explica muitas convenções estranhas de hackers, como And control H does a single character and is an old^H^H^H^H^H classic joke.( encontradas aqui ).

Iiridayn
fonte
1
Poderia implementar uma alternância de deslocamento para mais de ASCII c / foo ^= (foo & 0x60) == 0x20 ? 0x10 : 0x20, embora este seja apenas ASCII e, portanto, imprudente por razões declaradas em outras respostas. Provavelmente também pode ser aprimorado com programação sem ramificação.
Iiridayn
1
Ah, foo ^= 0x20 >> !(foo & 0x40)seria mais simples. Também é um bom exemplo de por que o código conciso é frequentemente considerado ilegível ^ _ ^.
Iiridayn 08/02/19
8

O Xoring com 32 (00100000 em binário) define ou redefine o sexto bit (da direita). Isso é estritamente equivalente a adicionar ou subtrair 32.

Yves Daoust
fonte
2
Outra maneira de dizer isso é que o XOR é um add-sem-carry.
Peter Cordes
7

As faixas alfabéticas em minúsculas e maiúsculas não cruzam um %32limite de "alinhamento" no sistema de codificação ASCII.

É por isso que bit 0x20é a única diferença entre as versões maiúsculas / minúsculas da mesma letra.

Se esse não fosse o caso, você precisaria adicionar ou subtrair 0x20, não apenas alternar, e para algumas letras, seria necessário realizar outros giros mais altos. (E não haveria uma única operação que pudesse alternar, e a verificação de caracteres alfabéticos em primeiro lugar seria mais difícil porque você não poderia | = 0x20 forçar o lcase.)


Truques somente ASCII relacionados: você pode verificar se há um caractere ASCII alfabético forçando letras minúsculas com c |= 0x20e, em seguida, verificando se (não assinado) c - 'a' <= ('z'-'a'). Portanto, apenas três operações: OR + SUB + CMP em relação a 25 constantes. É claro que os compiladores sabem como otimizar (c>='a' && c<='z') um ASM assim para você , portanto, no máximo, você deve fazer a c|=0x20parte você mesmo. É bastante inconveniente fazer toda a conversão necessária, especialmente para contornar promoções inteiras padrão a serem assinadas 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

Consulte também Converter uma sequência toupperem C ++ em maiúscula (sequência SIMD apenas para ASCII, mascarando o operando para o XOR usando essa verificação).

E também Como acessar uma matriz de caracteres e alterar letras minúsculas para maiúsculas e vice-versa (C com intrínsecas SIMD e x86 asm escalar maiúsculas e minúsculas para caracteres ASCII alfabéticos, deixando outros não modificados).


Esses truques são úteis apenas se você otimiza manualmente algum processamento de texto com SIMD (por exemplo, SSE2 ou NEON), depois de verificar se nenhum dos chars em um vetor tem seu bit alto definido. (E, portanto, nenhum dos bytes faz parte de uma codificação UTF-8 de vários bytes para um único caractere, que pode ter diferentes inversos maiúsculas / minúsculas). Se você encontrar algum, poderá voltar ao escalar para esse pedaço de 16 bytes ou para o restante da cadeia.

Existem até algumas localidades em que toupper()ou tolower()em alguns caracteres do intervalo ASCII produzem caracteres fora desse intervalo, principalmente turcos onde I I e İ ↔ i. Nesses locais, você precisaria de uma verificação mais sofisticada ou provavelmente não tentará usar essa otimização.


Mas, em alguns casos, você pode assumir ASCII em vez de UTF-8, por exemplo, utilitários Unix com LANG=C(o local POSIX), não en_CA.UTF-8ou o que quer.

Mas se você pode verificar se é seguro, pode toupperusar seqüências de comprimento médio muito mais rápidas do que chamar toupper()um loop (como 5x), e a última vez que testei com o Boost 1.58 , muito mais rápido do que o boost::to_upper_copy<char*, std::string>()que é estúpido dynamic_castpara todos os personagens.

Peter Cordes
fonte