^ = 32背后的想法是什么,将小写字母转换为高位字母,反之亦然?

问题描述 投票:145回答:10

我在解决代码问题上遇到了一些问题。通常我首先检查字符是英文字母的上部还是下部,然后减去或添加32将其转换为相应的字母。但我发现有人做^= 32做同样的事情。这里是:

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

我已经搜索了这方面的解释并没有找到答案。那么为什么会这样呢?

c++ bit-manipulation ascii
10个回答
149
投票

我们来看看二进制的ASCII码表。

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

32是0100000,这是小写和大写字母之间的唯一区别。因此,切换该位会切换字母的大小写。


7
投票

小写和大写字母范围不跨越ASCII编码系统中的%32“对齐”边界。

这就是为什么位0x20是同一个字母的大写/小写版本之间的唯一区别。

如果不是这种情况,你需要添加或减去0x20,而不仅仅是切换,对于某些字母,会有进位来翻转其他更高的位。 (并且没有一个操作可以切换,并且首先检查字母字符会更难,因为你不能| = 0x20来强制lcase。)


相关的纯ASCII技巧:您可以通过使用c |= 0x20强制小写,然后检查是否(无符号)c - 'a' <= ('z'-'a')来检查字母ASCII字符。所以只有3个操作:OR + SUB + CMP对抗常数25.当然,编译器知道如何优化(c>='a' && c<='z') into asm like this for you,所以最多你应该自己做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

另请参阅Convert a String In C++ To Upper Case(SIMD string toupper仅用于ASCII,使用该检查屏蔽XOR的操作数。)

还有How to access a char array and change lower case letters to upper case, and vice versa(带有SIMD内在函数的C,以及用于字母ASCII字符的标量x86 asm case-flip,其他未经修改的。)


在检查向量中没有任何chars具有高位设置后,如果用SIMD(例如SSE2或NEON)手动优化某些文本处理,这些技巧大多只有用。 (因此,对于单个字符,没有字节是多字节UTF-8编码的一部分,这可能具有不同的大写/小写反转)。如果你发现任何一个,你可以回退到这个16字节的块或者字符串的其余部分的标量。

甚至有一些语言环境,其中toupper()tolower()在ASCII范围内的某些字符产生该范围之外的字符,特别是土耳其语我和↔↔i。在这些区域设置中,您需要更复杂的检查,或者可能根本不尝试使用此优化。


但在某些情况下,您可以使用ASCII而不是UTF-8,例如使用LANG=C(POSIX语言环境)的Unix实用程序,而不是en_CA.UTF-8或其他任何东西。

但是如果你能证明它是安全的,你可以比在一个循环中调用toupper(比如5x)和toupper()快得多last I tested with Boost 1.58中等长度的字符串,比boost::to_upper_copy<char*, std::string>()快得多,dynamic_cast为每个角色做一个愚蠢的qazxswpoi。


116
投票

这使用了真实聪明人选择的ASCII值。

foo ^= 32;

这是flips the 6th lowest bitfoo1(ASCII类的大写标志),将ASCII大写字母转换为小写字母,反之亦然。

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

Example

'A' ^ 32

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

并且由XOR,'a' ^ 32 == 'A'的财产。

注意

C ++不需要使用ASCII来表示字符。另一个变种是EBCDIC。此技巧仅适用于ASCII平台。一个更便携的解决方案是使用std::tolowerstd::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开始计数)。


35
投票

请允许我说这是 - 虽然它看起来很聪明 - 真的,非常愚蠢的黑客。如果有人在2019年向你推荐这个,打他。尽可能地打他。 当然,如果你知道除了英语之外你永远不会使用任何语言,你可以在你自己的软件中使用你自己的软件。否则,不去。

大约在30-35年前,当计算机并没有真正做很多但是英语用ASCII,可能是一两种主要的欧洲语言时,黑客可以说是“好”。但是......不再如此。

黑客攻击是有效的,因为美国 - 拉丁文的上层和下层区域恰好是0x20彼此分开,并且以相同的顺序出现,这只是一点点差异。事实上,这有点黑客,切换。

现在,为西欧和后来的Unicode联盟创建代码页的人们足够聪明,可以将此方案用于例如德国变音符号和法语重音元音。对于ß来说并非如此(直到有人在2017年说服了Unicode联盟,以及大型假新闻印刷杂志上写过这篇文章,实际上说服Duden - 没有评论)甚至不存在作为一个版本(转换为SS) 。现在它确实存在作为versal,但这两个是0x1DBF位置分开,而不是0x20

