位运算：出现次数异常的数字（N次模型）

问题分类：出现次数异常

这类问题的核心是：数组中某些数出现了 k 次，其余数出现了 n 次，找出那些特殊的数。

只出现一次的数 II（LeetCode 137）

数组中除了一个数出现 1 次，其他所有数都出现 3 次，找出那个数。

方法 1：按位统计模 3

对每一位统计所有数 1 的个数，模 3 后即为目标数在该位的值。

int singleNumber(int[] nums) {
    int ans = 0;
    for (int i = 0; i < 32; i++) {
        int sum = 0;
        for (int num : nums) sum += (num >> i) & 1;  // 统计第 i 位的1的总数
        // sum % 3 是 0 或 1，即目标数在第 i 位的值
        if (sum % 3 != 0) ans |= (1 << i);
    }
    return ans;
}

时间：O(32n) = O(n)，空间：O(1)

方法 2：数字电路思维（位运算状态机）

用两个变量 ones 和 twos 作为每一位的状态：

• ones：某位出现了 1 次或 4 次...（模3余1）
• twos：某位出现了 2 次或 5 次...（模3余2）

每来一个新数 x：

新的 ones = 旧ones XOR x 的，但要减去已进入 twos 的位
新的 twos = 旧twos XOR x 的，但要减去已进入 threes（即全部消去）的位

# 状态转移：
ones = (ones ^ x) & ~twos
twos = (twos ^ x) & ~ones

int singleNumber(int[] nums) {
    int ones = 0, twos = 0;
    for (int num : nums) {
        ones = (ones ^ num) & ~twos;
        twos = (twos ^ num) & ~ones;
    }
    return ones;  // 最后 ones 存的就是出现1次的数
}

为什么正确：出现3次的数经过3轮后，ones 和 twos 对应位都清零（三次后状态回到00）。出现1次的数保留在 ones 中。

出现 k 次，其余 m 次（通用）

将模 2（XOR) 扩展到模 m：需要 ⌈log₂(m)⌉ 个变量来追踪每位的计数。

// 通用解法：找出现k次的数（其余数出现m次）
// 需要 bits = ceil(log2(m)) 个变量
int singleNumber_km(int[] nums, int k, int m) {
    int[] counters = new int[Integer.SIZE];  // 每一位用 int 追踪值(0到m-1)
    for (int num : nums) {
        for (int i = 0; i < Integer.SIZE; i++) {
            counters[i] += (num >> i) & 1;
            counters[i] %= m;  // 出现m次的归零
        }
    }
    int ans = 0;
    for (int i = 0; i < Integer.SIZE; i++) {
        if (counters[i] == k % m) ans |= (1 << i);  // 目标数出现k次
    }
    return ans;
}

只出现一次的数字（大数组找重复）

变体：找两个只出现奇数次的数（LeetCode 260）

扩展 XOR 方法：

int[] singleNumber(int[] nums) {
    int xor = 0;
    for (int n : nums) xor ^= n;  // xor = a ^ b

    // 找到 a 和 b 不同的某一位（选最低位的1）
    int diff = xor & (-xor);

    // 按 diff 位是否为1，分成两组各自 XOR
    int[] result = new int[2];
    for (int n : nums)
        result[(n & diff) == 0 ? 0 : 1] ^= n;

    return result;
}

出现次数超过 n/3 的数（LeetCode 229 摩尔投票扩展）

找出数组中所有出现次数超过 ⌊n/3⌋ 的元素（最多 2 个）：

List<Integer> majorityElement(int[] nums) {
    // 同时维护两个候选数
    int candidate1 = 0, count1 = 0;
    int candidate2 = 0, count2 = 0;

    for (int n : nums) {
        if (n == candidate1) {
            count1++;
        } else if (n == candidate2) {
            count2++;
        } else if (count1 == 0) {
            candidate1 = n; count1 = 1;
        } else if (count2 == 0) {
            candidate2 = n; count2 = 1;
        } else {
            count1--; count2--;  // 不同的三个数相互抵消
        }
    }

    // 验证候选数确实超过 n/3
    count1 = 0; count2 = 0;
    for (int n : nums) {
        if (n == candidate1) count1++;
        else if (n == candidate2) count2++;
    }

    List<Integer> result = new ArrayList<>();
    if (count1 > nums.length / 3) result.add(candidate1);
    if (count2 > nums.length / 3) result.add(candidate2);
    return result;
}

原理：超过 n/3 的数最多有 2 个。摩尔投票：三个不同的数相互抵消，最后留下的候选数就是多数元素。

字符出现次数 × 位运算（LeetCode 318）

最大单词长度乘积：找两个无公共字母的单词使长度乘积最大。

位掩码表示字母集合：用 int 的低 26 位表示 26 个字母：

int maxProduct(String[] words) {
    int n = words.length;
    int[] masks = new int[n];
    for (int i = 0; i < n; i++) {
        for (char c : words[i].toCharArray())
            masks[i] |= 1 << (c - 'a');  // 置对应字母位
    }

    int max = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if ((masks[i] & masks[j]) == 0)  // 无公共字母（AND = 0）
                max = Math.max(max, words[i].length() * words[j].length());
        }
    }
    return max;
}

优化：相同字母集合（掩码相同）只保留最长的词：

int maxProduct(String[] words) {
    Map<Integer, Integer> maskToLen = new HashMap<>();
    for (String word : words) {
        int mask = 0;
        for (char c : word.toCharArray()) mask |= 1 << (c - 'a');
        maskToLen.merge(mask, word.length(), Math::max);  // 相同掩码保留最大长度
    }

    int max = 0;
    List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(maskToLen.entrySet());
    for (int i = 0; i < entries.size(); i++) {
        for (int j = i + 1; j < entries.size(); j++) {
            if ((entries.get(i).getKey() & entries.get(j).getKey()) == 0) {
                max = Math.max(max, entries.get(i).getValue() * entries.get(j).getValue());
            }
        }
    }
    return max;
}

小结