如何统计异或结果含奇数个置位比特的子数组数量

• 前缀异或：对于数组nums，定义前缀异或数组prefix，其中prefix[0] = 0，prefix[i] = nums[0] ^ nums[1] ^ ... ^ nums[i-1]。任意子数组nums[j+1..i]的异或结果等于prefix[i] ^ prefix[j]——这是异或的基本性质：相同数异或为0，0与任何数异或等于该数本身。
• 置位比特奇偶性的运算性质：设f(x)表示x的二进制中1的个数的奇偶性（0为偶，1为奇），则f(a ^ b) = f(a) ^ f(b)。原因是异或操作会翻转对应位的比特，每翻转一次，1的个数的奇偶性就会切换，最终整体奇偶性等于两个数各自奇偶性的异或。
• 条件转化：我们需要子数组异或结果的f值为1，即f(prefix[i] ^ prefix[j]) = 1。根据上述性质，这等价于f(prefix[i]) ^ f(prefix[j]) = 1——也就是f(prefix[i])和f(prefix[j])必须一0一1。

思路 #

我们只需要统计遍历过程中，当前前缀异或的f值与之前所有前缀异或f值不相等的数量，累加起来就是结果。用两个计数器分别记录已遍历的前缀异或中f值为0和1的数量，就能在每一步O(1)时间内计算出符合条件的子数组数量。

步骤 #

1. 初始化：
   • current_xor：维护当前前缀异或值，初始为0（对应prefix[0]）
   • count0：记录已遍历前缀异或中f值为0的数量，初始为1（因为prefix[0] = 0，f(0)=0）
   • count1：记录已遍历前缀异或中f值为1的数量，初始为0
   • result：记录满足条件的子数组总数，初始为0
2. 遍历数组每个元素：
   • 更新current_xor为current_xor ^ num，得到当前的前缀异或值
   • 计算当前current_xor的f值：Python 3.10+可用current_xor.bit_count() % 2（效率更高），旧版本用bin(current_xor).count('1') % 2
   • 如果f值为1：所有之前f值为0的前缀异或都能和当前值组成符合条件的子数组，把count0加到result，然后count1 += 1
   • 如果f值为0：所有之前f值为1的前缀异或都能和当前值组成符合条件的子数组，把count1加到result，然后count0 += 1
3. 遍历结束后，result就是答案。

代码示例（Python） #

def count_subarrays_with_odd_set_bits(nums):
    current_xor = 0
    count0 = 1  # 初始对应prefix[0] = 0，f值为0
    count1 = 0
    result = 0
    for num in nums:
        current_xor ^= num
        # 计算置位比特数的奇偶性
        parity = current_xor.bit_count() % 2  # Python 3.10+高效写法
        # 兼容旧版本：parity = bin(current_xor).count('1') % 2
        if parity == 1:
            result += count0
            count1 += 1
        else:
            result += count1
            count0 += 1
    return result

示例验证 #

比如输入nums = [1,2]：

• 遍历第一个元素1：current_xor=1，parity=1，result += count0(1) → result=1，count1=1
• 遍历第二个元素2：current_xor=1^2=3，parity=0，result += count1(1) → result=2，count0=2
  最终返回2，对应满足条件的子数组[1]（异或结果1，1个置位）和[2]（异或结果2，1个置位），正确。

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