C语言中确定数组元素为非负数的快速技巧？

Question

我正在编写一个函数

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

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

我的问题是是否有比遍历和检查每个位置都更快的技巧？

脏/不可移植的技巧也可以。我也想知道那些。谢谢!

- apen

---

循环检查。这里没有什么捷径。如果这些已经排序，那么您可以始终测试最低值是否大于0，或者根据您对“非负”的定义而是大于等于0。 - tadman

你能给一些使用示例并更好地解释参数吗？ - tadman

你可以对 int 元素进行按位或操作，最后测试符号位是否为1。（在符号-数值实现中，这将把 −0 视为负数。）一些处理器上，一系列的按位或操作可能比比较更快。你也可以展开循环以并行计算。然后，你可以考虑使用 SIMD 等扩展功能。 - Eric Postpischil

对它们进行按位或操作会消除循环提前终止的可能性，从而使其在平均情况下性能较差。 - Eugene Sh.

@EricPostpischil 的确。我指出了这种方法可能存在的缺点，OP应该意识到。 - Eugene Sh.

Answer 1

在所有元素都需要检查的最坏情况下，您可以利用一个稍微“不干净/非便携”的技巧：在二进制补码int表示中，当且仅当值为负时，最高位设置。因此，您可以对它们进行按位 OR 运算并检查最高位。这可以使用矢量指令批处理执行，例如每次8个元素，假设32位整数和256位AVX指令。

- Pascal Getreuer

---

很棒的答案。一个（简化的）代码片段会很好。 - apen

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中看到。

- chqrlie

Answer 3

您可以通过转换为可用的最大整数并制作正确的掩码来一次检查k个元素，例如：如果您有一个char或int8_t数组，则可以一次检查8个元素。
掩码被制作成全零，除了符号位。
这样，如果其中一个chars为负数，则掩码和转换迭代器的按位与将是> 0

int8_t _i8[8] = { INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN };
uint64_t mask = *(uint64_t *)_i8;

uint64_t *it = (uint64_t *)a;
size_t i = 0;

if (it[i] & mask)
    return FALSE;

当然，你需要处理 n % k 的余数，可以通过以下简单的 switch 语句来完成：

size_t i = 0;

switch (n % 8) {
    case 0: if (a[i++] < 0) return FALSE;
    case 7: if (a[i++] < 0) return FALSE;
    case 6: if (a[i++] < 0) return FALSE;
    case 5: if (a[i++] < 0) return FALSE;
    case 4: if (a[i++] < 0) return FALSE;
    case 3: if (a[i++] < 0) return FALSE;
    case 2: if (a[i++] < 0) return FALSE;
    case 1: if (a[i++] < 0) return FALSE;
}

我做了一个概念验证，比较了天真的方法、使用Duff's device展开的方法以及同时使用Duff's device和掩码的展开方法。
需要进行更多测试，但看起来仍然有希望。

你可以在这里运行它https://onlinegdb.com/SyliIUrSZO

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <time.h>

#define CLOCKS_PER_MSEC (CLOCKS_PER_SEC/1000)

#define TRUE (0 == 0)
#define FALSE (!TRUE)