然而,实施者却没有考虑到这一点。例如,如果你用一些东欧语言或类似的方式应用你的黑客(我不会知道西里尔语),你会得到一个令人讨厌的惊喜。所有这些“斧头”字符都是其中的例子,小写和大写是相互分开的。因此黑客在那里不能正常工作。

还有更多要考虑的事情,例如,一些字符根本不会简单地从低级变换为大写(它们被不同的序列替换),或者它们可能会改变形式(需要不同的代码点)。

甚至不要考虑这个黑客会对泰国人或中国人做些什么(它只是给你完全无稽之谈)。

30年前节省了几百个CPU周期可能非常值得,但是现在,没有理由正确地转换字符串。有用于执行这个非平凡任务的库函数。 现在正确地转换几十千字节文本所花费的时间可以忽略不计。


33
投票

这是有效的,因为在发生这种情况时,ASCII和派生编码中'a'和A'之间的差异是32,而32也是第六位的值。使用异或将第6位翻转,从而在上下之间进行转换。


22
投票

很可能您的字符集实现将是ASCII。如果我们看一下表:

enter image description here

我们看到,在小写和大写数字的值之间存在完全不同的32。因此,如果我们执行^= 32(相当于切换第6个最低有效位),它会在小写和大写字符之间切换。

请注意,它适用于所有符号,而不仅仅是字母。它使用第6位不同的相应字符切换字符,从而产生一对在其间来回切换的字符。对于字母,相应的大写/小写字符形成这样的一对。一个NUL将变成Space,反之亦然,而@则用反击来切换。基本上,此图表第一列中的任何字符都会切换一列的字符,同样适用于第三列和第四列。

我不会使用这个hack,因为不能保证它可以在任何系统上运行。只需使用touppertolower,以及isupper之类的查询。


15
投票

这里有很多好的答案描述了它是如何工作的,但是为什么它以这种方式工作就是提高性能。按位运算比处理器内的大多数其他运算更快。您可以快速进行不区分大小写的比较,只需不查看确定大小写的位或通过翻转位来将大小写更改为大/小(那些设计ASCII表的人非常聪明)。

显然,由于更快的处理器和Unicode,这在1960年(当时的工作首次开始使用ASCII)时,并不像今天的交易那么大,但仍然有一些低成本的处理器,这可能会产生显着的差异只要你能保证只有ASCII字符。

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

在简单的低成本处理器上,通常,按位运算比除法快得多,比乘法快几倍,有时比加法快得多。

注意:出于多种原因(可读性,正确性,可移植性等),我建议使用标准库来处理字符串。如果您已经测量了性能,那么只能使用位翻转,这是您的瓶颈。


14
投票

这就是ASCII的工作原理,就是这样。

但是在利用它时,你放弃了可移植性,因为C ++不坚持使用ASCII作为编码。

这就是为什么函数std::toupperstd::tolower在C ++标准库中实现的 - 你应该使用它们。


11
投票

请参阅http://www.catb.org/esr/faqs/things-every-hacker-once-knew/#_ascii的第二张表,以及下面的说明,转载如下:

键盘上的Control修饰符基本上清除了您键入的任何字符的前三位,保留底部五位并将其映射到0..31范围。所以,例如,Ctrl-SPACE,Ctrl- @和Ctrl-`都意味着同样的事情:NUL。

很老的键盘用来做切换只需切换32或16位,具体取决于键;这就是为什么ASCII中的小写和大写字母之间的关系是如此规则的原因,如果你眯着眼睛,数字和符号之间的关系,以及一些符号对之间的关​​系是有规律的。 ASR-33是一个全大写的终端,甚至可以通过移动16位来生成一些没有键的标点符号;因此,例如,Shift-K(0x4B)变为[(0x5B)

ASCII的设计使得shift和ctrl键盘键可以在没有太多(或者可能是任何ctrl)逻辑的情况下实现 - 移位可能只需要几个门。它可能至少与任何其他字符编码存储有线协议一样有意义(不需要软件转换)。

链接的文章还解释了许多奇怪的黑客惯例,如And control H does a single character and is an old^H^H^H^H^H classic joke.found here)。


8
投票

Xoring 32(二进制00100000)设置或重置第六位(从右侧)。这相当于添加或减去32。

© www.soinside.com 2019 - 2024. All rights reserved.