面试题56（二）：数组中唯一只出现一次的数字

从“异或为什么突然失效”开始

先预测：1、1、1、2、2、2、3中唯一值是3。若像上一小题那样把所有值直接异或，三个1异或后仍是1，三个2异或后仍是2，最终结果是1异或2异或3，也就是0，并非答案3。

原因是相同数字出现两次才会异或归零；出现三次等价于留下一个副本。本题明确要求找出**数组中唯一只出现一次的数字**，而其他数字都出现三次，必须换一种能让三份贡献消失的聚合方式。

对每个二进制位置独立统计1的数量，这称为。任意重复值出现三次时，它在每一位要么贡献0，要么贡献3；对3取余都会归零。

示例低三位的总计是0、4、4，分别对3取余得到0、1、1，重建二进制011即3。

每一位对3取余为何有效

把所有元素在第j位的1相加。每个三次重复值在该位贡献3乘0或3乘1，必定是3的倍数；唯一值若该位为1则额外贡献1，为0则不贡献。

因此该位总数除以3的余数，恰好等于唯一值在这一位的比特。这种让三份相同贡献在模3下归零称为。

每个位置得到的0或1称为。把所有余数按原位放回，就恢复完整整数。

这不是数值总和对3取余。整数加法会产生进位，不同位相互影响；位计数让32个位置独立处理，才不会丢失位模式。

忠实还原作者32位实现

作者用bitSum[32]保存从高位到低位的计数。扫描每个数字时，bitMask从最低位1开始，但循环下标j从31递减到0，因此最低位累加到bitSum[31]，最高位累加到bitSum[0]。

