【位运算】常见位运算总结

常见位运算总结

位1的个数

191. 位1的个数

给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。
示例 1：
输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。
示例 2：
输入：n = 128
输出：1
解释：输入的二进制串 10000000 中，共有 1 个设置位。
示例 3：
输入：n = 2147483645
输出：30
解释：输入的二进制串 1111111111111111111111111111101 中，共有 30 个设置位。
提示：
1 <= n <= 231 - 1
进阶：
如果多次调用这个函数，你将如何优化你的算法？

方法一：逐位判断
根据 与运算 定义，设二进制数字 n ，则有：
若 n&1=0 ，则 n 二进制 最右一位 为 0 。
若 n&1=1 ，则 n 二进制 最右一位 为 1 。
根据以上特点，考虑以下 循环判断 ：
判断 n 最右一位是否为 1 ，根据结果计数。
将 n 右移一位（本题要求把数字 n 看作无符号数，因此使用 无符号右移 操作）。

public class Solution {public int hammingWeight(int n) {int res = 0;while (n != 0) {res += n & 1;n >>>= 1;}return res;}
}

复杂度分析：
时间复杂度 O(logn) ： 此算法循环内部仅有 移位、与、加 等基本运算，占用 O(1) ；逐位判断需循环 log₂ n 次，其中 log₂n 代表数字 n 最高位 1 的所在位数。
空间复杂度 O(1) ： 变量 res 使用常数大小额外空间。
方法二：巧用 n&(n−1)
(n−1) 作用： 二进制数字 n 最右边的 1 变成 0 ，此 1 右边的 0 都变成 1 。
n&(n−1) 作用： 二进制数字 n 最右边的 1 变成 0 ，其余不变。

public class Solution {public int hammingWeight(int n) {int res = 0;while (n != 0) {res++;n &= n - 1;}return res;}
}

复杂度分析：
时间复杂度 O(M) ： n&(n−1) 操作仅有减法和与运算，占用 O(1) ；设 M 为二进制数字 n 中 1 的个数，则需循环 M 次（每轮消去一个1），占用 O(M) 。
空间复杂度 O(1) ： 变量 res 使用常数大小额外空间。

比特位计数

338. 比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1：
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10
示例 2：
输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
提示：
0 <= n <= 105
进阶：
很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

