n是负数、正数还是零？返回1、2或4。

Question

n是负数、正数还是零？返回1、2或4。

35

我正在构建一个PowerPC解释器，它工作得非常好。在Power架构中，条件寄存器CR0（在x86上的EFLAGS）在几乎所有指令中都会更新。它的设置方式如下：如果上次操作结果为负，则CR0的值为1；如果上次操作结果为正，则其值为2；否则为4。

我最初的天真方法是：

if (n < 0)
    cr0 = 1
else if (n > 0)
    cr0 = 2;
else
    cr0 = 4;

我知道所有这些分支都不会是最优的，因为它们每秒运行数百万次。我在SO上看到了一些位操作，但其中没有一个似乎是合适的。例如，我发现许多示例可以根据符号或0将数字转换为-1、0或1。但如何使-1 = 1，1 = 2，0 = 4呢？我请求位操作专家的帮助......

提前感谢

更新: 首先：谢谢各位，你们太棒了。我会仔细测试你们的代码以获得速度，并且你们会成为第一个知道谁获胜的人。

@jalf:关于你的第一个建议，我实际上并没有在每个指令上计算CR0。我相反是保留了一个lastResult变量，当（如果）随后的指令要求标志时，进行比较。有三个主要动机使我回到“每次”更新：

在PPC上，你不像在x86上那样被迫像ADD一样更改EFLAGS，即使不需要，你有两种ADD的口味，一种是更新的。如果编译器选择使用更新的一种，这意味着它在某个点上将使用CR0，所以没有延迟的意义......
有一个特别痛苦的指令叫做mtcrf，它可以任意更改CR0。你甚至可以将其设置为7，并且没有算术含义...这只是破坏了保留“lastResult”变量的可能性。

- Francesco Boffa

6

你怎么知道比特操作会更快？ - Pubby

24

作为译者的我提醒回答者，您能否尽量不要回答“别问这个问题”的内容。我们可以假设提问者对于自己实现代码感到好奇，而非依赖编译器；或者由于某种原因，已经试过并检查过编译器生成的代码，发现其运行速度太慢。如果以上两点都无法满足，请给出更好的理由来避免只是简单地说“你应该闭上眼睛，相信编译器，并希望一切都会好起来”的建议。 - jalf

2

你的解释器运行在哪个CPU上？如果你想要一个接近最佳解决方案的话，了解指令集可能是必要的。 - jalf

+1. 很好的问题，有很多有趣的答案。你能尝试所有的方法并发布一些基准测试结果吗？ - André Caron

1

请注意，即使他这样做了，基准测试也不一定会告诉您任何东西。您的编译器、CPU甚至操作系统可能会导致不同的结果。 - jalf

相关内容：无分支代码将零、负数和正数映射为0、1、2 - phuclv

8个回答

20

通常有很多近似于“不”的答案，:) 你想了解一下二进制技巧？那么你将得到它。然后随意使用或不使用，你自行决定。

您可以使用这个映射为-1、0和1 (sign)，然后执行以下操作:

return 7 & (0x241 >> ((sign(x) + 1) * 4));

这本质上使用了一个小查找表。

或者使用“朴素的位操作技巧”：

int y = ((x >> 31) & 1) | ((-x >> 31) & 2)
return (~(-y >> 31) & 4) | y;

第一行将x < 0映射为1，将x > 0映射为2，将x == 0映射为0。第二行将y == 0映射为4，将y != 0映射为y。

当然，它还有一个棘手的边界情况，即x = 0x80000000被映射为3。糟糕。好吧，让我们修复一下:

int y = ((x >> 31) & 1) | ((-x >> 31) & 2)
y &= 1 | ~(y << 1);  // remove the 2 if odd
return (~(-y >> 31) & 4) | y;

- harold

3

请编写一些单元测试。之后，检查你的 sign(x) 实现，确保它没有任何分支。使用性能分析器来确保这实际上更快。 - Ben Voigt

2

最终版本在添加缺失的分号后可以工作，但速度非常非常慢。 - Ben Voigt

@BenVoigt 我认为是的，如果我数对了的话，它有一个长度为13的依赖链，而第一个也不应该很快。 - harold

