判断4个整数符合“第一个为1，后三个为0”的方法

safedead

[ 本帖最后由 safedead 于 2013-02-18 18:25 编辑 ]

有4个无符号整数，存储在四个变量里
uint64_t rax;
uint64_t rdx;
uint64_t r8;
uint64_t r9;

现在需要计算如下条件表达式的结果:
(rax == 1) && (rdx == 0) && (r8 == 0) && (r9 == 0)

我是这么设计的
uint64_t rsi = 0;
if (rax != 1) rsi = 1;
if (rdx != 0) rsi = 1;
if (r8 != 0) rsi = 1;
if (r9 != 0) rsi = 1;
rsi就是计算结果

还有没有更高效的算法？

根据hellioncu提供的算法
得到当前最优答案

movq    %rax, %rsi
xorq    $1, %rsi
orq     %rdx, %rsi
orq     %r8, %rsi
orq     %r9, %rsi
jz      .L_IS_ONE

不超过5个指令周期完成判断一个256位整数是否为1的运算

safedead

[ 本帖最后由 safedead 于 2013-02-17 11:34 编辑 ]


我是这么写的:(rcx就是常数1，若条件表达式成立，rsi为0，否则为1)
        xorq        %rcx, %rcx
        incq        %rcx
        xorq        %rsi, %rsi
        test        %r9, %r9
        cmovnz        %rcx, %rsi
        test        %r8, %r8
        cmovnz        %rcx, %rsi
        test        %rdx, %rdx
        cmovnz        %rcx, %rsi
        cmpq        %rcx, %rax
        cmovne        %rcx, %rsi

Ager

1. 
   
2. if (rax != 1) rsi = 1;
   
3. if (rdx != 0) rsi = 1;
   
4. if (r8 != 0) rsi = 1;
   
5. if (r9 != 0) rsi = 1;
   
6. 
   
7. rsi就是计算结果
   

复制代码

没看明白 ……那四个uint64_t整数，预设好了是非0即1的吗？ {:3_201:}

zylthinking

safedead 发表于 2013-02-17 11:26
[ 本帖最后由 safedead 于 2013-02-17 11:27 编辑 ]

有4个无符号整数，存储在四个变量里

好歹这个速度更高点吧

a = rbx | r8 | r9;
rsi = rax;
if (a != 0) rsi = 0;

safedead

zylthinking 发表于 2013-02-17 12:06
好歹这个速度更高点吧

a = rbx | r8 | r9;

这个好，我总觉得我自己写得怪怪的
先将所有要判断为0的同或，如果为0表示全部为0
然后判断rax是否为1，只要两次cmov即可得到最终结果

我的目的是这样的
有n个64位整数构成一个大数，低位在前，高位在后，我要判断这个大数是否为1
以256位二进制数为例子
rax, rdx, r8, r9分别存储从低到高4个64位单元，如果这个256位数值等于1
必须满足：(rax == 1) && (rdx == 0) && (r8 == 0) && (r9 == 0)
用rsi保存中间结果，按照楼上的方法运算就是
rsi = 0;
rsi |= r9;
rsi |= r8;
rsi |= rdx;
if (rsi == 0) {
    if (rax == 1) 条件成立;
}

w_anthony

如果你用C写，编译后看汇编，不出意外应该cmp+jnz+test+jnz+test+jnz+test+jnz，何必要计算以后再跳转呢？
既然是一个大数，那么刚好等于1的概率本身就很小，可能第一次cmp或者test就不满足条件，可以直接jnz掉，但是耍个花招反而要多算几次才知道结果。

safedead

改好了

rsi = 0;
if (rax == 1) rsi = 1;
rsi |= r9;
rsi |= r8;
rsi |= rdx;
if (rsi == 0) 条件成立

汇编结果：
movq    $1, %rcx
xorq    %rsi, %rsi
test    %rcx, %rax
cmovnz  %rcx, %rsi
orq     %r9, %rsi
orq     %r8, %rsi
orq     %rdx, %rsi
test    %rsi, %rsi
jz      .L_IS_ONE

safedead

w_anthony 发表于 2013-02-17 13:51
如果你用C写，编译后看汇编，不出意外应该cmp+jnz+test+jnz+test+jnz+test+jnz，何必要计算以后再跳转呢？
...

这么编译相当糟糕，破坏流水线的惩罚可是很严重的，跳转指令要尽可能的少
多用几个cmov，最后跳转比较有利

hellioncu

rsi = (rax ^ 0x1) | (rdx | r8 | r9)