题解

思路

对每一个数不断除以 $2$：

• x % 2 是当前最低二进制位；
• 把它加入总计数；
• x /= 2 删除最低位。

所有数字处理完后，输出总数 ans 和 ans % 2。

也可以使用位运算 x & 1 和 x >>= 1，原理相同。

正确性说明

每次取模得到当前数的一位二进制数码，整除 $2$ 后转向下一位，因此循环恰好统计该数所有的 1。对全部输入累加后得到总数 $S$，而 $S\bmod2$ 正好按照题意给出校验码。

复杂度

每个数最多有 $8$ 个二进制位：

• 时间复杂度：$O(8n)=O(n)$；
• 空间复杂度：$O(1)$。