位运算.md

基础异或

136. 只出现一次的数字

​ 287. 寻找重复数

巧妙位运算

231. 2的幂

有一些题除了用回溯法以外，还可以用迭代+位方法。

例如：

78. 子集

401. 二进制手表

位运算解题技巧

异或

一个数和它本身的异或运算等于0，0和一个数的异或运算等于它本身。

常用位运算：

• 将二进制中最右边的 1 设置为 0：n & (n - 1)。
• 获取二进制中最右边的 1：n & (n - 1) 另一种方法 n & (-n)。(n - 1)相当于补码，即-n
• 把二进制数的第i位变成1，其余位不变 a|=(1<<i)

指定位置的位运算 将X最右边的n位清零：x & (0 << n) 获取x的第n位值：(x >> n) & 1 获取x的第n位的幂值：x & (1 << n) 仅将第n位置为1：x | (1 << n) 仅将第n位置为0：x & ((1 << n)) 将x最高位至第n位（含）清零：x & ((1 << n) - 1) 将第n位至第0位（含）清零：x & (~((1 << (n + 1)) - 1))

基础异或

136. 只出现一次的数字

Difficulty: 简单

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

说明：

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

示例 1:

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

示例 2:

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

**思路：一个数和它本身的位运算等于0，0和一个数的位运算等于它本身。**因此所有数字异或运算一遍，最终结果是那个只出现一次的数。

public int singleNumber(int[] nums) {
    int res = 0;
    for (int num : nums) {
        res ^= num;
    }
    return res;
}

287. 寻找重复数

Difficulty: 中等

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n之间（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1,1]
输出：1

示例 4：

输入：nums = [1,1,2]
输出：1

提示：

• 2 <= n <= 3 * 10⁴
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

进阶：

• 如何证明 nums 中至少存在一个重复的数字?
• 你可以在不修改数组 nums 的情况下解决这个问题吗？
• 你可以只用常量级 O(1) 的额外空间解决这个问题吗？
• 你可以设计一个时间复杂度小于 O(n²) 的解决方案吗？

思路：把数组遍历的下标利用上，就和136. 只出现一次的数字一样了。

public int findDuplicate(int[] nums) {
    int res = 0;
    for(int i = 0; i < nums.length; i++){
        res = res ^ i;
        res = res ^ nums[i];
    }
    return res;
}

巧妙位运算

231. 2的幂

Difficulty: 简单

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

示例 1:

输入: 1
输出: true
解释: 20 = 1

示例 2:

输入: 16
输出: true
解释: 24 = 16

示例 3:

输入: 218
输出: false

思路：用位运算更简单。只有一位是1，其余位都是0。

• 获取二进制中最右边的 1：x & (-x)。
• 将二进制中最右边的 1 设置为 0：x & (x - 1)。

//常规方法
public boolean isPowerOfTwo(int n) {
    if (n == 0) {
        return false;
    }
    while (n % 2 == 0) {
        n /= 2;
    }
    return n == 1;
}

public boolean isPowerOfTwo(int n) {
    return n > 0 && n & (n-1)) == 0;
}

public boolean isPowerOfTwo(int n) {
    return n > 0 && ((n - (n & (-n))) == 0);
}