为什么是 (int)((unsigned int)((int)v)?
Why (int)((unsigned int)((int)v)?
The website in which I found this code
int v, sign;
// or, to avoid branching on CPUs with flag registers (IA32):
sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1)); // if v < 0 then -1, else 0.
此语句将变量 sign 赋给变量 v 的符号(-1 或 0)。我想知道为什么使用 (int)((unsigned int)((int)v)
而不是普通的 v?
它首先转换为 int
,然后转换为 unsigned int
,然后执行移位,然后转换回 int
,最后取反结果并将其存储在sign
。 unsigned 转换可能会影响结果,因为它会强制进行逻辑移位(这将补零),而不是算术移位(这将符号扩展)。
请注意,他们实际上想要算术移位,但我不相信 C 能保证它的可用性,这大概就是他们手动执行逻辑移位的否定的原因符号位。
请注意,您已经在问题中提取了表达式的一个片段(您引用的 (int)((unsigned int)((int)v)
左括号 (
比右括号 )
多一个)。赋值语句的RHS表达式完整为:
-(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));
如果你加几个空格,你会发现:
-(int) ( (unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1) );
^ ^ ^^ ^ ^ ^ ^
| +------------++------+ +--------------------------+ |
+----------------------------------------------------------+
也就是说,外部 (int)
转换适用于所有:
((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));
(int)
的内部转换是空洞的;它的结果立即转换为 unsigned int
。 (unsigned int)
转换确保右移定义明确。表达式作为一个整体决定最高有效位是 0 还是 1。外层 int
将结果转换回 int
,然后 -
取反,因此如果 v
为负,则表达式为 -1
;如果 v
为零或正,则表达式为 0
— 这就是评论所说的。
引用 C 标准 6.5.7p5:
The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.
作者正在撰写有关如何有效实现函数 sign(int v)
的功能,其中 returns -1
用于负数,0
用于 0 和正数。一个天真的方法是这样的:
int sign(int v) {
if (v < 0)
return -1;
else
return 0;
}
但此解决方案可能会编译为执行比较的代码,并根据比较设置的 CPU 标志进行分支。这是低效的。他提出了一个更简单直接的解决方案:
sign = -(v > 0);
但是这个计算仍然需要在 CPU 上进行比较和分支,这些 CPU 不会直接将比较结果作为布尔值产生。 CPU 带有标志寄存器的通常会在比较指令甚至大多数算术指令上设置各种标志。所以他提出了另一种基于移动符号位的解决方案,但是正如标准上面规定的那样,他不能依赖右移负值的结果。
将 v
转换为 unsigned
可消除此问题,因为右移无符号值已明确指定。假设符号位处于最高位置,这对所有现代处理器都是正确的,但 C 标准没有强制要求,将 (unsigned)v
右移一个小于其类型中位数的位会产生 1
表示负值,0
否则。取反结果应该产生负值 v
的预期值 -1
和正值 0
以及零 v
的预期值。但是表达式是无符号的,所以简单的否定将产生 UINT_MAX
或 0
,当存储到 int
或什至只是转换为 (int)
时,这反过来会导致算术溢出。在取反之前将此结果转换回 int
可以正确计算所需的结果,-1
表示负数 v
和 0
表示正数或零 v
.
算术溢出通常是良性的并且被大多数程序员广泛忽视,但现代编译器倾向于利用其未定义性来执行积极的优化,因此依赖 expected 是不明智的但在所有情况下都是无根据的行为,最好避免算术溢出。
表达式可以简化为:
sign = -(int)((unsigned)v >> (sizeof(int) * CHAR_BIT - 1));
请注意,如果右移定义为为您的平台复制位(当前 CPUs 的几乎普遍行为),表达式会简单得多(假设 int v
):
sign = v >> (sizeof(v) * CHAR_BIT - 1)); // works on x86 CPUs
bithacks 页面 https://graphics.stanford.edu/~seander/bithacks.html ,确实很有启发性,包含详细的解释:
int v; // we want to find the sign of v
int sign; // the result goes here
// CHAR_BIT is the number of bits per byte (normally 8).
sign = -(v < 0); // if v < 0 then -1, else 0.
// or, to avoid branching on CPUs with flag registers (IA32):
sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));
// or, for one less instruction (but not portable):
sign = v >> (sizeof(int) * CHAR_BIT - 1);
对于 32 位整数,上面最后一个表达式的计算结果为 sign = v >> 31。这是一种比显而易见的方法 sign = -(v < 0) 更快的操作。这个技巧之所以有效,是因为当有符号整数右移时,最左边位的值被复制到其他位。当值为负时,最左边的位为 1,否则为 0;所有 1 位给出 -1。不幸的是,这种行为是特定于体系结构的。
作为结语,我建议使用最易读版本并依靠编译器生成最高效的代码:
sign = -(v < 0);
可以在这个有启发性的页面上验证:http://gcc.godbolt.org/# 用 gcc -O3 -std=c99 -m64
编译上面的代码确实会为上面的所有解决方案生成下面的代码,即使是最天真的 if
/else
语句:
sign(int):
movl %edi, %eax
sarl , %eax
ret
The website in which I found this code
int v, sign;
// or, to avoid branching on CPUs with flag registers (IA32):
sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1)); // if v < 0 then -1, else 0.
此语句将变量 sign 赋给变量 v 的符号(-1 或 0)。我想知道为什么使用 (int)((unsigned int)((int)v)
而不是普通的 v?
它首先转换为 int
,然后转换为 unsigned int
,然后执行移位,然后转换回 int
,最后取反结果并将其存储在sign
。 unsigned 转换可能会影响结果,因为它会强制进行逻辑移位(这将补零),而不是算术移位(这将符号扩展)。
请注意,他们实际上想要算术移位,但我不相信 C 能保证它的可用性,这大概就是他们手动执行逻辑移位的否定的原因符号位。
请注意,您已经在问题中提取了表达式的一个片段(您引用的 (int)((unsigned int)((int)v)
左括号 (
比右括号 )
多一个)。赋值语句的RHS表达式完整为:
-(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));
如果你加几个空格,你会发现:
-(int) ( (unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1) );
^ ^ ^^ ^ ^ ^ ^
| +------------++------+ +--------------------------+ |
+----------------------------------------------------------+
也就是说,外部 (int)
转换适用于所有:
((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));
(int)
的内部转换是空洞的;它的结果立即转换为 unsigned int
。 (unsigned int)
转换确保右移定义明确。表达式作为一个整体决定最高有效位是 0 还是 1。外层 int
将结果转换回 int
,然后 -
取反,因此如果 v
为负,则表达式为 -1
;如果 v
为零或正,则表达式为 0
— 这就是评论所说的。
引用 C 标准 6.5.7p5:
The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.
作者正在撰写有关如何有效实现函数 sign(int v)
的功能,其中 returns -1
用于负数,0
用于 0 和正数。一个天真的方法是这样的:
int sign(int v) {
if (v < 0)
return -1;
else
return 0;
}
但此解决方案可能会编译为执行比较的代码,并根据比较设置的 CPU 标志进行分支。这是低效的。他提出了一个更简单直接的解决方案:
sign = -(v > 0);
但是这个计算仍然需要在 CPU 上进行比较和分支,这些 CPU 不会直接将比较结果作为布尔值产生。 CPU 带有标志寄存器的通常会在比较指令甚至大多数算术指令上设置各种标志。所以他提出了另一种基于移动符号位的解决方案,但是正如标准上面规定的那样,他不能依赖右移负值的结果。
将 v
转换为 unsigned
可消除此问题,因为右移无符号值已明确指定。假设符号位处于最高位置,这对所有现代处理器都是正确的,但 C 标准没有强制要求,将 (unsigned)v
右移一个小于其类型中位数的位会产生 1
表示负值,0
否则。取反结果应该产生负值 v
的预期值 -1
和正值 0
以及零 v
的预期值。但是表达式是无符号的,所以简单的否定将产生 UINT_MAX
或 0
,当存储到 int
或什至只是转换为 (int)
时,这反过来会导致算术溢出。在取反之前将此结果转换回 int
可以正确计算所需的结果,-1
表示负数 v
和 0
表示正数或零 v
.
算术溢出通常是良性的并且被大多数程序员广泛忽视,但现代编译器倾向于利用其未定义性来执行积极的优化,因此依赖 expected 是不明智的但在所有情况下都是无根据的行为,最好避免算术溢出。
表达式可以简化为:
sign = -(int)((unsigned)v >> (sizeof(int) * CHAR_BIT - 1));
请注意,如果右移定义为为您的平台复制位(当前 CPUs 的几乎普遍行为),表达式会简单得多(假设 int v
):
sign = v >> (sizeof(v) * CHAR_BIT - 1)); // works on x86 CPUs
bithacks 页面 https://graphics.stanford.edu/~seander/bithacks.html ,确实很有启发性,包含详细的解释:
int v; // we want to find the sign of v
int sign; // the result goes here
// CHAR_BIT is the number of bits per byte (normally 8).
sign = -(v < 0); // if v < 0 then -1, else 0.
// or, to avoid branching on CPUs with flag registers (IA32):
sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));
// or, for one less instruction (but not portable):
sign = v >> (sizeof(int) * CHAR_BIT - 1);
对于 32 位整数,上面最后一个表达式的计算结果为 sign = v >> 31。这是一种比显而易见的方法 sign = -(v < 0) 更快的操作。这个技巧之所以有效,是因为当有符号整数右移时,最左边位的值被复制到其他位。当值为负时,最左边的位为 1,否则为 0;所有 1 位给出 -1。不幸的是,这种行为是特定于体系结构的。
作为结语,我建议使用最易读版本并依靠编译器生成最高效的代码:
sign = -(v < 0);
可以在这个有启发性的页面上验证:http://gcc.godbolt.org/# 用 gcc -O3 -std=c99 -m64
编译上面的代码确实会为上面的所有解决方案生成下面的代码,即使是最天真的 if
/else
语句:
sign(int):
movl %edi, %eax
sarl , %eax
ret