本文所列题目来自 LeetCode 中国网站，属于算法面试中关于位运算的经典高频考题。题解由 Doocs 开源社区 leetcode 项目维护者提供。
目前已经有超过 50 位开发者参与了此项目，期待你的加入！
题目1
题目描述
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]输出：[2,10] 或 [10,2]
限制：
•2 <= nums <= 10000
解法
异或运算求解。
首先明确，两个相同的数异或之后的结果为 0。对该数组所有元素进行异或运算，结果就是两个只出现一次的数字异或的结果。找出这个结果中某个二进制位为 1 的位置，之后对数组所有元素进行分类，二进制位为 0 的异或到 a，二进制位为 1 的异或到 b，结果就是 a，b。
Python3
class Solution: def singleNumbers(self, nums: List[int]) -> List[int]: xor_res = 0 for num in nums: xor_res ^= num pos = 0 while (xor_res & 1) == 0: pos += 1 xor_res >>= 1 a = b = 0 for num in nums: t = num >> pos if (t & 1) == 0: a ^= num else: b ^= num return [a, b]
Java
class Solution { public int[] singleNumbers(int[] nums) { int xor = 0; for (int num : nums) { xor ^= num; } int pos = 0; while ((xor & 1) == 0) { ++pos; xor >>= 1; } int a = 0, b = 0; for (int num : nums) { int t = num >> pos; if ((t & 1) == 0) { a ^= num; } else { b ^= num; } } return new int[] {a, b}; }}
题目2
题目描述
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：
输入：nums = [3,4,3,3]输出：4
示例 2：
输入：nums = [9,1,7,9,7,9,7]输出：1
限制：
•1 <= nums.length <= 10000
•1 <= nums[i] < 2^31
解法
统计所有数字每个位中 1 出现的次数，对于某个位，1 出现的次数一定是 3 的倍数 +1 或 0。对这个数 %3 得到的结果就是那个出现一次的数字在该位上的值。
Python3
class Solution: def singleNumber(self, nums: List[int]) -> int: bits = [0 for _ in range(32)] for num in nums: for i in range(32): bits[i] += (num & 1) num >>= 1 res = 0 for i in range(32): if bits[i] % 3 == 1: res += (1 << i) return res
Java
class Solution { public int singleNumber(int[] nums) { int[] bits = new int[32]; for (int num : nums) { for (int i = 0; i < 32; ++i) { bits[i] += (num & 1); num >>= 1; } } int res = 0; for (int i = 0; i < 32; ++i) { if (bits[i] % 3 == 1) { res += (1 << i); } } return res; }}
题目3
题目描述
集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。
给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例 1:
输入: nums = [1,2,2,4]输出: [2,3]
注意:
1.给定数组的长度范围是[2, 10000]。
2.给定的数组是无序的。
解法
首先使用 1 到 n 的所有数字做异或运算，然后再与数组中的所有数字异或，得到的值就是缺失数字与重复的数字异或的结果。
接着计算中这个值中其中一个非零的位 pos。然后 pos 位是否为 1，将 nums 数组的元素分成两部分，分别异或；接着将 1~n 的元素也分成两部分，分别异或。得到的两部分结果分别为 a,b，即是缺失数字与重复数字。
最后判断数组中是否存在 a 或 b，若存在 a，说明重复数字是 a，返回 [a,b]，否则返回 [b,a]。
Python3
class Solution: def findErrorNums(self, nums: List[int]) -> List[int]: res = 0 for num in nums: res ^= num for i in range(1, len(nums) + 1): res ^= i pos = 0 while (res & 1) == 0: res >>= 1 pos += 1 a = b = 0 for num in nums: if ((num >> pos) & 1) == 0: a ^= num else: b ^= num for i in range(1, len(nums) + 1): if ((i >> pos) & 1) == 0: a ^= i else: b ^= i for num in nums: if num == a: return [a, b] return [b, a]
Java
class Solution { public int[] findErrorNums(int[] nums) { int res = 0; for (int num : nums) { res ^= num; } for (int i = 1, n = nums.length; i < n + 1; ++i) { res ^= i; } int pos = 0; while ((res & 1) == 0) { res >>= 1; ++pos; } int a = 0, b = 0; for (int num : nums) { if (((num >> pos) & 1) == 0) { a ^= num; } else { b ^= num; } } for (int i = 1, n = nums.length; i < n + 1; ++i) { if (((i >> pos) & 1) == 0) { a ^= i; } else { b ^= i; } } for (int num : nums) { if (num == a) { return new int[]{a, b}; } } return new int[]{b, a}; }}
题目4
题目描述
请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
示例 1：
输入：00000000000000000000000000001011输出：3解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000输出：1解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101输出：31解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
解法
n & (n - 1) 会消除 n 中最后一位中的 1。
Python3
class Solution: def hammingWeight(self, n: int) -> int: res = 0 while n: n &= (n - 1) res += 1 return res
Java
public class Solution { // you need to treat n as an unsigned value public int hammingWeight(int n) { int res = 0; while (n != 0) { n &= (n - 1); ++res; } return res; }}