// 8 bit integers
int are_non_negatives_naive_i8(int8_t *a, size_t n)
{
    size_t i;

    for (i = 0; i < n; ++i)
        if (a[i] < 0)
            return FALSE;

    return TRUE;
}
int are_non_negatives_unrolled_i8(int8_t *a, size_t n)
{
    size_t M = (n + 7) / 8;
    size_t i = 0;

    switch (n % 8) {
        case 0: do { if (a[i++] < 0) return FALSE;
        case 7:      if (a[i++] < 0) return FALSE;
        case 6:      if (a[i++] < 0) return FALSE;
        case 5:      if (a[i++] < 0) return FALSE;
        case 4:      if (a[i++] < 0) return FALSE;
        case 3:      if (a[i++] < 0) return FALSE;
        case 2:      if (a[i++] < 0) return FALSE;
        case 1:      if (a[i++] < 0) return FALSE;
                    } while (--M > 0);
    }
}
int are_non_negatives_unrolled_masked_i8(int8_t *a, size_t n)
{
    int8_t _i8[8] = { INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN };
    uint64_t mask = *(uint64_t *)_i8;

    uint64_t *it = (uint64_t *)a;

    size_t i = 0;

    switch (n % 8) {
        case 0: if (a[i++] < 0) return FALSE;
        case 7: if (a[i++] < 0) return FALSE;
        case 6: if (a[i++] < 0) return FALSE;
        case 5: if (a[i++] < 0) return FALSE;
        case 4: if (a[i++] < 0) return FALSE;
        case 3: if (a[i++] < 0) return FALSE;
        case 2: if (a[i++] < 0) return FALSE;
        case 1: if (a[i++] < 0) return FALSE;
    }

    size_t N = n / 8;
    // for (i = 0; i < N; ++i)
    //     if (it[i] & mask)
    //         return FALSE;

    size_t M = (N + 7) / 8;
    switch (N % 8) {
        case 0: do { if (it[i++] & mask) return FALSE;
        case 7:      if (it[i++] & mask) return FALSE;
        case 6:      if (it[i++] & mask) return FALSE;
        case 5:      if (it[i++] & mask) return FALSE;
        case 4:      if (it[i++] & mask) return FALSE;
        case 3:      if (it[i++] & mask) return FALSE;
        case 2:      if (it[i++] & mask) return FALSE;
        case 1:      if (it[i++] & mask) return FALSE;
                    } while (--M > 0);
    }

    return TRUE;
}
//----------------------------------------------------------------

// 16 bit integers 
int are_non_negatives_naive_i16(int16_t *a, size_t n)
{
    size_t i;

    for (i = 0; i < n; ++i)
        if (a[i] < 0)
            return FALSE;

    return TRUE;
}
int are_non_negatives_unrolled_i16(int16_t *a, size_t n)
{
    size_t M = (n + 7) / 8;
    size_t i = 0;

    switch (n % 8) {
        case 0: do { if (a[i++] < 0) return FALSE;
        case 7:      if (a[i++] < 0) return FALSE;
        case 6:      if (a[i++] < 0) return FALSE;
        case 5:      if (a[i++] < 0) return FALSE;
        case 4:      if (a[i++] < 0) return FALSE;
        case 3:      if (a[i++] < 0) return FALSE;
        case 2:      if (a[i++] < 0) return FALSE;
        case 1:      if (a[i++] < 0) return FALSE;
                    } while (--M > 0);
    }
}
int are_non_negatives_unrolled_masked_i16(int16_t *a, size_t n)
{
    int16_t _i16[4] = { INT16_MIN, INT16_MIN, INT16_MIN, INT16_MIN };
    uint64_t mask = *(uint64_t *)_i16;

    uint64_t *it = (uint64_t *)a;

    size_t i = 0;

    switch (n % 8) {
        case 0: if (a[i++] < 0) return FALSE;
        case 7: if (a[i++] < 0) return FALSE;
        case 6: if (a[i++] < 0) return FALSE;
        case 5: if (a[i++] < 0) return FALSE;
        case 4: if (a[i++] < 0) return FALSE;
        case 3: if (a[i++] < 0) return FALSE;
        case 2: if (a[i++] < 0) return FALSE;
        case 1: if (a[i++] < 0) return FALSE;
    }

    size_t N = n / 4;
    // for (i = 0; i < N; ++i)
    //     if (it[i] & mask)
    //         return FALSE;

    size_t M = (N + 7) / 8;
    switch (N % 8) {
        case 0: do { if (it[i++] & mask) return FALSE;
        case 7:      if (it[i++] & mask) return FALSE;
        case 6:      if (it[i++] & mask) return FALSE;
        case 5:      if (it[i++] & mask) return FALSE;
        case 4:      if (it[i++] & mask) return FALSE;
        case 3:      if (it[i++] & mask) return FALSE;
        case 2:      if (it[i++] & mask) return FALSE;
        case 1:      if (it[i++] & mask) return FALSE;
                    } while (--M > 0);
    }

    return TRUE;
}
//----------------------------------------------------------------

