Jaka jest idea ^ = 32, polegająca na zamianie małych liter na duże i odwrotnie?

Rozwiązałem jakiś problem z siłami współrzędnymi. Zwykle najpierw sprawdzam, czy znak jest wielką, czy dolną literą angielską, a następnie odejmuję lub dodaję, 32aby przekonwertować go na odpowiednią literę. Ale znalazłem kogoś, kto zrobił ^= 32to samo. Oto ona:

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

Szukałem wyjaśnienia tego i nie dowiedziałem się. Więc dlaczego to działa?

Rzućmy okiem na binarną tabelę kodów ASCII.

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

A 32 jest 0100000jedyną różnicą między małymi i wielkimi literami. Więc przełączenie tego bitu powoduje przełączenie wielkości liter.

Wykorzystuje to fakt, że wartości ASCII zostały wybrane przez naprawdę inteligentnych ludzi.

foo ^= 32;

Ten odwraca 6. najniższy bit ¹ o foo(wielkie litery flagi ASCII rodzaju), transformujący ASCII górnej pokrywy do dolnej obudowy i odwrotnie .

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

Przykład

'A' ^ 32

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

I mienia XOR 'a' ^ 32 == 'A'.

Ogłoszenie

C ++ nie musi używać ASCII do reprezentowania znaków. Innym wariantem jest EBCDIC . Ta sztuczka działa tylko na platformach ASCII. Bardziej przenośnym rozwiązaniem byłoby użycie std::toloweri std::toupper, z oferowanym bonusem, znajomość języka (nie rozwiązuje to jednak automagicznie wszystkich problemów, patrz komentarze):

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'));

¹⁾ Ponieważ 32 to 1 << 5(2 do potęgi 5), odwraca szósty bit (licząc od 1).

Pozwólcie, że powiem, że jest to - choć wydaje się sprytne - naprawdę głupie hack. Jeśli ktoś ci to poleci w 2019 roku, uderz go. Uderz go tak mocno, jak potrafisz.
Możesz oczywiście zrobić to we własnym oprogramowaniu, którego Ty i nikt inny nie używa, jeśli wiesz, że i tak nigdy nie będziesz używać żadnego języka poza angielskim. W przeciwnym razie nie idź.

Hack był dyskusyjny "OK" jakieś 30-35 lat temu, kiedy komputery tak naprawdę niewiele robiły, poza angielskim w ASCII i może w jednym lub dwóch głównych językach europejskich. Ale ... już nie.

Hack działa, ponieważ wielkie i małe litery w języku amerykańskim i łacińskim są dokładnie 0x20od siebie oddalone i pojawiają się w tej samej kolejności, co stanowi tylko niewielką różnicę. Co w rzeczywistości, ten kawałek włamuje się.

Teraz ludzie tworzący strony kodowe dla Europy Zachodniej, a później konsorcjum Unicode, byli na tyle sprytni, aby zachować ten schemat np. Dla niemieckich umlautów i samogłosek z francuskim akcentem. Nie tak dla ß, które (dopóki ktoś nie przekonał konsorcjum Unicode w 2017 r., A duży drukowany magazyn Fake News napisał o tym, faktycznie przekonując Dudena - bez komentarza) nie istnieje nawet jako wersal (przekształca się w SS) . Teraz to ma istnieć jako Versal, ale dwa są 0x1DBFpozycje od siebie, nie 0x20.

W implementors były jednak nie taktowny tyle, aby utrzymać ten zamiar. Na przykład, jeśli zastosujesz hack w niektórych językach wschodnioeuropejskich lub podobnych (nie wiedziałbym o cyrylicy), otrzymasz paskudną niespodziankę. Wszystkie te „toporki” są tego przykładem, małe i duże litery są jednym z osobna. Dlatego hack nie działa tam poprawnie.

Należy wziąć pod uwagę znacznie więcej, na przykład niektóre znaki w ogóle nie zmieniają się z małych na duże (są zastępowane różnymi sekwencjami) lub mogą zmieniać formę (wymagając różnych punktów kodowych).

Nawet nie myśl o tym, co ten hack zrobi z rzeczami takimi jak tajskie lub chińskie (po prostu dostaniesz kompletny nonsens).