有趣。我没想到这会是最快的，但也不是“非常慢”。这只是表明，在优化时做出假设是多么危险。 :) - jalf

@harold：如果您不小心提前提交了答案，您可以立即删除它，在删除时进行编辑，并在完成后取消删除。否则，人们将浪费时间考虑和评论您的帖子。 - Sven Marnach

显示剩余4条评论

6

以下表达式略微晦涩，但并不过于复杂，看起来编译器可以轻松优化它：

cr0 = 4 >> ((2 * (n < 0)) + (n > 0));

以下是使用-O2参数编译x86目标时，GCC 4.6.1生成的代码：

xor ecx, ecx
mov eax, edx
sar eax, 31
and eax, 2
test    edx, edx
setg    cl
add ecx, eax
mov eax, 4
sar eax, cl

使用 /Ox 编译选项的 VC 2010 看起来非常相似:

xor ecx, ecx
test eax, eax
sets cl
xor edx, edx
test eax, eax
setg dl
mov eax, 4
lea ecx, DWORD PTR [edx+ecx*2]
sar eax, cl

使用if测试版本，这两个编译器都会生成使用跳转的汇编代码。当然，除非你实际检查输出，否则永远不会确定任何特定编译器对你选择的任何特定代码将要执行什么。我的表达方式足够晦涩，以至于除非它真的是一个性能关键的代码片段，否则我可能仍然会选择if语句版本。由于需要频繁设置CR0寄存器，所以我认为测量一下这个表达式是否有帮助可能是值得的。

- Michael Burr

4

不进行优化的gcc

        movl    %eax, 24(%esp)  ; eax has result of reading n
        cmpl    $0, 24(%esp)
        jns     .L2
        movl    $1, 28(%esp)
        jmp     .L3
.L2:
        cmpl    $0, 24(%esp)
        jle     .L4
        movl    $2, 28(%esp)
        jmp     .L3
.L4:
        movl    $4, 28(%esp)
.L3:

使用 -O2：

        movl    $1, %edx       ; edx = 1
        cmpl    $0, %eax
        jl      .L2            ; n < 0
        cmpl    $1, %eax       ; n < 1
        sbbl    %edx, %edx     ; edx = 0 or -1
        andl    $2, %edx       ; now 0 or 2
        addl    $2, %edx       ; now 2 or 4
.L2:
        movl    %edx, 4(%esp)

我认为你不太可能做得更好。

- stark

5

首先，实际发布反汇编真的很好。这绝对是在尝试进行此级别的优化时唯一明智的起点。但其次，GCC代码中有一个分支，我怀疑你可以通过消除它来加速处理速度。毕竟，问题不仅在于指令数量，还包括CPU执行它们的方式。 :) - jalf

1

速度上的限制取决于内存操作次数。优化后的版本除了读取指令外，唯一的内存操作是一次堆栈存储。 - stark

2

不仅仅是内存操作次数。有很多因素在起作用。你说得对，内存操作往往占主导地位，但在它们不存在的情况下，其他因素也可能很重要。我的直觉是无分支实现会更快（而且指令数量大致相同，如果不是更少），但显然需要进行测试。我不知道GCC的代码是否更快。 - jalf

@jalf 我尝试编译你的代码。即使在 -O3 下，gcc 也不能很好地减少操作次数，所以最终结果是17条指令，没有分支，只有一个存储。 - stark

很好奇。其他人报告说我的答案有9条指令（我自己还没有尝试编译和反汇编它）。 - jalf

4

我正在处理这个问题时，我的电脑崩溃了。

int cr0 = (-(n | n-1) >> 31) & 6;
cr0 |= (n >> 31) & 5;
cr0 ^= 4;

以下是生成的汇编代码（适用于Intel x86）：

PUBLIC  ?tricky@@YAHH@Z                                 ; tricky
; Function compile flags: /Ogtpy
_TEXT   SEGMENT
_n$ = 8                                                 ; size = 4
?tricky@@YAHH@Z PROC                                    ; tricky
; Line 18
        mov     ecx, DWORD PTR _n$[esp-4]
        lea     eax, DWORD PTR [ecx-1]
        or      eax, ecx
        neg     eax
        sar     eax, 31                                 ; 0000001fH