// 32 bit integers 
int are_non_negatives_naive_i32(int32_t *a, size_t n)
{
    size_t i;

    for (i = 0; i < n; ++i)
        if (a[i] < 0)
            return FALSE;

    return TRUE;
}
int are_non_negatives_unrolled_i32(int32_t *a, size_t n)
{
    size_t M = (n + 7) / 8;
    size_t i = 0;

    switch (n % 8) {
        case 0: do { if (a[i++] < 0) return FALSE;
        case 7:      if (a[i++] < 0) return FALSE;
        case 6:      if (a[i++] < 0) return FALSE;
        case 5:      if (a[i++] < 0) return FALSE;
        case 4:      if (a[i++] < 0) return FALSE;
        case 3:      if (a[i++] < 0) return FALSE;
        case 2:      if (a[i++] < 0) return FALSE;
        case 1:      if (a[i++] < 0) return FALSE;
                    } while (--M > 0);
    }
}
int are_non_negatives_unrolled_masked_i32(int32_t *a, size_t n)
{
    int32_t _i32[2] = { INT32_MIN, INT32_MIN };
    uint64_t mask = *(uint64_t *)_i32;

    uint64_t *it = (uint64_t *)a;

    size_t i = 0;

    switch (n % 8) {
        case 0: if (a[i++] < 0) return FALSE;
        case 7: if (a[i++] < 0) return FALSE;
        case 6: if (a[i++] < 0) return FALSE;
        case 5: if (a[i++] < 0) return FALSE;
        case 4: if (a[i++] < 0) return FALSE;
        case 3: if (a[i++] < 0) return FALSE;
        case 2: if (a[i++] < 0) return FALSE;
        case 1: if (a[i++] < 0) return FALSE;
    }

    size_t N = n / 2;
    // for (i = 0; i < N; ++i)
    //     if (it[i] & mask)
    //         return FALSE;

    size_t M = (N + 7) / 8;
    switch (N % 8) {
        case 0: do { if (it[i++] & mask) return FALSE;
        case 7:      if (it[i++] & mask) return FALSE;
        case 6:      if (it[i++] & mask) return FALSE;
        case 5:      if (it[i++] & mask) return FALSE;
        case 4:      if (it[i++] & mask) return FALSE;
        case 3:      if (it[i++] & mask) return FALSE;
        case 2:      if (it[i++] & mask) return FALSE;
        case 1:      if (it[i++] & mask) return FALSE;
                    } while (--M > 0);
    }

    return TRUE;
}
//----------------------------------------------------------------

void fill_array(void *array, size_t type, size_t n, int contains_negatives)
{
    size_t i;

    switch (type) {
        case 1: {
            int8_t *a = array;

            for (i = 0; i < n; ++i)
                a[i] = rand() % INT8_MAX;
            break;
        }
        case 2: {
            int16_t *a = array;

            for (i = 0; i < n; ++i)
                a[i] = rand() % INT16_MAX;
            break;
        }
        case 4: {
            int32_t *a = array;

            for (i = 0; i < n; ++i)
                a[i] = rand() % INT32_MAX;
            break;
        }
        case 8: {
            int64_t *a = array;

            for (i = 0; i < n; ++i)
                a[i] = rand();
            break;
        }
    }

    if (contains_negatives) {
        int how_many = rand() % n;
        
        for (int i; i < how_many; ++i) {
            int j = rand() % n;

            switch (type) {
                case 1: {
                    int8_t *a = array;
                    a[j] *= -1;
                    break;
                }
                case 2: {
                    int16_t *a = array;
                    a[j] *= -1;
                    break;
                }
                case 4: {
                    int32_t *a = array;
                    a[j] *= -1;
                    break;
                }
                case 8: {
                    int64_t *a = array;
                    a[j] *= -1;
                    break;
                }
            }
        }
    }
}

