0

玩弄删除 C++ 中的分支，无法破译输出背后的原因。

PopHi()采用两个升序整数向量和迄今为止最大的当前索引。它通过减少两者中较大者的索引来“弹出”最大的 int。

代码

原来的：

void PopHi(vector<int> &arrA, vector<int> &arrB, int &idxHiA, int &idxHiB) {
    int hi = max(arrA[idxHiA], arrB[idxHiB]);
    if (hi == arrA[idxHiA])
        --idxHiA;
    else
        --idxHiB;
}

Nobranch 版本 1：

void PopHi(vector<int> &arrA, vector<int> &arrB, int &idxHiA, int &idxHiB) {
    idxHiA -= (arrA[idxHiA] > arrB[idxHiB]);
    idxHiB -= (!(arrA[idxHiA] > arrB[idxHiB]));
}

Nobranch 版本 2，因为如果它们相等，我们选择哪一个并不重要：

void PopHi(vector<int> &arrA, vector<int> &arrB, int &idxHiA, int &idxHiB) {
    idxHiA -= (arrA[idxHiA] >= arrB[idxHiB]);
    idxHiB -= (!(arrA[idxHiA] >= arrB[idxHiB])); // extra paranoia parens
}

这就是我使用它的方式：

// compiled with g++ -std=c++11 main.cpp -o run
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    vector<int> arrA({1, 3, 5});
    vector<int> arrB({5});
    int idxHiA = 2;
    int idxHiB = 0;
    cout << idxHiA << ", " << idxHiB << endl;
    PopHi(arrA, arrB, idxHiA, idxHiB);
    cout << idxHiA << ", " << idxHiB << endl;
    return 0;
}

输出

原来的：

2, 0
1, 0 // ok

版本 1：

2, 0
2, -1 // also ok

版本 2：

2, 0
1, -1 // wtf??
4

1 回答 1

3 
idxHiA -= (arrA[idxHiA] >= arrB[idxHiB]);

你在idxHiA这里换...

idxHiB -= (!(arrA[idxHiA] >= arrB[idxHiB]));

......在这里咬你。您想使用 的旧值idxHiA，但正在使用递减的值（这可能是非法的顺便说一句）。该位置的元素不再是最大值。

我建议将比较的结果存储到一个布尔变量中，这样更容易阅读。

PS：我会在汇编程序中检查您的“无分支”版本实际上没有分支。有时，带有布尔变量的操作会使用分支进行转换。

于 2012-11-01T00:03:10.410 回答