Oszczędność kilkuset cykli procesora mogła być bardzo opłacalna 30 lat temu, ale obecnie nie ma usprawiedliwienia dla prawidłowej konwersji łańcucha. Istnieją funkcje biblioteczne do wykonania tego nietrywialnego zadania.
Czas potrzebny do konwersji kilkadziesiąt kilobajtów tekstu właściwie jest znikoma w dzisiejszych czasach.

Działa, ponieważ tak się składa, że ​​różnica między „a” i A ”w kodowaniu ASCII i pochodnych wynosi 32, a 32 to także wartość szóstego bitu. Odwrócenie szóstego bitu z wyłącznym OR powoduje więc konwersję między górnym a dolnym.

Najprawdopodobniej Twoją implementacją zestawu znaków będzie ASCII. Jeśli spojrzymy na stół:

Widzimy, że istnieje różnica dokładnie 32między wartością małej i dużej litery. Dlatego jeśli to zrobimy ^= 32(co jest równoznaczne z przełączeniem szóstego najmniej znaczącego bitu), zmienia się między małą a wielką literą.

Zauważ, że działa ze wszystkimi symbolami, a nie tylko literami. Przełącza znak z odpowiednim znakiem, w którym szósty bit jest inny, w wyniku czego para znaków jest przełączana między nimi. W przypadku liter odpowiednie duże / małe litery tworzą taką parę. A NULzmieni się w Spacei na odwrót, i @przełącza się z backtickiem. Zasadniczo każdy znak w pierwszej kolumnie na tym wykresie jest przełączany ze znakiem znajdującym się o jedną kolumnę powyżej i to samo dotyczy trzeciej i czwartej kolumny.

Nie użyłbym jednak tego hacka, ponieważ nie ma gwarancji, że zadziała na każdym systemie. Po prostu użyj zamiast tego toupper i tolower oraz zapytań takich jak isupper .

Wiele dobrych odpowiedzi, które opisują, jak to działa, ale dlaczego tak działa, to poprawa wydajności. Operacje bitowe są szybsze niż większość innych operacji w procesorze. Możesz szybko przeprowadzić porównanie bez uwzględniania wielkości liter, po prostu nie patrząc na bit, który określa wielkość liter lub zmieniając wielkość liter na duże / dolne, po prostu odwracając bit (ci faceci, którzy zaprojektowali tabelę ASCII, byli całkiem sprytni).

Oczywiście nie jest to dziś tak wielka transakcja, jak to było w 1960 roku (kiedy po raz pierwszy rozpoczęto prace nad ASCII) ze względu na szybsze procesory i Unicode, ale nadal istnieje kilka tanich procesorów, które mogą mieć znaczący wpływ tak długo, jak możesz zagwarantować tylko znaki ASCII.

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

Na prostych, niedrogich procesorach operacje bitowe są zwykle znacznie szybsze niż dzielenie, kilka razy szybciej niż mnożenie, a czasami znacznie szybciej niż dodawanie.

UWAGA: Zalecałbym używanie standardowych bibliotek do pracy z napisami z kilku powodów (czytelność, poprawność, przenośność itp.). Używaj odwracania bitów tylko wtedy, gdy zmierzyłeś wydajność i to jest twoje wąskie gardło.

Tak działa ASCII, to wszystko.

Ale wykorzystując to, rezygnujesz z przenośności, ponieważ C ++ nie nalega na ASCII jako kodowanie.

Dlatego funkcje std::toupperi std::tolowersą zaimplementowane w standardowej bibliotece C ++ - zamiast tego należy ich używać.

Zobacz drugą tabelę pod adresem http://www.catb.org/esr/faqs/things-every-hacker-once-knew/#_ascii oraz poniższe uwagi, zamieszczone poniżej:

Modyfikator Control na klawiaturze w zasadzie czyści trzy górne bity dowolnego wpisanego znaku, pozostawiając pięć dolnych i mapując je na zakres 0..31. Na przykład Ctrl-SPACE, Ctrl- @ i Ctrl-`oznaczają to samo: NUL.

Bardzo stare klawiatury wykonywały Shift tylko przez przełączanie 32 lub 16 bitów, w zależności od klawisza; dlatego związek między małymi i dużymi literami w ASCII jest tak regularny, a związek między liczbami i symbolami oraz niektórymi parami symboli jest dość regularny, jeśli się na to zmrużysz. ASR-33, który był terminalem składającym się wyłącznie z wielkich liter, pozwolił nawet wygenerować kilka znaków interpunkcyjnych, dla których nie miał kluczy, przez przesunięcie 16-bitowego; w ten sposób, na przykład, Shift-K (0x4B) stało się [(0x5B)

ASCII został zaprojektowany w taki sposób, że klawisze shifti ctrlklawiatury można było zaimplementować bez dużej (lub być może żadnej ctrl) logiki - shiftprawdopodobnie wymagało to tylko kilku bramek. Prawdopodobnie przechowywanie protokołu przewodowego miało co najmniej tyle samo sensu, co inne kodowanie znaków (nie jest wymagana konwersja oprogramowania).

Połączony artykuł wyjaśnia również wiele dziwnych konwencji hakerskich, takich jak And control H does a single character and is an old^H^H^H^H^H classic joke.( znalezione tutaj ).

Xoring z 32 (00100000 binarnie) ustawia lub resetuje szósty bit (od prawej). Jest to ściśle równoważne z dodawaniem lub odejmowaniem 32.

Zakresy pisane małymi i dużymi literami alfabetu nie przekraczają %32granicy „wyrównania” w systemie kodowania ASCII.

Dlatego bit 0x20jest jedyną różnicą między wersjami tej samej litery z dużych / małych liter.

Gdyby tak nie było, musiałbyś dodawać lub odejmować 0x20, a nie tylko przełączać, a dla niektórych liter byłoby przeprowadzane, aby przerzucić inne wyższe bity. (I nie byłoby ani jednej operacji, która mogłaby się przełączać, a sprawdzenie znaków alfabetu w pierwszej kolejności byłoby trudniejsze, ponieważ nie można | = 0x20 wymusić lcase.)

Powiązane sztuczki tylko ASCII: możesz sprawdzić alfabetyczny znak ASCII , wymuszając małe litery za pomocą, c |= 0x20a następnie sprawdzając, czy (bez znaku) c - 'a' <= ('z'-'a'). Więc tylko 3 operacje: OR + SUB + CMP w porównaniu ze stałą 25. Oczywiście kompilatory wiedzą, jak zoptymalizować (c>='a' && c<='z') dla Ciebie taki asm , więc co najwyżej powinieneś wykonać tę c|=0x20część samodzielnie. Raczej niewygodne jest samodzielne wykonywanie wszystkich niezbędnych rzutów, zwłaszcza w celu obejścia domyślnych promocji całkowitych na podpisane 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

Zobacz także Konwertuj ciąg w C ++ na wielkie litery (ciąg SIMD touppertylko dla ASCII, maskujący operand dla XOR przy użyciu tego sprawdzenia).

A także jak uzyskać dostęp do tablicy znaków i zmienić małe litery na duże i odwrotnie (C z elementami wewnętrznymi SIMD i skalarnym odwracaniem wielkości liter x86 asm dla alfabetycznych znaków ASCII, pozostawiając inne niezmodyfikowane).

Te triki są głównie przydatne tylko przy ręcznej optymalizacji przetwarzania tekstu za pomocą SIMD (np. SSE2 lub NEON), po sprawdzeniu, że żaden z chars w wektorze nie ma ustawionego wysokiego bitu. (A zatem żaden z bajtów nie jest częścią wielobajtowego kodowania UTF-8 dla pojedynczego znaku, który może mieć różne odwrotne wielkie / małe litery). Jeśli znajdziesz, możesz wrócić do wartości skalarnej dla tego fragmentu 16-bajtowego lub dla reszty ciągu.

Istnieją nawet ustawienia narodowe, w których toupper()lub tolower()na niektórych znakach z zakresu ASCII tworzą znaki spoza tego zakresu, zwłaszcza tureckie, gdzie I ↔ ı i İ ↔ i. W tych lokalizacjach potrzebowałbyś bardziej wyrafinowanej kontroli lub prawdopodobnie nie próbowałbyś w ogóle używać tej optymalizacji.

Ale w niektórych przypadkach możesz założyć ASCII zamiast UTF-8, np. Narzędzia Unix z LANG=C(locale POSIX), nie en_CA.UTF-8lub cokolwiek.

Ale jeśli możesz zweryfikować, że jest to bezpieczne, możesz toupperznacznie szybciej łańcuchy średniej długości niż wywoływanie toupper()w pętli (np. 5x), a ostatnio testowałem z Boost 1.58 , znacznie szybciej niż boost::to_upper_copy<char*, std::string>()robi to głupio dynamic_castdla każdej postaci.