; Line 19
        sar     ecx, 31                                 ; 0000001fH
        and     eax, 6
        and     ecx, 5
        or      eax, ecx
; Line 20
        xor     eax, 4
; Line 22
        ret     0
?tricky@@YAHH@Z ENDP                                    ; tricky

还有一个完整详尽的测试方法，也相当适合进行基准测试：

#include <limits.h>

int direct(int n)
{
    int cr0;
    if (n < 0)
        cr0 = 1;
    else if (n > 0)
        cr0 = 2;
    else
        cr0 = 4;
    return cr0;
}

const int shift_count = sizeof(int) * CHAR_BIT - 1;
int tricky(int n)
{
    int cr0 = (-(n | n-1) >> shift_count) & 6;
    cr0 |= (n >> shift_count) & 5;
    cr0 ^= 4;
    return cr0;
}

#include <iostream>
#include <iomanip>
int main(void)
{
    int i = 0;
    do {
        if (direct(i) != tricky(i)) {
            std::cerr << std::hex << i << std::endl;
            return i;
        }
    } while (++i);
    return 0;
}

- Ben Voigt

1

+1 而且既然您似乎要对所有提出的解决方案进行基准测试，也许您可以发布一些结果（至少对于有效的解决方案）？在进行基准测试时，考虑对输入位进行随机洗牌以干扰分支预测器并使其成为更真实的测试如何？ - Christian Rau

如果要用于基准测试，测试不应该更随机吗？这样分支版本看起来会比实际情况好很多。 - harold

1

@harold：这绝对不是一个理想的基准测试，但它比仅仅计算汇编指令能更好地显示速度。 - Ben Voigt

这是真的。 :) 创建准确的基准测试非常困难。只要你意识到其局限性，简单的基准测试就可以了。 - jalf

理想情况下，您也希望了解实际输入的分布情况。50％正数、25％零和25％负数的分布比均匀分布更好。 - Ben Voigt

1

如果有更快的方法，编译器可能已经在使用它了。

保持你的代码简短和简单；这使得优化器最有效。

简单直接的解决方案在速度方面表现出人意料的好。

cr0 = n? (n < 0)? 1: 2: 4;

x86汇编（由VC++ 2010生成，标志/Ox）：

PUBLIC  ?tricky@@YAHH@Z                                 ; tricky
; Function compile flags: /Ogtpy
_TEXT   SEGMENT
_n$ = 8                                                 ; size = 4
?tricky@@YAHH@Z PROC                                    ; tricky
; Line 26
        mov     eax, DWORD PTR _n$[esp-4]
        test    eax, eax
        je      SHORT $LN3@tricky
        xor     ecx, ecx
        test    eax, eax
        setns   cl
        lea     eax, DWORD PTR [ecx+1]
; Line 31
        ret     0
$LN3@tricky:
; Line 26
        mov     eax, 4
; Line 31
        ret     0
?tricky@@YAHH@Z ENDP                                    ; tricky

- Ben Voigt

在这种情况下，我不会那么确定。PowerPC似乎没有整数条件移动指令。 - Mysticial

2

如果编译器还没有使用最快的方法怎么办？我同意第二行，但是在需要超出编译器能为您生成的内容时呢？ - jalf

1

模拟器是“简短而简单”模式的少数反例之一，其中小的性能优势（如果存在）可以很快得到回报。 - BeeOnRope

好的...我误读了问题的一部分。我以为它是在 PowerPC 上本地运行的。 - Mysticial

@Christian：请展示你的三指令位操作技巧。我在这里看到的最短的是九个（jalf的最终表达式，加上括号）。 - Ben Voigt

显示剩余6条评论

1

对于完全不可移植的方法，我想知道这是否有任何速度优势：

void func(signed n, signed& cr0) {
    cr0 = 1 << (!(unsigned(n)>>31)+(n==0));
}

mov         ecx,eax  ;with MSVC10, all optimizations except inlining on.
shr         ecx,1Fh  
not         ecx  
and         ecx,1  
xor         edx,edx  
test        eax,eax  
sete        dl  
mov         eax,1  
add         ecx,edx  
shl         eax,cl  
mov         ecx,dword ptr [cr0]  
mov         dword ptr [ecx],eax

与我机器上的代码相比：

