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 32
para convertê-lo na letra correspondente. Mas eu encontrei alguém ^= 32
para 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?
c++
bit-manipulation
ascii
Devon
fonte
fonte
@
em `usando^ 32
.toupper
etolower
alternar entre maiúsculas e minúsculas.A
paraZ
. 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.Respostas:
Vamos dar uma olhada na tabela de códigos ASCII em binário.
E 32 é
0100000
a única diferença entre letras minúsculas e maiúsculas. Então, alternar esse bit alterna o caso de uma carta.fonte
{
é menor que[
, portanto, é um caso "inferior". Não? Ok, eu vou me mostrar: Dfoobar[]
efoobar{}
ser apelidos idênticos, como apelidos são caso insensível , e IRC tem suas origens na Escandinávia :)Isso usa o fato de que os valores ASCII foram escolhidos por pessoas realmente inteligentes.
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 .Exemplo
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::tolower
estd::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):1) Como 32 é
1 << 5
(2 à potência 5), ele vira o sexto bit (contando de 1).fonte
tolower
em alemão não precisa apenas de um dicionário, ele deve ser capaz de analisar o significado.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
0x20
separadas 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
0x1DBF
posições à parte, não0x20
.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.
fonte
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.
fonte
Provavelmente, sua implementação do conjunto de caracteres será ASCII. Se olharmos para a mesa:
Vemos que há uma diferença exata
32
entre 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
NUL
mudará paraSpace
o 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 .
fonte
32 ^ 32
é 0, não é 64 #[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 "]".%32
limite de "alinhamento" no sistema de codificação ASCII. Este é por isso que pouco0x20
é 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 subtrair0x20
, 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|= 0x20
a força LCase.)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
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.
fonte
É 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::toupper
estd::tolower
são implementadas na biblioteca padrão C ++ - você deve usá-las.fonte
Veja a segunda tabela em http://www.catb.org/esr/faqs/things-every-hacker-once-knew/#_ascii e as seguintes notas, reproduzidas abaixo:
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 ).fonte
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.foo ^= 0x20 >> !(foo & 0x40)
seria mais simples. Também é um bom exemplo de por que o código conciso é frequentemente considerado ilegível ^ _ ^.O Xoring com 32 (00100000 em binário) define ou redefine o sexto bit (da direita). Isso é estritamente equivalente a adicionar ou subtrair 32.
fonte
As faixas alfabéticas em minúsculas e maiúsculas não cruzam um
%32
limite 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 |= 0x20
e, 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 ac|=0x20
parte você mesmo. É bastante inconveniente fazer toda a conversão necessária, especialmente para contornar promoções inteiras padrão a serem assinadasint
.Consulte também Converter uma sequência
toupper
em 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
char
s 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()
outolower()
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ãoen_CA.UTF-8
ou o que quer.Mas se você pode verificar se é seguro, pode
toupper
usar seqüências de comprimento médio muito mais rápidas do que chamartoupper()
um loop (como 5x), e a última vez que testei com o Boost 1.58 , muito mais rápido do que oboost::to_upper_copy<char*, std::string>()
que é estúpidodynamic_cast
para todos os personagens.fonte