Я решал некоторые проблемы с 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-й младший бит 1 из 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'));
1) Поскольку 32 равно 1 << 5 (от 2 до степени 5), оно переворачивает 6-й бит (считая от 1).
Это работает, потому что, как это бывает, разница между 'a' и A 'в ASCII и производных кодировках составляет 32, а 32 также является значением шестого бита. Переключение 6-го бита с исключительным ИЛИ, таким образом, преобразует между верхним и нижним.
Позвольте мне сказать, что это - хотя это кажется умным - действительно, действительно глупый взлом. Если кто-то порекомендует это вам в 2019 году, поразите его. Ударь его так сильно, как только сможешь.
Конечно, вы можете делать это в своем собственном программном обеспечении, которое вы и никто другой не используете, если вы знаете, что никогда не будете использовать какой-либо язык, кроме английского. В противном случае не идти.
Возможно, взлом был "ОК" 30-35 лет назад, когда компьютеры почти ничего не делали, кроме английского в ASCII и, возможно, одного или двух основных европейских языков. Но... уже не так.
Хак работает, потому что латиница США upper- и строчные буквы находятся точно на расстоянии 0x20 друг от друга и отображаются в одинаковом порядке, что является лишь одним отличием. Который, на самом деле, этот бит взломать, переключает.
Теперь люди, создающие кодовые страницы для Западной Европы, а затем и консорциум Unicode, были достаточно умны, чтобы сохранить эту схему, например, для немецких умлаутов и гласных с французским акцентом. Это не так для ß, который (пока кто-то не убедил консорциум Unicode в 2017 году, и об этом не написал большой печатный журнал Fake News, на самом деле убедивший Duden - без комментариев) даже не существует как версаль (трансформируется в SS), Теперь он существует как версаль, но эти две позиции расположены на расстоянии 0x1DBF, а не на 0x20.
Однако разработчики были недостаточно внимательны, чтобы продолжать. Например, если вы примените свой хак на некоторых восточноевропейских языках или тому подобное (я бы не знал о кириллице), вас ждет неприятный сюрприз. Все эти символы "топорик" являются примерами того, что строчные и прописные - это одно. Таким образом, взлом не работает должным образом.
Есть еще кое-что, что можно рассмотреть, например, некоторые символы не просто преобразуются из lower- в верхний регистр вообще (они заменяются различными последовательностями), или они могут изменить форму (требуя разных кодовых точек).
Даже не думайте о том, что этот хак сделает с такими вещами, как тайский или китайский (это просто даст вам полную чушь).
Сохранение нескольких сотен циклов ЦП могло бы быть очень полезным 30 лет назад, но в настоящее время действительно нет оправдания для правильного преобразования строки. Есть библиотечные функции для выполнения этой нетривиальной задачи.
Время, необходимое для правильного преобразования нескольких десятков килобайт текста, в наше время ничтожно мало.
Скорее всего, ваша реализация набора символов будет ASCII. Если мы посмотрим на таблицу:
Мы видим, что разница между значением строчных и прописных чисел составляет ровно 32. Поэтому, если мы делаем ^= 32 (что соответствует переключению 6-го младшего значащего бита), он меняется между строчными и прописными буквами.
Обратите внимание, что он работает со всеми символами, а не только с буквами. Он переключает символ с соответствующим символом, где 6-й бит отличается, в результате чего получается пара символов, которые переключаются между ними. Для букв соответствующие прописные/строчные буквы образуют такую пару. NUL изменится на Space и наоборот, а NUL @ переключаться с обратной черты. По сути, любой символ в первом столбце этой диаграммы переключается с символом на один столбец выше, и то же самое относится к третьему и четвертому столбцам.
Я бы не стал использовать этот хак, так как не могу гарантировать, что он будет работать на любой системе. Просто используйте взамен toupper и tolower и такие запросы, как isupper.
Это как ASCII работает, вот и все.
Но, используя это, вы отказываетесь от переносимости, поскольку C++ не настаивает на ASCII в качестве кодировки.
Вот почему функции std::toupper и std::tolower реализованы в стандартной библиотеке C++ - вы должны использовать их вместо этого.
Здесь много хороших ответов, которые описывают, как это работает, но почему это работает, так это для повышения производительности. Побитовые операции выполняются быстрее, чем большинство других операций внутри процессора. Вы можете быстро выполнить сравнение без учета регистра, просто не глядя на бит, который определяет регистр, или измените регистр на верхний/нижний, просто перевернув бит (те ребята, которые разработали таблицу ASCII, были довольно умны).
Очевидно, что сегодня это не так важно, как это было в 1960 году (когда впервые началась работа над ASCII), из-за более быстрых процессоров и Unicode, но все еще есть некоторые недорогие процессоры, которые могут иметь существенное значение до тех пор, пока вы можете гарантировать только символы ASCII.
https://en.wikipedia.org/wiki/Bitwise_operation
На простых недорогих процессорах побитовые операции обычно выполняются значительно быстрее, чем деление, в несколько раз быстрее, чем умножение, а иногда значительно быстрее, чем сложение.
ПРИМЕЧАНИЕ. Я бы порекомендовал использовать стандартные библиотеки для работы со строками по ряду причин (удобочитаемость, корректность, переносимость и т.д.). Используйте переворот только в том случае, если вы измерили производительность, и это ваше узкое место.
См. Вторую таблицу по адресу 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 а затем проверив (без знака) if(c - 'a' < ('a'-'z')). Так что всего 3 операции: ИЛИ + SUB + CMP против постоянной 25.
unsigned char lcase = c|0x20;
if (lcase - 'a' < ('a'-'z')) { // lcase-'a' will wrap for characters below 'a'
// c is alphabetic ASCII
}
// else it not
Смотрите также Преобразование строки в C++ в верхнем регистре (SIMD строки toupper для только ASCII, маскируя операнд для XOR с помощью этой проверки.)
А также Как получить доступ к массиву символов и изменить строчные буквы на прописные, и наоборот (C с внутренними SIMD и скалярный x86 asm case-flip для буквенных символов ASCII, оставляя другие без изменений.)
Эти приемы в основном полезны только при ручной оптимизации некоторой обработки текста с помощью SIMD (например, SSE2 или NEON), после проверки того, что ни у одного из char в векторе не установлен старший бит. (И, таким образом, ни один из байтов не является частью многобайтовой кодировки UTF-8 для одного символа, который может иметь различные обратные символы верхнего/нижнего регистра). Если вы найдете что-либо, вы можете вернуться к скаляру для этого фрагмента из 16 байтов или для остальной части строки.
Есть даже некоторые локали, где toupper() или tolower() для некоторых символов в диапазоне ASCII производят символы вне этого диапазона, особенно турецкие, где я ↔ ı и İ ↔ 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 для каждого символа.
Это потому, что 32 представлен 0b100000, поэтому вы можете добавить или вычесть 32 (только один раз) с помощью оператора xor.
Тогда, как вы сказали, разница между a и A равна 32, и просто оказывается, что их двоичное представление изменяется только для этого бита, поэтому xor работает правильно.
Если вы хотите быть немного более педантичным и явным, вместо 32 в качестве магического числа, вы можете определить его как:
const char toLower = 'a' - 'A'; // 32
const char toHigher = 'A' - 'a'; // -32
Другие ответы очень хорошо объясняют битовые операции, но я рекомендую использовать этот вид кода для удобства чтения.