test        eax,eax            ; if (n < 0)
jns         func+0Bh (401B1Bh)  
mov         dword ptr [ecx],1  ; cr0 = 1;
ret                            ; cr0 = 2; else cr0 = 4; }
xor         edx,edx            ; else if (n > 0)
test        eax,eax  
setle       dl  
lea         edx,[edx+edx+2]  
mov         dword ptr [ecx],edx ; cr0 = 2; else cr0 = 4; }
ret

我对汇编不是很了解，所以不能确定这是否有任何好处（甚至不确定我的代码是否有跳转。我没有看到任何以j开头的指令）。像往常一样，（正如其他人说过无数次的那样）要进行性能分析。

我怀疑这比Jalf或Ben的代码更快，但我没有看到任何一个利用x86上所有负数都有特定位设置的事实的代码，所以我想我可以提供一个。

[编辑] BenVoigt建议使用cr0 = 4 >> ((n != 0) + (unsigned(n) >> 31));来消除逻辑否定，并且我的测试表明这是一个巨大的改进。

- Mooing Duck

1

我认为 2 << ((n == 0) - (unsigned(n) >> 31)) 会更好一些，因为它消除了逻辑否定的需要。或者是 (2 << (n == 0)) - (unsigned(n) >> 31)。 - Ben Voigt

з”ҡиҮіеҸҜд»ҘдҪҝз”Ёз®—жңҜз§»дҪҚиҖҢдёҚжҳҜйҖ»иҫ‘з§»дҪҚзҡ„+ (n >> 31)гҖӮдҪҶжҲ‘зңҹзҡ„дёҚи®Өдёәиҝҷз§Қж–№жі•дјҡжңүд»»дҪ•жҖ§иғҪдјҳеҠҝгҖӮ - Ben Voigt

@BenVoigt：你在第一条评论中的代码在我的大多数测试中都比这个页面上的大多数代码表现得更好，但在我最近一轮的测试中，出现了错误的结果。 - Mooing Duck

@BenVoigt：也许正确的代码应该是cr0 = 4 >> ((n != 0) + (unsigned(n) >> 31));它接近于你所建议的，并且比其他所有代码都更有效。 - Mooing Duck

嗯，是的，我猜传递负移位计数是未定义行为，而您的最新版本修复了这个问题。所以我建议在您的答案中加入这一点。虽然我的第二个变体（将减法放在移位之外）不应该受到UB的影响。 - Ben Voigt

-1

以下是我的尝试。

int cro = 4 >> (((n > 0) - (n < 0)) % 3 + (n < 0)*3);

- Appleman1234

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jalf · Accepted Answer

首先，如果这个变量要在每条指令后（几乎）更新，那么显而易见的建议是：

不要

只有在后续指令需要其值时才更新它。在任何其他时间，更新它都没有意义。

但无论如何，当我们更新它时，我们希望的是这种行为：

R < 0  => CR0 == 0b001 
R > 0  => CR0 == 0b010
R == 0 => CR0 == 0b100

理想情况下，我们根本不需要分支。以下是一种可能的方法：

将CR0设置为值1。(如果你真的想要速度，可以调查是否可以在不从内存获取常量的情况下完成此操作。即使您必须花费几个指令来完成它，这也很值得）
如果R >= 0，则左移一位。
如果R == 0，则左移一位。

其中步骤2和3可以进行转换以消除“if”部分。

CR0 <<= (R >= 0);
CR0 <<= (R == 0);

这样做更快吗？我不确定。像往常一样，当你关心性能时，你需要进行测量、测量和测量。

然而，我可以看到这种方法有几个优点：

我们完全避免了分支
我们避免了内存的读取/存储。
我们依赖的指令（位移和比较）应该具有低延迟，而对于乘法来说并不总是如此。

缺点是我们三行代码之间存在依赖链：每个代码都修改CR0寄存器，然后在下一行使用它。这在一定程度上限制了指令级并行性。

为了尽量减少这种依赖链，我们可以改为这样做：

CR0 <<= ((R >= 0) + (R == 0));

因此，我们只需要在其初始化后修改CR0一次。

或者，一行代码完成所有操作：

CR0 = 1 << ((R >= 0) + (R == 0));

当然，这个主题有很多可能的变化，所以继续尝试和实验吧。