方法一：枚举二进制为1的位
对于任意整数 x，令 x=x & (x−1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。
对于给定的 n，计算从 0 到 n 的每个整数的「一比特数」的时间都不会超过 O(logn)，因此总时间复杂度为 O(nlogn)。

class Solution {public int[] countBits(int n) {int[] bits=new int[n+1];for(int i=0;i<=n;i++){int ones=0;int x=i;while(x>0){x&=(x-1);ones++;}bits[i]=ones;}return bits;}
}

复杂度分析
时间复杂度：O(nlogn)。需要对从 0 到 n 的每个整数使用计算「一比特数」，对于每个整数计算「一比特数」的时间都不会超过 O(logn)。
空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。
方法二：动态规划——最低设置位
定义正整数 x 的「最低设置位」为 x 的二进制表示中的最低的 1 所在位。例如，10 的二进制表示是 1010 (2) ，其最低设置位为 2，对应的二进制表示是 10 (2) 。
令 y=x & (x−1)，则 y 为将 x 的最低设置位从 1 变成 0 之后的数，显然 0≤y<x，bits[x]=bits[y]+1。因此对任意正整数 x，都有 bits[x]=bits[x & (x−1)]+1。
遍历从 1 到 n 的每个正整数 i，计算 bits 的值。最终得到的数组 bits 即为答案。

class Solution {public int[] countBits(int n) {int[] bits = new int[n + 1];for (int i = 1; i <= n; i++) {bits[i] = bits[i & (i - 1)] + 1;}return bits;}
}

复杂度分析
时间复杂度：O(n)。对于每个整数，只需要 O(1) 的时间计算「一比特数」。
空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。

汉明距离

461. 汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
示例 1：
输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
示例 2：
输入：x = 3, y = 1
输出：1
提示：
0 <= x, y <= 231 - 1

前言
汉明距离广泛应用于多个领域。在编码理论中用于错误检测，在信息论中量化字符串之间的差异。
两个整数之间的汉明距离是对应位置上数字不同的位数。
根据以上定义，我们使用异或运算，记为 ⊕，当且仅当输入位不同时输出为 1。
计算 x 和 y 之间的汉明距离，可以先计算 x⊕y，然后统计结果中等于 1 的位数。
现在，原始问题转换为位计数问题。位计数有多种思路
方法一：内置位计数功能
思路及算法
大多数编程语言都内置了计算二进制表达中 1 的数量的函数。在工程中，我们应该直接使用内置函数。

class Solution {public int hammingDistance(int x, int y) {return Integer.bitCount(x ^ y);}
}

复杂度分析
时间复杂度：O(1)。不同语言的实现方法不一，我们可以近似认为其时间复杂度为 O(1)。
空间复杂度：O(1)。
方法二：Brian Kernighan 算法
思路及算法
该算法可以被描述为这样一个结论：记 f(x) 表示 x 和 x−1 进行与运算所得的结果（即 f(x)=x & (x−1)），那么 f(x) 恰为 x 删去其二进制表示中最右侧的 1 的结果。
基于该算法，当我们计算出 s=x⊕y，只需要不断让 s=f(s)，直到 s=0 即可。这样每循环一次，s 都会删去其二进制表示中最右侧的 1，最终循环的次数即为 s 的二进制表示中 1 的数量。

class Solution {public int hammingDistance(int x, int y) {int s = x ^ y, ret = 0;while (s != 0) {s &= s - 1;ret++;}return ret;}
}

复杂度分析
时间复杂度：O(logC)，其中 C 是元素的数据范围，在本题中 logC=log2³¹ =31
空间复杂度：O(1)
lowbit
熟悉树状数组的同学都知道，lowbit 可以快速求得 x 二进制表示中最低位 1 表示的值。
因此我们可以先将 x 和 y 进行异或，再统计异或结果中 1 的个数。

class Solution {int lowbit(int x) {return x & -x;}public int hammingDistance(int x, int y) {int ans = 0;for (int i = x ^ y; i > 0; i -= lowbit(i)) ans++;return ans;}
}

时间复杂度：O( C )，C 最多为 32
空间复杂度：O(1)

只出现一次的数字

136. 只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：
输入：nums = [2,2,1]
输出：1
示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：
输入：nums = [1]
输出：1
提示：
1 <= nums.length <= 3 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴
除了某个元素只出现一次以外，其余每个元素均出现两次。

方法一：位运算
如果不考虑时间复杂度和空间复杂度的限制，这道题有很多种解法，可能的解法有如下几种。

• 使用集合存储数字。遍历数组中的每个数字，如果集合中没有该数字，则将该数字加入集合，如果集合中已经有该数字，则将该数字从集合中删除，最后剩下的数字就是只出现一次的数字。
• 使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字。
• 使用集合存储数组中出现的所有数字，并计算数组中的元素之和。由于集合保证元素无重复，因此计算集合中的所有元素之和的两倍，即为每个元素出现两次的情况下的元素之和。由于数组中只有一个元素出现一次，其余元素都出现两次，因此用集合中的元素之和的两倍减去数组中的元素之和，剩下的数就是数组中只出现一次的数字。

上述三种解法都需要额外使用 O(n) 的空间，其中 n 是数组长度。
如何才能做到线性时间复杂度和常数空间复杂度呢？
答案是使用位运算。对于这道题，可使用异或运算 ⊕。异或运算有以下三个性质。

• 任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
• 任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
• 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

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

复杂度分析
时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
空间复杂度：O(1)。