如何在不使用比较操作的前提下统计自然数数组中的正数个数

首先明确规则：这里的「不使用任何比较操作」通常指禁止在判断元素是否为正数的逻辑中使用>、<、>=、<=、==、!=等显式比较运算符，算术运算、位运算、累加操作均允许使用。

注：如果要求完全禁用所有比较（包括遍历的边界判断），可基于对应编程语言的底层遍历指令（如x86汇编的loop指令）实现无比较遍历，常规实现中默认遍历边界的比较不属于限制范围。

因为数组所有元素都是非负自然数，我们只需要给每个元素生成对应标识：正数对应1，0对应0，累加所有标识即可得到正数总数。 #

通用位运算实现（适配固定位宽有符号整数，如C/C++/Java的32位int） #

核心逻辑利用补码的位特征：

• 当x = 0时，x | -x结果为0
• 当x > 0时，x补码最高位为0，-x补码最高位为1，按位或后所有位都是1，对应32位有符号整数的-1

将上述结果算术右移31位后和1按位与，就能得到我们要的标识：

int countPositive(int* arr, int arrLen) {
    int res = 0;
    for (int i = 0; i < arrLen; i++) {
        int x = arr[i];
        res += ((x | -x) >> 31) & 1;
    }
    return res;
}

整个元素判断逻辑没有用到任何比较运算符，完全符合要求。 #

任意精度整数实现（如Python） #

如果使用无固定位宽的整数类型，还可以用更简单的写法：

def count_positive(arr):
    count = 0
    for x in arr:
        # bool(x)在x为0时返回False（对应数值0），非0时返回True（对应数值1），无显式比较
        count += int(bool(x))
    return count

如果不允许使用隐式布尔转换，也可以基于位宽计算改造通用位运算逻辑适配任意精度整数。 #

内容的提问来源于stack exchange，提问作者YAKOVM