int FindNumberAppearingOnce(
    int numbers[],
    int length) {
    if (numbers == nullptr ||
        length <= 0) {
        throw new std::exception(
            \"Invalid input.\");
    }
 
    int bitSum[32] = {0};
    for (int i = 0; i < length; ++i) {
        int bitMask = 1;
        for (int j = 31; j >= 0; --j) {
            int bit =
                numbers[i] & bitMask;
            if (bit != 0) {
                bitSum[j] += 1;
            }
            bitMask = bitMask << 1;
        }
    }
 
    int result = 0;
    for (int i = 0; i < 32; ++i) {
        result = result << 1;
        result += bitSum[i] % 3;
    }
    return result;
}

重建时从bitSum[0]开始，每轮先左移已有结果，再加当前余数。32轮后，余数序列恢复为一个int位模式。

作者没有按数值大小或输入顺序做任何特殊处理。唯一值是最小、中间、最大、负数或0，都只影响各位余数。

负数依赖完整符号位

负数测试不是附带项，作者Test4到Test7系统覆盖唯一值为负、重复值为负、正负重复混合和全部为负。要恢复负数，最高也必须参与计数与重建。

以-10和三个214为例，214的每个置位都贡献3并在模3后消失；-10的32位补码模式完整留下，包括最高符号位，最终解释回-10。

不过作者代码对signed int执行左移。bitMask移入符号位、result逐步构造负数时，都可能触及有符号溢出或负值左移的未定义行为。测试在原Visual C++环境按预期工作，不代表这段写法符合所有现代C++实现。

可移植的固定宽度版本

现代实现应明确使用int32_t与uint32_t，把位运算放在无符号类型上，再用bit_cast按相同位模式解释回有符号值。

#include <array>
#include <bit>
#include <cstdint>
#include <span>
#include <stdexcept>
 
std::int32_t findNumberAppearingOnce(
    std::span<const std::int32_t> numbers) {
    if (numbers.empty()) {
        throw std::invalid_argument(
            \"numbers must not be empty\");
    }
 
    std::array<std::uint32_t, 32> sums{};
    for (std::int32_t value : numbers) {
        const std::uint32_t bits =
            std::bit_cast<std::uint32_t>(
                value);
        for (std::uint32_t bit = 0;
             bit < 32;
             ++bit) {
            sums[bit] +=
                (bits >> bit) & 1u;
        }
    }
 
    std::uint32_t resultBits = 0;
    for (std::uint32_t bit = 0;
         bit < 32;
         ++bit) {
        if (sums[bit] % 3u != 0) {
            resultBits |= 1u << bit;
        }
    }
    return std::bit_cast<std::int32_t>(
        resultBits);
}

这里bit索引0直接代表最低位，31代表符号位，不再用反向数组下标。无符号左移在位宽范围内定义明确，bit_cast只改变解释类型，不做数值转换。

固定int32_t与32个计数共同形成。若要支持64位整数，计数数组、循环上界和无符号类型都要一起改为64。

作者bitSum使用int并累计完整次数；若输入流极长，某一位的1数量可能超过int上限。算法最终只关心模3余数，可以在每次加1后立即执行计数对3取余，让每个槽始终只保存0、1、2，从根本上避免累计溢出。这样还可对不可回放数据流单遍处理：32个余数就是完整状态，流结束后直接重建结果，不需要保存历史元素。

分片并行时，每个工作节点也可输出32个局部模3计数，汇总端逐位相加再取模3。前提是所有分片使用相同位宽和整数编码，并对同一数据快照只处理一次；重复投递某个分片会改变模3频次，不能像幂等集合操作那样自动去重。

作者（边界条件）异常写法的边界

空指针或非正长度时，源码执行throw new std::exception。它抛出的是堆上异常指针，不是异常对象；若捕获方不负责delete，会泄漏。标准C++的std::exception也不保证接受字符串构造参数，这依赖旧MSVC扩展。

可移植写法应按值抛出std::invalid_argument，并按const引用捕获。或者让函数返回optional，使空输入不依赖异常控制流。

返回0不能表示失败，因为Test8的合法唯一值就是0。异常、optional或显式状态必须和数值结果分开。

契约损坏时余数代表什么

合法输入下，每个重复值出现三次，唯一值出现一次。若另一个值出现六次、九次，它的每位置位仍贡献3的倍数，也会消失；算法实际支持其他值出现任意3的倍数次。

若某值出现两次、四次或五次，它会留下模3余数并与唯一值按位叠加。结果可能恰好等于某个输入，也可能是从未出现过的位模式，函数不会报警。

多个只出现一次的值也会按位计数相加再模3，位上的进位不会跨位置，无法解释为普通整数和。位计数是求满足频次模3约束的聚合，不是完整频次验证器。

要验证“恰有一个值次数为1，其余次数为3”，需要哈希频次或排序扫描。那会使用O(u)空间或O(n log n)时间，其中u是不同值数量；是否验证由数据可信边界决定。

Test9为何七个零也能通过

作者Test9数组包含一个3467和七个0，而题面要求其他数字出现三次。七不是3的倍数，表面上违反契约。

但0的32个位全部为0，无论出现多少次都不给bitSum增加任何值，因此它对结果完全不可见，3467仍被重建。这个用例说明“零的任意频次不影响位计数”，不是一般值都可出现七次。

若把七个0换成七个5，5的每个置位贡献7，模3余1，会与3467混合并破坏答案。页面必须把这一特殊性限定在零，不能据此放宽所有重复值的频次约束。

状态机版本压缩32个计数

还可以让每一位在“出现次数模3为0、1、2”三个状态间转换，并用两个32位掩码ones与twos并行表示所有位。这仍是位级模3，只是把32个小计数压成两个位集合。

#include <bit>
#include <cstdint>
#include <span>
 
std::int32_t findOnceStateMachine(
    std::span<const std::int32_t> values) {
    std::uint32_t ones = 0;
    std::uint32_t twos = 0;
 
    for (std::int32_t value : values) {
        const std::uint32_t bits =
            std::bit_cast<std::uint32_t>(
                value);
        ones = (ones ^ bits) & ~twos;
        twos = (twos ^ bits) & ~ones;
    }
    return std::bit_cast<std::int32_t>(
        ones);
}

某位第一次出现进入ones，第二次从ones移到twos，第三次从twos清除，重新回到0。全部输入处理后，合法唯一值只出现一次，其置位保留在ones。

这版常数更小，但推导和调试难度更高。作者32计数版更适合教学、跨位观察和推广到“其他值出现m次”场景；工程中应优先选择团队能证明和维护的实现。

作者9组测试逐项还原

1. 正数中唯一值3最小。
2. 正数中唯一值4大小居中。
3. 正数中唯一值7最大。
4. 唯一值-10为负，重复值214为正。
5. 唯一值3467为正，重复值-209为负。
6. 重复值1024和-1025正负混合，唯一值1023。
7. 全部数字为负，唯一值-1023。
8. 唯一值为0，-23与214各出现三次。
9. 唯一值3467，零出现七次。

前3组覆盖正数大小位置，4到7覆盖符号位组合，8与9分别验证唯一零和重复零。作者没有调用空输入异常分支，也没有测试违反频次后应怎样处理。

#include <cassert>
 
void testNumberAppearingOnce() {
    int test1[] =
        {1, 1, 2, 2, 2, 1, 3};
    int test4[] =
        {-10, 214, 214, 214};
    int test6[] =
        {1024, -1025, 1024, -1025,
         1024, -1025, 1023};
    int test7[] =
        {-1024, -1024, -1024, -1023};
    int test8[] =
        {-23, 0, 214, -23,
         214, -23, 214};
    int test9[] =
        {0, 3467, 0, 0, 0, 0, 0, 0};
 
    assert(FindNumberAppearingOnce(
        test1, 7) == 3);
    assert(FindNumberAppearingOnce(
        test4, 4) == -10);
    assert(FindNumberAppearingOnce(
        test6, 7) == 1023);
    assert(FindNumberAppearingOnce(
        test7, 4) == -1023);
    assert(FindNumberAppearingOnce(
        test8, 7) == 0);
    assert(FindNumberAppearingOnce(
        test9, 8) == 3467);
}

随机对拍可选择一个唯一int32_t，再生成若干不同值各放三次并打乱；哈希频次参考应只找到该值。应显式加入INT32_MIN、INT32_MAX、-1和0，覆盖最高位与全1位模式。

对旧作者版做跨编译器测试时，负数用例可能暴露有符号移位差异；可移植无符号版应在相同数据上稳定一致。

本章练习

概念说明

数组中唯一只出现一次的数字，是其他数字都出现三次时仍唯一出现的值。逐位统计1的个数，每一位对3取余，就能恢复出只出现一次的数字。

本章回顾

1. 数组中唯一只出现一次的数字不能用直接异或解决，因为其他值出现三次。
2. 逐位统计1的个数后，每一位对3取余即可得到唯一值位模式。
3. 三次重复值在每一位都贡献3的倍数，模3后完全消失。
4. 作者固定32位并从高到低重建，负数依赖符号位。
5. 有符号左移和throw new std::exception不便携，应使用无符号位模式与按值异常。
6. 频次不合法时函数仍会给出聚合位模式，不是输入验证器。
7. Test9的七个零能通过只因零没有任何置位，不能推广到普通值。
8. 作者9组测试重点覆盖正负数与零，现代版还应测试整数极值。

名词解释