В чем идея ^ = 32, которая преобразует строчные буквы в прописные и наоборот?

Я решал некоторые проблемы с codeforces. Обычно я сначала проверяю, является ли символ верхней или нижней английской буквой, затем вычитаю или добавляю, 32чтобы преобразовать его в соответствующую букву. Но я нашел, что кто-то ^= 32делает то же самое. Вот:

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

Я искал объяснение этому и не узнал. Так почему это работает?

Давайте посмотрим на таблицу кодов ASCII в двоичном виде.

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

И 32 - 0100000это единственная разница между строчными и прописными буквами. Так что переключение этого бита переключает регистр букв.

Это использует тот факт, что значения ASCII были выбраны действительно умными людьми.

foo ^= 32;

Это переворачивает 6-й младший бит ¹ из foo(флаг верхнего регистра типа ASCII), преобразуя верхний регистр ASCII в нижний регистр и наоборот .

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

пример

'A' ^ 32

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

И благодаря свойству XOR 'a' ^ 32 == 'A'.

уведомление

C ++ не требуется использовать ASCII для представления символов. Другой вариант - EBCDIC . Этот прием работает только на платформах ASCII. Более переносимым решением было бы использовать std::tolowerи std::toupper, с учетом предлагаемого бонуса, быть осведомленным о локали (хотя это не решает автоматически все ваши проблемы, см. Комментарии):

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

¹⁾ Поскольку 32 равно 1 << 5(2 степени 5), оно переворачивает 6-й бит (считая от 1).

Позвольте мне сказать, что это - хотя это кажется умным - действительно, действительно глупый взлом. Если кто-то порекомендует это вам в 2019 году, поразите его. Ударь его так сильно, как только сможешь.
Конечно, вы можете сделать это в своем собственном программном обеспечении, которое вы и никто другой не используете, если вы знаете, что вы никогда не будете использовать какой-либо язык, кроме английского. В противном случае не идти.

Взлом был спорным «ОК» около 30-35 лет назад, когда компьютеры на самом деле мало что делали, кроме английского в ASCII и, возможно, одного или двух основных европейских языков. Но ... уже не так.

Хак работает, потому что верхний и нижний регистр США-латиницы точно 0x20отделены друг от друга и отображаются в одном и том же порядке, что является лишь одним отличием. Который, на самом деле, этот бит взломать, переключает.

Теперь люди, создающие кодовые страницы для Западной Европы, а затем и консорциум Unicode, были достаточно умны, чтобы сохранить эту схему, например, для немецких умлаутов и гласных с французским акцентом. Это не так, поскольку (пока кто-то не убедил консорциум Unicode в 2017 году, и об этом не написал большой печатный журнал Fake News, на самом деле убедив Duden - без комментариев) , даже не существует как версаль (трансформируется в SS) , Теперь он действительно существует как версальна, но две 0x1DBFпозиции друг от друга, а не 0x20.

Однако разработчики были недостаточно внимательны, чтобы продолжать. Например, если вы примените свой хак на некоторых восточноевропейских языках или тому подобное (я бы не знал о кириллице), вы получите неприятный сюрприз. Все эти символы «топорик» являются примерами того, что строчные и прописные - один за другим. Таким образом, взлом не работает должным образом.

Есть еще много вопросов, которые нужно учитывать, например, некоторые символы не просто преобразуются из строчных в верхние (они заменяются различными последовательностями), либо они могут изменить форму (требуя разных кодовых точек).

Даже не думайте о том, что этот хак сделает с такими вещами, как тайский или китайский (это просто даст вам полную чушь).

Сохранение нескольких сотен циклов ЦП могло бы быть очень полезным 30 лет назад, но в настоящее время действительно нет оправдания для правильного преобразования строки. Существуют библиотечные функции для выполнения этой нетривиальной задачи.
Время , необходимое для преобразования нескольких десятков килобайт текста должным образом в настоящее время незначительно.

Это работает, потому что, как это бывает, разница между 'a' и A 'в ASCII и производных кодировках составляет 32, а 32 также является значением шестого бита. Переключение 6-го бита с исключительным ИЛИ, таким образом, преобразует между верхним и нижним.

Скорее всего, ваша реализация набора символов будет ASCII. Если мы посмотрим на таблицу:

Мы видим, что есть разница 32между значением строчных и прописных чисел. Следовательно, если мы это сделаем ^= 32(что равняется переключению 6-го младшего значащего бита), он меняется между строчными и прописными буквами.

Обратите внимание, что он работает со всеми символами, а не только с буквами. Он переключает символ с соответствующим символом, где 6-й бит отличается, в результате чего получается пара символов, которые переключаются между ними. Для букв соответствующие прописные / строчные буквы образуют такую ​​пару. А NULизменится на Spaceи наоборот, и @переключится с обратной чертой. В основном любой символ в первом столбце на этой диаграмме переключается с символом на один столбец выше, и то же самое относится к третьему и четвертому столбцам.

Я бы не стал использовать этот хак, поскольку нет гарантии, что он будет работать на любой системе. Просто используйте взамен toupper и tolower и такие запросы, как isupper .

Здесь много хороших ответов, которые описывают, как это работает, но почему это работает, так это для повышения производительности. Побитовые операции выполняются быстрее, чем большинство других операций внутри процессора. Вы можете быстро выполнить сравнение без учета регистра, просто не глядя на бит, который определяет регистр, или измените регистр на верхний / нижний, просто перевернув бит (те ребята, которые разработали таблицу ASCII, были довольно умны).

