博客

位运算解析

位运算是以二进制为单位的运算，其操作数和运算结果都是整数值。以下列举一些相对常遇到或常使用的位运算符号。

一元运算符

二元运算符

LeetCode例题（更新ing）

136.只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？（空间复杂度为O（1））

示例 1:

输入: [2,2,1]

输出: 1

示例 2:

输入: [4,1,2,1,2]

输出: 4

解决思路

此题中除了一个特定元素只出现一次之外，其他所有元素出现两次，相同元素之间进行异或位运算（^）等于 0；将所有数组元素进行异或，得出的数值便是数组中只出现一次的数组元素

class Solution {
    public int singleNumber(int[] nums) {
        int len = nums.length;
        int sum = 0;
        for(int i=0;i<len;i++){
            sum = nums[i]^sum;
        }
        return sum;
    }
}

78.子集（位运算实现）

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]

输出:

[

[3],

[1],

[2],

[1,2,3],

[1,3],

[2,3],

[1,2],

[]

]

解题思路

可以给每个数组元素设置一个二进制的唯一“下标”，每次通过下标进行 **位与运算（&）**得出其中一个子集并加入子集数组中。

例如：一个数组的内容如下：{1，2，3}，给这个数组的每个元素设置二进制下标，则这个数组中共有000~111共 2^n -1 即2^3 -1个结果

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int len = nums.length;
		int n = (1<<len);
		List<List<Integer>> answer = new ArrayList<>();
		for(int i=0 ; i<n ;i++) {
			List<Integer> temp = new ArrayList<>();
			for(int j=0;j<len;j++) {	//将所有下标为1的元素加到temp中，形成所有子集的其中一个
				if((i&(1<<j)) != 0) {
					temp.add(nums[j]);
				}
			}
			answer.add(temp);
		}
		return answer;
    }
}