int main()
{
    time_t t;

    clock_t clock_start;
    clock_t clock_end;
    clock_t clock_naive = 0;
    clock_t clock_unrolled = 0;
    clock_t clock_unrolled_masked = 0;

    /* Intializes random number generator */
    srand((unsigned long) time(&t));

    printf("8 bit integers\n");
    printf("----------------------------------------------------------------\n");
    int8_t *array_i8;

    for (int i = 3; i < 7; ++i) {
        size_t size = pow(10, i);
        array_i8 = malloc(size * sizeof(int8_t));

        printf("------------------------------------------------\n");
        printf("%lu elements\n", size);
        for (int has_neg = 0; has_neg < 2; ++has_neg) {
            printf("--------------------------------\n");
            printf("Has negatives: %s\n", has_neg ? "yes": "no");
            fill_array(array_i8, sizeof(int8_t), size, has_neg);

            int neg_naive;
            int neg_unrolled;
            int neg_unrolled_masked;

            clock_start = clock();
            neg_naive = are_non_negatives_naive_i8(array_i8, size);
            clock_end = clock();
            clock_naive = clock_end - clock_start;

            clock_start = clock();
            neg_unrolled = are_non_negatives_unrolled_i8(array_i8, size);
            clock_end = clock();
            clock_unrolled = clock_end - clock_start;

            clock_start = clock();
            neg_unrolled_masked = are_non_negatives_unrolled_masked_i8(array_i8, size);
            clock_end = clock();
            clock_unrolled_masked = clock_end - clock_start;
            
            if (!has_neg) {
                if (!neg_naive)
                    printf("Error: neg_naive\n");
                if (!neg_unrolled)
                    printf("Error: neg_unrolled\n");
                if (!neg_unrolled_masked)
                    printf("Error: neg_unrolled_masked\n");
            }

            printf("          clock_naive: %lu\n", clock_naive);
            printf("       clock_unrolled: %lu\n", clock_unrolled);
            printf("clock_unrolled_masked: %lu\n", clock_unrolled_masked);
            printf("--------------------------------\n");
        }
        printf("------------------------------------------------\n");

        free (array_i8);
        array_i8 = NULL;
    }
    printf("----------------------------------------------------------------\n");

    printf("16 bit integers\n");
    printf("----------------------------------------------------------------\n");
    int16_t *array_i16;

    for (int i = 3; i < 7; ++i) {
        size_t size = pow(10, i);
        array_i16 = malloc(size * sizeof(int16_t));

        printf("------------------------------------------------\n");
        printf("%lu elements\n", size);
        for (int has_neg = 0; has_neg < 2; ++has_neg) {
            printf("--------------------------------\n");
            printf("Has negatives: %s\n", has_neg ? "yes": "no");
            fill_array(array_i16, sizeof(int16_t), size, has_neg);

            int neg_naive;
            int neg_unrolled;
            int neg_unrolled_masked;

            clock_start = clock();
            neg_naive = are_non_negatives_naive_i16(array_i16, size);
            clock_end = clock();
            clock_naive = clock_end - clock_start;

            clock_start = clock();
            neg_unrolled = are_non_negatives_unrolled_i16(array_i16, size);
            clock_end = clock();
            clock_unrolled = clock_end - clock_start;

            clock_start = clock();
            neg_unrolled_masked = are_non_negatives_unrolled_masked_i16(array_i16, size);
            clock_end = clock();
            clock_unrolled_masked = clock_end - clock_start;
            
            if (!has_neg) {
                if (!neg_naive)
                    printf("Error: neg_naive\n");
                if (!neg_unrolled)
                    printf("Error: neg_unrolled\n");
                if (!neg_unrolled_masked)
                    printf("Error: neg_unrolled_masked\n");
            }

            printf("          clock_naive: %lu\n", clock_naive);
            printf("       clock_unrolled: %lu\n", clock_unrolled);
            printf("clock_unrolled_masked: %lu\n", clock_unrolled_masked);
            printf("--------------------------------\n");
        }
        printf("------------------------------------------------\n");

        free (array_i16);
        array_i16 = NULL;
    }
    printf("----------------------------------------------------------------\n");

    printf("32 bit integers\n");
    printf("----------------------------------------------------------------\n");
    int32_t *array_i32;

    for (int i = 3; i < 7; ++i) {
        size_t size = pow(10, i);
        array_i32 = malloc(size * sizeof(int32_t));

        printf("------------------------------------------------\n");
        printf("%lu elements\n", size);
        for (int has_neg = 0; has_neg < 2; ++has_neg) {
            printf("--------------------------------\n");
            printf("Has negatives: %s\n", has_neg ? "yes": "no");
            fill_array(array_i32, sizeof(int32_t), size, has_neg);

            int neg_naive;
            int neg_unrolled;
            int neg_unrolled_masked;

            clock_start = clock();
            neg_naive = are_non_negatives_naive_i32(array_i32, size);
            clock_end = clock();
            clock_naive = clock_end - clock_start;

            clock_start = clock();
            neg_unrolled = are_non_negatives_unrolled_i32(array_i32, size);
            clock_end = clock();
            clock_unrolled = clock_end - clock_start;

            clock_start = clock();
            neg_unrolled_masked = are_non_negatives_unrolled_masked_i32(array_i32, size);
            clock_end = clock();
            clock_unrolled_masked = clock_end - clock_start;
            
            if (!has_neg) {
                if (!neg_naive)
                    printf("Error: neg_naive\n");
                if (!neg_unrolled)
                    printf("Error: neg_unrolled\n");
                if (!neg_unrolled_masked)
                    printf("Error: neg_unrolled_masked\n");
            }

            printf("          clock_naive: %lu\n", clock_naive);
            printf("       clock_unrolled: %lu\n", clock_unrolled);
            printf("clock_unrolled_masked: %lu\n", clock_unrolled_masked);
            printf("--------------------------------\n");
        }
        printf("------------------------------------------------\n");

        free (array_i32);
        array_i32 = NULL;
    }
    printf("----------------------------------------------------------------\n");
}

