按位运算符在 StringBuilder 中的优势
Bitwise operator advantages in StringBuilder
为什么StringBuffer/StringBuilder类中的reverse()方法使用位运算符？
我想知道它的优点。
public AbstractStringBuilder reverse() {
boolean hasSurrogate = false;
int n = count - 1;
for (int j = (n-1) >> 1; j >= 0; --j) {
char temp = value[j];
char temp2 = value[n - j];
if (!hasSurrogate) {
hasSurrogate = (temp >= Character.MIN_SURROGATE && temp <= Character.MAX_SURROGATE)
|| (temp2 >= Character.MIN_SURROGATE && temp2 <= Character.MAX_SURROGATE);
}
value[j] = temp2;
value[n - j] = temp;
}
if (hasSurrogate) {
// Reverse back all valid surrogate pairs
for (int i = 0; i < count - 1; i++) {
char c2 = value[i];
if (Character.isLowSurrogate(c2)) {
char c1 = value[i + 1];
if (Character.isHighSurrogate(c1)) {
value[i++] = c1;
value[i] = c2;
}
}
}
}
return this;
}
它使用(n-1) >> 1而不是(n-1)/2来找到要反转的内部数组的中间索引。位移运算符通常比除法运算符更有效。
右移一位意味着除以二，我认为您不会注意到任何性能差异，编译器将在编译时执行这些优化。
许多程序员习惯在除法而不是写 / 2 时右移两位，这是一种风格问题，或者也许有一天，右移而不是实际除法 / 2 确实更有效=13=]，（优化之前）。编译器知道如何优化这样的东西，我不会浪费时间尝试编写其他程序员可能不清楚的东西（除非它们真的有所作为）。不管怎样，循环相当于：
int n = count - 1;
for (int j = (n-1) / 2; j >= 0; --j)
正如@MarkoTopolnik 在他的评论中提到的，JDK 是在完全没有考虑任何优化的情况下编写的，这可以解释为什么他们明确地将数字右移一个而不是明确地除以它，如果他们考虑最大值优化的力量，他们可能会写 / 2.
以防万一你想知道为什么它们是等价的，最好的解释是举例，考虑数字 32。假设 8 位，它的二进制表示是：
00100000
右移一位：
00010000
其值为 16 (1 * 24)
在这个方法中，只有这个表达式：(n-1) >> 1。我假设这是你所指的表达。这叫做对shift/shifting。它等同于 (n-1)/2 但它通常被认为更快、更高效。它也经常用于许多其他语言（例如 C/C++）。
请注意，即使您使用像 (n-1)/2 这样的除法，现代编译器仍会优化您的代码。所以使用右移没有明显的好处。这更像是编码偏好、风格和习惯的问题。
另请参阅：
Is shifting bits faster than multiplying and dividing in Java? .NET?
总结：
- Java 中的
>> 运算符称为 符号扩展右移 运算符。
对于 X 的所有严格正值，X >> 1 在数学上等同于 X / 2。X >> 1 总是比 X / 2 快，比率大约为 1:16，尽管差异 可能 由于现代处理器架构，在实际基准测试中的意义要小得多。- 所有主流的JVM都可以正确的进行这样的优化，但是在这些优化真正发生之前，未优化的字节码会以解释模式执行上千次。
- JRE 源代码使用了很多 优化习语，因为它们对在解释模式下执行的代码产生重要影响（最重要的是，在 JVM 启动时）。
- 系统地使用被整个开发团队接受的被证明有效的代码优化习语并不是过早的优化。
长答案
以下讨论试图正确解决本页其他评论中提出的所有问题和疑惑。之所以这么长，是因为我觉得有必要强调 为什么 某些方法更好，而不是炫耀个人基准测试结果、信念和实践，其中 millage 可能与一个有很大差异下一个人。
那么让我们一次回答一个问题。
1. Java中的X >> 1（或X << 1，或X >>> 1）是什么意思？
>>、<< 和 >>> 统称为 Bit Shift 运算符。 >> 通常称为 符号扩展右移 或 算术右移 。 >>>是非符号扩展右移（也称为逻辑右移），<<只是左位移位（符号扩展不适用于该方向，因此不需要逻辑和算术 个变体）。
Bit Shift 运算符在许多编程语言中都可用（尽管符号不同）（实际上，从我的快速调查来看，几乎每一种语言都或多或少是后代C 语言，加上其他一些）。位移位是基本的二进制操作，因此，几乎每个曾经创建的 CPU 都为这些操作提供了汇编指令。 位移位器 也是电子设计中的经典构建块，在给定合理数量的晶体管的情况下，它可以一步提供其最终结果，并具有恒定且可预测的稳定周期时间。
具体来说，位移位运算符通过移动其所有位n[=165]来转换数字=] 位置，左边或右边。 掉落的位被遗忘； "comes in" 的位被强制为 0，除了 符号扩展右移 的情况，其中最左边的位保留其值（因此保留其符号） .请参阅 Wikipedia 以获取一些图形。
2。 X >> 1是否等于X / 2？
可以，只要保证分红为正即可。
更一般地说：
- 左移
N相当于乘2<sup>N</sup>;
- 逻辑右移
N相当于无符号整数除法除以2<sup>N</sup> ;
- 算术右移
N相当于非整数除以2<sup>N</sup>，向负无穷大舍入为整数（这也相当于 有符号整数除法 除以 2<sup>N</sup> 对于任何严格的正整数）。
3。在 CPU 级别，位移 是否比等效的算术运算更快？
是的，是的。
首先，我们可以很容易地断言，在 CPU 的水平上，移位确实比等效的算术运算需要更少的 work。对于乘法和除法都是如此，其原因很简单：整数乘法和整数除法电路本身都包含 几个 位移位器。换句话说：位移单元仅代表乘法或除法单元复杂程度的一小部分。因此可以保证执行简单的位移而不是完整的算术运算需要更少的能量。然而，最终，除非您监控 CPU 的耗电量或散热情况，否则我怀疑您是否会注意到 CPU 正在消耗更多能量这一事实。
现在，让我们谈谈速度。在具有相当简单架构的处理器上（大致上，在奔腾或 PowerPC 之前设计的任何处理器，加上不具有某种形式的执行管道的最新处理器），整数除法（和乘法，在较小程度上）通常被实现通过迭代其中一个操作数上的位（实际上是位组，称为基数）。每次迭代需要一个 CPU 周期，这意味着 32 位处理器上的整数除法最多需要（）16 个周期（假设 Radix 2 SRT 除法单元，在假设的处理器上）。乘法单元通常一次处理更多位，因此 32 位处理器可能在 4 到 8 个周期内完成整数乘法。这些单元可能使用某种形式的可变位移位器来快速跳过连续零序列，因此在乘以或除以 简单 操作数（例如二的正幂）时可能会快速终止；在那种情况下，算术运算将在更少的周期内完成，但仍然需要比简单的位移操作更多的操作。
显然，指令时序因处理器设计而异，但先行比（位移 = 1，乘法 = 4，除法 = 16）是这些指令实际性能的合理近似值。作为参考，在 Intel 486 上，SHR、IMUL 和 IDIV 指令（对于 32 位，假设寄存器为常量）分别需要 2、13-42 和 43 个周期（参见 here 的 486 条指令列表他们的时机）。
现代计算机中的 CPU 又如何呢？这些处理器是围绕允许同时执行多条指令的流水线架构设计的；结果是现在大多数指令只需要 专用 时间的一个周期。但这是一种误导，因为指令在被释放之前实际上会在流水线中保留几个周期，在此期间它们可能会阻止其他指令完成。整数乘法或除法单元在此期间保持 "reserved"，因此任何进一步的除法都将被阻止。这在短循环中尤其是一个问题，其中单个乘法或除法最终会因先前尚未完成的自身调用而停止。位移指令不会遭受这种风险：大多数 "complex" 处理器可以访问多个位移单元，并且不需要将它们保留很长时间（尽管由于流水线架构固有的原因通常至少需要 2 个周期).实际上，将其转化为数字，快速查看 Atom 的 Intel Optimization Reference Manual 似乎表明 SHR、IMUL 和 IDIV（与上述相同的参数）分别具有 2、5 和 57 个延迟周期；对于 64 位操作数，它是 8、14 和 197 个周期。类似的延迟适用于最新的英特尔处理器。
所以，是的，位移比等效的算术运算更快，即使在某些情况下，在现代处理器上，它实际上可能完全没有区别。但在大多数情况下，它是非常重要的。
4. Java 虚拟机会为我执行这样的优化吗？
当然可以。好吧……当然，而且……最终。
与大多数语言编译器不同，常规 Java 编译器不执行优化。人们认为 Java 虚拟机处于决定如何针对特定执行上下文优化程序的最佳位置。这确实在实践中提供了良好的结果。 JIT 编译器对代码的动态有非常深刻的理解，并利用这些知识 select 并应用大量次要代码转换，以生成非常高效的本机代码。
但是将字节码编译成优化的本地方法需要大量的时间和内存。这就是为什么 JVM 甚至不会考虑在执行数千次之前优化代码块。然后，即使代码块已安排优化，编译器线程实际处理该方法之前可能需要很长时间。稍后，各种情况可能会导致优化的代码块被丢弃，恢复为字节代码解释。
尽管 JSE API 的设计具有 objective 可由各种供应商实施的特点，但声称 JRE 也是如此的说法是不正确的。 Oracle JRE作为参考实现提供给其他人，但不鼓励将其与其他JVM一起使用（实际上，不久前，在Oracle开源JRE的源代码之前，它是被禁止的）。
JRE 源代码中的优化是 JRE 开发人员采用约定和优化努力的结果，即使在 JIT 优化尚未或根本无济于事的情况下也能提供合理的性能。例如，在调用 main 方法之前加载了数百个 类。那时，JIT 编译器还没有获得足够的信息来正确优化代码。在这种时候，手工优化会产生重要的影响。
5.这不是过早的优化吗？
是的，除非有原因。
现代生活的一个事实是，每当一个程序员在某处展示代码优化时，另一个程序员就会反对 Donald Knuth 关于优化的引用（好吧，是他的吗？谁知道...）甚至很多人都认为作为 Knuth 的明确断言，我们永远不应该尝试优化代码。不幸的是，这是对 Knuth 在过去几十年中对计算机科学的重要贡献的主要误解：Knuth 实际上撰写了数千页关于 实用 代码优化的文字。
正如 Knuth 所说：
Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.
— Donald E. Knuth, "Structured Programming with Goto Statements"
Knuth 认为过早优化的是需要大量思考的优化 and 仅适用于程序的非关键部分，and对调试和维护有很强的负面影响。现在，所有这些都可以争论很长时间，但我们不要。
然而，应该理解的是，已被证明有效（即至少在总体上平均而言）不会对程序的整体构造产生负面影响的小型局部优化，不会降低代码的可维护性，不需要多余的思考根本不是坏事。这样的优化其实是好的，因为它不花你的钱，我们不应该错过这样的机会。
然而，最重要的是要记住，在某种情况下对程序员来说 微不足道 的优化可能会变得 难以理解 给另一个上下文中的程序员。出于这个原因，位移位和屏蔽习惯用法尤其成问题。知道这个习语的程序员可以不加思考地阅读和使用它，并且这些优化的有效性已得到证明，尽管通常微不足道，除非代码包含数百次出现。这些习语很少是错误的实际来源。尽管如此，不熟悉特定习惯用法的程序员仍然会浪费时间来理解该特定代码片段的作用、原因和方式。
最后，是否赞成这种优化，以及究竟应该使用 哪个 成语实际上是团队决策和代码上下文的问题。我个人认为一定数量的习语在所有情况下都是最佳实践，任何加入我团队的新程序员都会很快掌握这些习语。更多的习语保留给关键代码路径。放入内部共享代码库的所有代码都被视为关键代码路径，因为它们可能会被证明是从这样的关键代码路径调用的。无论如何，这是我个人的做法，您的经验可能会有所不同。
为什么StringBuffer/StringBuilder类中的reverse()方法使用位运算符？
我想知道它的优点。
public AbstractStringBuilder reverse() {
boolean hasSurrogate = false;
int n = count - 1;
for (int j = (n-1) >> 1; j >= 0; --j) {
char temp = value[j];
char temp2 = value[n - j];
if (!hasSurrogate) {
hasSurrogate = (temp >= Character.MIN_SURROGATE && temp <= Character.MAX_SURROGATE)
|| (temp2 >= Character.MIN_SURROGATE && temp2 <= Character.MAX_SURROGATE);
}
value[j] = temp2;
value[n - j] = temp;
}
if (hasSurrogate) {
// Reverse back all valid surrogate pairs
for (int i = 0; i < count - 1; i++) {
char c2 = value[i];
if (Character.isLowSurrogate(c2)) {
char c1 = value[i + 1];
if (Character.isHighSurrogate(c1)) {
value[i++] = c1;
value[i] = c2;
}
}
}
}
return this;
}
它使用(n-1) >> 1而不是(n-1)/2来找到要反转的内部数组的中间索引。位移运算符通常比除法运算符更有效。
右移一位意味着除以二，我认为您不会注意到任何性能差异，编译器将在编译时执行这些优化。
许多程序员习惯在除法而不是写 / 2 时右移两位，这是一种风格问题，或者也许有一天，右移而不是实际除法 / 2 确实更有效=13=]，（优化之前）。编译器知道如何优化这样的东西，我不会浪费时间尝试编写其他程序员可能不清楚的东西（除非它们真的有所作为）。不管怎样，循环相当于：
int n = count - 1;
for (int j = (n-1) / 2; j >= 0; --j)
正如@MarkoTopolnik 在他的评论中提到的，JDK 是在完全没有考虑任何优化的情况下编写的，这可以解释为什么他们明确地将数字右移一个而不是明确地除以它，如果他们考虑最大值优化的力量，他们可能会写 / 2.
以防万一你想知道为什么它们是等价的，最好的解释是举例，考虑数字 32。假设 8 位，它的二进制表示是：
00100000
右移一位：
00010000
其值为 16 (1 * 24)
在这个方法中，只有这个表达式：(n-1) >> 1。我假设这是你所指的表达。这叫做对shift/shifting。它等同于 (n-1)/2 但它通常被认为更快、更高效。它也经常用于许多其他语言（例如 C/C++）。
请注意，即使您使用像 (n-1)/2 这样的除法，现代编译器仍会优化您的代码。所以使用右移没有明显的好处。这更像是编码偏好、风格和习惯的问题。
另请参阅：
Is shifting bits faster than multiplying and dividing in Java? .NET?
总结：
- Java 中的
>>运算符称为 符号扩展右移 运算符。
对于 X 的所有严格正值， X >> 1在数学上等同于X / 2。X >> 1总是比X / 2快，比率大约为 1:16，尽管差异 可能 由于现代处理器架构，在实际基准测试中的意义要小得多。- 所有主流的JVM都可以正确的进行这样的优化，但是在这些优化真正发生之前，未优化的字节码会以解释模式执行上千次。
- JRE 源代码使用了很多 优化习语，因为它们对在解释模式下执行的代码产生重要影响（最重要的是，在 JVM 启动时）。
- 系统地使用被整个开发团队接受的被证明有效的代码优化习语并不是过早的优化。
长答案
以下讨论试图正确解决本页其他评论中提出的所有问题和疑惑。之所以这么长，是因为我觉得有必要强调 为什么 某些方法更好，而不是炫耀个人基准测试结果、信念和实践，其中 millage 可能与一个有很大差异下一个人。
那么让我们一次回答一个问题。
1. Java中的X >> 1（或X << 1，或X >>> 1）是什么意思？
>>、<< 和 >>> 统称为 Bit Shift 运算符。 >> 通常称为 符号扩展右移 或 算术右移 。 >>>是非符号扩展右移（也称为逻辑右移），<<只是左位移位（符号扩展不适用于该方向，因此不需要逻辑和算术 个变体）。
Bit Shift 运算符在许多编程语言中都可用（尽管符号不同）（实际上，从我的快速调查来看，几乎每一种语言都或多或少是后代C 语言，加上其他一些）。位移位是基本的二进制操作，因此，几乎每个曾经创建的 CPU 都为这些操作提供了汇编指令。 位移位器 也是电子设计中的经典构建块，在给定合理数量的晶体管的情况下，它可以一步提供其最终结果，并具有恒定且可预测的稳定周期时间。
具体来说，位移位运算符通过移动其所有位n[=165]来转换数字=] 位置，左边或右边。 掉落的位被遗忘； "comes in" 的位被强制为 0，除了 符号扩展右移 的情况，其中最左边的位保留其值（因此保留其符号） .请参阅 Wikipedia 以获取一些图形。
2。 X >> 1是否等于X / 2？
可以，只要保证分红为正即可。
更一般地说：
- 左移
N相当于乘2<sup>N</sup>; - 逻辑右移
N相当于无符号整数除法除以2<sup>N</sup>; - 算术右移
N相当于非整数除以2<sup>N</sup>，向负无穷大舍入为整数（这也相当于 有符号整数除法 除以2<sup>N</sup>对于任何严格的正整数）。
3。在 CPU 级别，位移 是否比等效的算术运算更快？
是的，是的。
首先，我们可以很容易地断言，在 CPU 的水平上，移位确实比等效的算术运算需要更少的 work。对于乘法和除法都是如此，其原因很简单：整数乘法和整数除法电路本身都包含 几个 位移位器。换句话说：位移单元仅代表乘法或除法单元复杂程度的一小部分。因此可以保证执行简单的位移而不是完整的算术运算需要更少的能量。然而，最终，除非您监控 CPU 的耗电量或散热情况，否则我怀疑您是否会注意到 CPU 正在消耗更多能量这一事实。
现在，让我们谈谈速度。在具有相当简单架构的处理器上（大致上，在奔腾或 PowerPC 之前设计的任何处理器，加上不具有某种形式的执行管道的最新处理器），整数除法（和乘法，在较小程度上）通常被实现通过迭代其中一个操作数上的位（实际上是位组，称为基数）。每次迭代需要一个 CPU 周期，这意味着 32 位处理器上的整数除法最多需要（）16 个周期（假设 Radix 2 SRT 除法单元，在假设的处理器上）。乘法单元通常一次处理更多位，因此 32 位处理器可能在 4 到 8 个周期内完成整数乘法。这些单元可能使用某种形式的可变位移位器来快速跳过连续零序列，因此在乘以或除以 简单 操作数（例如二的正幂）时可能会快速终止；在那种情况下，算术运算将在更少的周期内完成，但仍然需要比简单的位移操作更多的操作。
显然，指令时序因处理器设计而异，但先行比（位移 = 1，乘法 = 4，除法 = 16）是这些指令实际性能的合理近似值。作为参考，在 Intel 486 上，SHR、IMUL 和 IDIV 指令（对于 32 位，假设寄存器为常量）分别需要 2、13-42 和 43 个周期（参见 here 的 486 条指令列表他们的时机）。
现代计算机中的 CPU 又如何呢？这些处理器是围绕允许同时执行多条指令的流水线架构设计的；结果是现在大多数指令只需要 专用 时间的一个周期。但这是一种误导，因为指令在被释放之前实际上会在流水线中保留几个周期，在此期间它们可能会阻止其他指令完成。整数乘法或除法单元在此期间保持 "reserved"，因此任何进一步的除法都将被阻止。这在短循环中尤其是一个问题，其中单个乘法或除法最终会因先前尚未完成的自身调用而停止。位移指令不会遭受这种风险：大多数 "complex" 处理器可以访问多个位移单元，并且不需要将它们保留很长时间（尽管由于流水线架构固有的原因通常至少需要 2 个周期).实际上，将其转化为数字，快速查看 Atom 的 Intel Optimization Reference Manual 似乎表明 SHR、IMUL 和 IDIV（与上述相同的参数）分别具有 2、5 和 57 个延迟周期；对于 64 位操作数，它是 8、14 和 197 个周期。类似的延迟适用于最新的英特尔处理器。
所以，是的，位移比等效的算术运算更快，即使在某些情况下，在现代处理器上，它实际上可能完全没有区别。但在大多数情况下，它是非常重要的。
4. Java 虚拟机会为我执行这样的优化吗？
当然可以。好吧……当然，而且……最终。
与大多数语言编译器不同，常规 Java 编译器不执行优化。人们认为 Java 虚拟机处于决定如何针对特定执行上下文优化程序的最佳位置。这确实在实践中提供了良好的结果。 JIT 编译器对代码的动态有非常深刻的理解，并利用这些知识 select 并应用大量次要代码转换，以生成非常高效的本机代码。
但是将字节码编译成优化的本地方法需要大量的时间和内存。这就是为什么 JVM 甚至不会考虑在执行数千次之前优化代码块。然后，即使代码块已安排优化，编译器线程实际处理该方法之前可能需要很长时间。稍后，各种情况可能会导致优化的代码块被丢弃，恢复为字节代码解释。
尽管 JSE API 的设计具有 objective 可由各种供应商实施的特点，但声称 JRE 也是如此的说法是不正确的。 Oracle JRE作为参考实现提供给其他人，但不鼓励将其与其他JVM一起使用（实际上，不久前，在Oracle开源JRE的源代码之前，它是被禁止的）。
JRE 源代码中的优化是 JRE 开发人员采用约定和优化努力的结果，即使在 JIT 优化尚未或根本无济于事的情况下也能提供合理的性能。例如，在调用 main 方法之前加载了数百个 类。那时，JIT 编译器还没有获得足够的信息来正确优化代码。在这种时候，手工优化会产生重要的影响。
5.这不是过早的优化吗？
是的，除非有原因。
现代生活的一个事实是，每当一个程序员在某处展示代码优化时，另一个程序员就会反对 Donald Knuth 关于优化的引用（好吧，是他的吗？谁知道...）甚至很多人都认为作为 Knuth 的明确断言，我们永远不应该尝试优化代码。不幸的是，这是对 Knuth 在过去几十年中对计算机科学的重要贡献的主要误解：Knuth 实际上撰写了数千页关于 实用 代码优化的文字。
正如 Knuth 所说：
Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.
— Donald E. Knuth, "Structured Programming with Goto Statements"
Knuth 认为过早优化的是需要大量思考的优化 and 仅适用于程序的非关键部分，and对调试和维护有很强的负面影响。现在，所有这些都可以争论很长时间，但我们不要。
然而，应该理解的是，已被证明有效（即至少在总体上平均而言）不会对程序的整体构造产生负面影响的小型局部优化，不会降低代码的可维护性，不需要多余的思考根本不是坏事。这样的优化其实是好的，因为它不花你的钱，我们不应该错过这样的机会。
然而，最重要的是要记住，在某种情况下对程序员来说 微不足道 的优化可能会变得 难以理解 给另一个上下文中的程序员。出于这个原因，位移位和屏蔽习惯用法尤其成问题。知道这个习语的程序员可以不加思考地阅读和使用它，并且这些优化的有效性已得到证明，尽管通常微不足道，除非代码包含数百次出现。这些习语很少是错误的实际来源。尽管如此，不熟悉特定习惯用法的程序员仍然会浪费时间来理解该特定代码片段的作用、原因和方式。
最后，是否赞成这种优化，以及究竟应该使用 哪个 成语实际上是团队决策和代码上下文的问题。我个人认为一定数量的习语在所有情况下都是最佳实践，任何加入我团队的新程序员都会很快掌握这些习语。更多的习语保留给关键代码路径。放入内部共享代码库的所有代码都被视为关键代码路径，因为它们可能会被证明是从这样的关键代码路径调用的。无论如何，这是我个人的做法，您的经验可能会有所不同。