在 C 中确定数组元素是否为非负的快速技巧？

Question

我正在写一个函数

int are_non_negatives(int* start, int n) {
  ...
}

如果n数组start中的所有下一个整数都是非负数，则此函数返回 1 。否则返回 0。

我的问题是是否存在尽可能快地执行此操作的技巧（除了循环和检查每个位置）？

脏/非便携式技巧很好。我也想知道这些。谢谢！

Answer 1

在需要检查所有元素的最坏情况下，您可以利用一个稍微“脏/不可移植”的技巧：在 2 的补码 int 表示中，当且仅当值为负时设置最高位。因此，您可以将它们全部按位或并检查最高位。这可以使用向量指令一次完成批量处理，例如，假设 32 位 int 和 256 位 AVX 指令，一次处理 8 个元素。

Answer 2

尝试提高性能是 C 程序员反复讨论的主题。有必要对替代方案进行基准测试，以测试优化是否有用且值得付出努力。这是一个幼稚的实现供参考：

int are_non_negatives_naive(const int *start, int n) {
    while (n --> 0) {
        if (*start++ >= 0)
            return 0;
    }
    return 1;
}

在当前的体系结构（二进制补码）上，您可以组合条目块并更少地测试符号位。如果数组很小，您可以组合所有元素并使用单个测试：

int are_non_negatives_full(const int *start, int n) {
    int combined = 0;
    while (n --> 0) {
        combined |= *start++;
    }
    return combined >= 0;
}

如果数组大小不同，您可以组合块中的所有元素并测试每个块，以便在存在负值时尽早退出：

int are_non_negatives_chunks(const int *start, int n) {
    int combined;
    for (; n >= 8; n -= 8, start += 8) {
        combined = (start[0] | start[1] | start[2] | start[3] |
                    start[4] | start[5] | start[6] | start[7]);
        if (combined < 0)
            return 0;
    }
    combined = 0;
    while (n --> 0) {
        combined |= *start++;
    }
    return combined >= 0;
}

通过使用可移植结构（例如使用 64 位类型）或更具体的硬件特定内在函数对上述内容进行矢量化，可以实现进一步的性能改进。如果编译器可以自行对上述算法进行向量化，那么这项工作可能就没有必要了：clang使用 SIMD 指令，如Godbolt Compiler Explorer所示。