Очевидно, что сегодня это не так важно, как это было в 1960 году (когда впервые началась работа над ASCII), из-за более быстрых процессоров и Unicode, но все еще есть некоторые недорогие процессоры, которые могут существенно изменить ситуацию. до тех пор, пока вы можете гарантировать только символы ASCII.

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

На простых недорогих процессорах побитовые операции обычно выполняются значительно быстрее, чем деление, в несколько раз быстрее, чем умножение, а иногда значительно быстрее, чем сложение.

ПРИМЕЧАНИЕ. Я бы рекомендовал использовать стандартные библиотеки для работы со строками по ряду причин (удобочитаемость, корректность, переносимость и т. Д.). Используйте переворот только в том случае, если вы измерили производительность, и это ваше узкое место.

Вот как работает ASCII, вот и все.

Но используя это, вы отказываетесь от переносимости, поскольку C ++ не настаивает на ASCII в качестве кодировки.

Вот почему функции std::toupperи std::tolowerреализованы в стандартной библиотеке C ++ - вы должны использовать их вместо этого.

См. Вторую таблицу по адресу http://www.catb.org/esr/faqs/things-every-hacker-once-knew/#_ascii и следующие примечания, воспроизведенные ниже:

Модификатор Control на вашей клавиатуре в основном очищает первые три бита любого набираемого вами символа, оставляя нижние пять и отображая его в диапазоне 0.31. Так, например, Ctrl-SPACE, Ctrl- @ и Ctrl-`все означают одно и то же: NUL.

Очень старые клавиатуры использовали Shift, просто переключая 32 или 16 бит, в зависимости от клавиши; Вот почему отношения между маленькими и заглавными буквами в ASCII настолько регулярны, а отношения между цифрами и символами, а также некоторыми парами символов являются регулярными, если вы щуритесь на это. ASR-33, который был полностью прописным терминалом, даже позволял вам генерировать некоторые знаки пунктуации, для которых у него не было ключей, сдвигая 16 бит; таким образом, например, Shift-K (0x4B) стал [(0x5B)

ASCII был разработан таким образом, чтобы shift и ctrlклавиши клавиатуры могут быть реализованы без особой (или , возможно , какой - либо для ctrl) логики - shiftвероятно , требуется всего лишь несколько ворот. Вероятно, имеет смысл хранить как минимум такой же проводной протокол, как и любую другую кодировку символов (никакого программного преобразования не требуется).

Связанная статья также объясняет много странных соглашений хакеров, таких как And control H does a single character and is an old^H^H^H^H^H classic joke.( найденный здесь ).

Xoring с 32 (00100000 в двоичном формате) устанавливает или сбрасывает шестой бит (справа). Это строго эквивалентно сложению или вычитанию 32.

Буквенные диапазоны в нижнем и верхнем регистре не пересекают границу %32«выравнивания» в системе кодирования ASCII.

Вот почему бит 0x20- единственное различие между версиями одной и той же буквы в верхнем / нижнем регистре.

Если бы это было не так, вам нужно было бы добавлять или вычитать 0x20, а не просто переключать, и для некоторых букв было бы выполнено переворачивание других старших бит. (И не было бы ни одной операции, которая могла бы переключаться, и проверка буквенных символов в первую очередь была бы более сложной, потому что вы не могли | = 0x20 заставить lcase.)

Связанные трюки только для ASCII: вы можете проверить алфавитный символ ASCII , введя строчные буквы с, c |= 0x20а затем проверив, если (без знака) c - 'a' <= ('z'-'a'). Так что всего 3 операции: ИЛИ + SUB + CMP против постоянной 25. Конечно, компиляторы знают, как оптимизировать (c>='a' && c<='z') в asm, как это для вас , поэтому самое большее вы должны выполнить c|=0x20сами. Довольно неудобно выполнять все необходимые кастинги самостоятельно, особенно для работы с целочисленными акциями по умолчанию для подписанных 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

См. Также Преобразование строки в C ++ в верхний регистр (SIMD-строка toupperтолько для ASCII, маскировка операнда для XOR с использованием этой проверки.)

А также Как получить доступ к массиву символов и изменить строчные буквы на прописные, и наоборот (C с внутренними SIMD и скалярный x86 asm case-flip для буквенных символов ASCII, оставляя другие без изменений.)

Эти приемы в основном полезны только при ручной оптимизации некоторой обработки текста с помощью SIMD (например, SSE2 или NEON), после проверки того, что ни один из char s в векторе не установлен старший бит. (И, таким образом, ни один из байтов не является частью многобайтовой кодировки UTF-8 для одного символа, который может иметь различные обратные символы верхнего / нижнего регистра). Если вы найдете что-либо, вы можете вернуться к скаляру для этого фрагмента из 16 байтов или для остальной части строки.

Есть даже некоторые места, где toupper()илиtolower() на некоторых символах в диапазоне ASCII производят символы вне этого диапазона, особенно турецкие, где I ↔ ı и İ ↔ i. В этих локалях вам понадобится более сложная проверка, или, возможно, вы вообще не будете пытаться использовать эту оптимизацию.

Но в некоторых случаях вам разрешено использовать ASCII вместо UTF-8, например, утилиты Unix с LANG=C (локаль POSIX), а не что- en_CA.UTF-8либо еще.

Но если вы можете убедиться, что это безопасно, вы можете выполнять toupperстроки средней длины намного быстрее, чем вызывать toupper()в цикле (например, 5x), и последнее, что я тестировал с Boost 1.58 , намного быстрее, чем boost::to_upper_copy<char*, std::string>()глупость dynamic_castдля каждого символа.