Java中如何快速找出多位集合中唯一无重复的位

核心思路 #

要找出所有集合中仅出现一次的数字，本质是统计每个数字在所有集合中的出现次数，最终筛选出次数恰好为1的数字。利用位运算可以高效提取每个集合中的元素，避免冗余遍历：

• 计数跟踪：用数组（或哈希表）记录每个数字出现的集合次数，数组索引对应数字，值对应次数。
• 高效提取集合元素：对每个集合的位掩码，通过current & -current快速获取最低位的1，计算对应的数字后更新计数，再移除该位继续处理，直到掩码为0。
• 筛选结果：遍历计数容器，收集所有次数为1的数字。

Java 实现代码 #

import java.util.ArrayList;
import java.util.List;

public class UniqueBitFinder {
    public static List<Integer> findUniqueBits(long[] masks) {
        // 根据业务场景调整数字范围，此处假设最大数字不超过63
        int[] occurrenceCount = new int[64];
        
        for (long mask : masks) {
            long currentMask = mask;
            while (currentMask != 0) {
                // 提取当前掩码中最低位的1
                long lowestSetBit = currentMask & -currentMask;
                // 计算该位对应的数字（即2的多少次方）
                int num = Long.numberOfTrailingZeros(lowestSetBit);
                occurrenceCount[num]++;
                // 移除已处理的最低位
                currentMask ^= lowestSetBit;
            }
        }
        
        List<Integer> uniqueNums = new ArrayList<>();
        for (int i = 0; i < occurrenceCount.length; i++) {
            if (occurrenceCount[i] == 1) {
                uniqueNums.add(i);
            }
        }
        return uniqueNums;
    }

    public static void main(String[] args) {
        // 对应示例中的集合转换为位掩码
        long[] masks = {
            168,  // {3,5,7} → 2^3 + 2^5 + 2^7 = 8+32+128
            552,  // {3,5,9} →8+32+512
            552,  // {3,5,9}
            610,  // {1,5,6,9} →2+32+64+512
            736,  // {5,6,7,9} →32+64+128+512
            648   // {3,7,9} →8+128+512
        };
        System.out.println(findUniqueBits(masks)); // 输出 [1]
    }
}

优化说明 #

• 时间复杂度：O(N*K)，其中N是集合总数，K是每个集合的平均元素数，仅处理实际存在的元素，避免遍历所有可能数字。
• 扩展性：若数字范围超过64，可改用BigInteger处理掩码，并用HashMap<Integer, Integer>替代数组计数，保持高效性。
• 避免冗余操作：无需对集合进行两两组合的位运算（如AND/OR），直接聚焦每个数字的出现次数统计。

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