任何建议或修复都非常欢迎。

---

请注意，这种解决方案并不标准，取决于数据类型的对齐方式。
虽然它通常可以工作，但您应该使用类似以下的方法进行检查。

#include <stdio.h>
#include <stdint.h>
#include <stdalign.h>

int main()
{
    printf(
        "alignof(int8_t ): %lu\n"
        "alignof(int16_t): %lu\n"
        "alignof(int32_t): %lu\n"
        "alignof(int64_t): %lu\n",
        alignof(int8_t),
        alignof(int16_t),
        alignof(int32_t),
        alignof(int64_t)
    );

    return 0;
}

- Jack Lilhammers

---

*(uint64_t *)_i8 和 uint64_t *it = (uint64_t *)a; 都是严格别名规则的违反，因此会导致未定义行为。它们还通过违反C11 6.3.2.3p7而冒着未定义行为的风险：“指向对象类型的指针可以转换为指向不同对象类型的指针。如果所得到的指针对于引用的类型没有正确对齐，则其行为未定义。” - Andrew Henle

Answer 4

根据你的问题背景，我怀疑这种方法对你可能不适用。但是如果你的代码允许捕获数组操作（初始化、插入、修改、删除），那么你可以一致地维护一个单独的负值元素列表。如果你有这个自由，那么这只是一个空间和速度的权衡。

- pion