剑指 Offer II 004. 只出现一次的数字

题目

给你一个整数数组nums ，除某个元素仅出现一次外，其余每个元素都恰出现三次。请你找出并返回那个只出现了一次的元素。

示例 1：
输入：nums = [2,2,3,2]
输出：3

示例 2： 输入：nums = [0,1,0,1,0,1,100]
输出：100

提示：

1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums 中，除某个元素仅出现一次外，其余每个元素都恰出现三次

进阶：
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

注意：本题与主站137题重复

题解

public int singleNumber(int[] nums) {
    int result = 0;

    // 从第31位开始 符号位也要判断
    for (int i = 31; i >= 0; i--) {
        int cnt = 0, bit = 1 << i;
        for (int num : nums) {
            // 来判断位元是否为0 若存在符号位 结果为负数
            if ((bit & num) != 0) {
                cnt++;
            }
        }

        // 计算int所有为中1出现的次数 对3取余 剩余的就是只出现了一次的数字
        if (cnt % 3 != 0) {
            // 数字累加
            result |= bit;
        }
    }

    return result;
}