【Java算法专场】位运算（上）

常见位运算总结

了解位运算的一些基本操作，那么我们就来通过题目来巩固一下

位1的个数

算法思路

初始化：定义变量count来存储变量比特位1的个数。
遍历：利用上述第7条特性。当遍历不为0时，循环遍历，每次让变量按位与(n-1)，干掉最右侧的1，让count++.
返回结果：当遍历完成，返回count即可。

算法代码

/*** Solution类提供了一种计算整数的汉明重量的方法* 汉明重量是整数在二进制表示中1的个数*/
class Solution {/*** 计算给定整数的汉明重量* * @param n 整数输入，其汉明重量将被计算* @return 返回n的汉明重量*/public int hammingWeight(int n) {// 初始化计数器为0，用于记录汉明重量int count=0;// 当n不为0时，循环继续while(n!=0){// 使用n和n-1进行位操作，消除n二进制表示中的最后一个1n&=(n-1);// 每消除一个1，计数器增加1count++;}// 返回计数器的值，即汉明重量return count;}
}

时间复杂度为O(logn).

比特位计数

算法思路

初始化：定义一个长度为n+1的数组ans，用来存储结果。
计数方法：我们可以利用特性7n&(n-1)，来计算一个数二进制有多少个1，并利用变量ones来计数。
循环：从1开始遍历到n，每次循环都调用计数方法并将i传过去，将返回值放入到ans[i]中
返回ans：当遍历完成之后，返回ans数组即可。

算法代码

/*** Solution类提供了一种计算从0到给定数字n之间每个数字二进制表示中1的数量的方法*/
class Solution {/*** 计算从0到n每个数字的二进制表示中1的数量* * @param n 需要计算的范围上限* @return 一个整数数组，其中数组的第i个元素表示数字i的二进制表示中1的数量*/public int[] countBits(int n) {// 初始化答案数组，大小为n+1，以便包含从0到n的所有数字int[] ans = new int[n + 1];// 遍历从1到n的每个数字，计算并存储每个数字二进制表示中1的数量for (int i = 1; i <= n; i++) {ans[i] = countOne(i);}return ans;}/*** 计算给定数字x的二进制表示中1的数量* * @param x 需要计算的数字* @return 返回x的二进制表示中1的数量*/public int countOne(int x) {// 初始化计数器，用于记录1的数量int one = 0;// 循环直到x为0，每次迭代都会消除x二进制表示中最右侧的1while (x != 0) {// 使用位操作消除最右侧的1，位运算的结果将x的最右侧的1变为0x &= (x - 1);// 增加计数器，表示已经消除一个1one++;}// 返回计数器的值，即x二进制表示中1的总数return one;}
}

时间复杂度为O(n*logx),n为数组长度,x为数组元素值。

空间复杂度为O(n)

汉明距离

算法思路

初始化：定义变量n,并初始化为x^y，定义count并初始化为0，用来计算n的1的个数。
循环：当n不为0 时，通过特性7n&(n-1),每次干掉n最右侧的1，并让count++.
返回：当结束循环后，此时返回count即可。

算法代码

/*** Solution类提供了一个方法来计算两个整数之间的汉明距离* 汉明距离是指两个数的二进制表示中，不同位的数量*/
class Solution {/*** 计算两个整数x和y之间的汉明距离* * @param x 第一个整数* @param y 第二个整数* @return 返回x和y之间的汉明距离*/public int hammingDistance(int x, int y) {// 通过异或操作找出x和y不同的位，结果存储在n中int n = x ^ y;int count = 0;// 循环直到n为0，每次循环都会将n的最后一个1变为0，并增加计数while (n != 0) {// 利用n&(n-1)将n的最后一个1变为0，并进行与操作，以计算有多少个1n &= (n - 1);count++;}// 返回计数的结果，即汉明距离return count;}
}

时间复杂度为O(logn)，n为x^y的值，过程中只遍历到n二进制中1的数。

空间复杂度为O(1)，只用了常数个变量。

只出现一次的数字

算法思路

初始化：定义变量ans并初始化为0。
遍历数组：利用特性9，按位异或(^)数组每一个元素。
返回：当遍历完数组，返回ans即可。

算法代码

/*** Solution 类，提供数组操作的解决方案。*/class Solution {/*** 在一个数组中找出只出现一次的数字。* 使用按位异或运算来消除成对出现的数字，最终剩下的就是那个唯一的数字。* * @param nums 一个整数数组，其中每个元素除了一个之外都出现了两次。* @return 数组中只出现一次的那个元素。*/public int singleNumber(int[] nums) {// 初始化答案变量为 0，因为它是异或运算的身份元素。int ans = 0;// 遍历数组并对所有元素执行异或运算。for (int x : nums) {ans ^= x;}// 返回异或运算的结果，即我们要找的答案。return ans;}
}

时间复杂度为O(n),n为数组长度

空间复杂度为O(1),只用了1个变量。

丢失的数字

算法思路

初始化：定义一个变量ans并初始化位0，用来存储缺失的数。
遍历：这里需要遍历两次，第一次从0遍历到n，遍历过程中ans^=i,第二次遍历数组中的元素，ans同样是ans^=nums[i]。
返回结果：当遍历完成之后，返回结果ans即可。

算法代码

/*** Solution类用于解决寻找缺失数字的问题*/
class Solution {/*** 使用异或操作查找缺失的数字* 该方法通过将数组中的每个元素与从0到n的每个数字进行异或操作，来找到缺失的数字* 异或操作具有自反性和交换律，因此所有数字都会被取消，除了那个缺失的数字** @param nums 一个包含从0到n的n个唯一数字的数组，其中一个数字缺失* @return 缺失的数字*/public int missingNumber(int[] nums) {// 初始化答案为0，因为异或操作需要一个起始值int ans = 0;// 获取数组长度，即nint n = nums.length;// 对数组中的每个元素进行异或操作for (int i = 0; i < n; i++) {ans ^= nums[i];}// 对从0到n的每个数字进行异或操作，包括缺失的数字for (int i = 0; i <= n; i++) {ans ^= i;}// 返回缺失的数字return ans;}
}

时间复杂度为O(n),n为数组长度

空间复杂度为O(1),只用了一个变量。

本篇就先到这了，下篇将讲解位运算在leetcode中的一些中等题目~

若有不足，欢迎指正~