漯河市源汇区建设局网站,网站开发主要内容,网站代码 商品添加分类,宁波网络营销推广外包公司Day 6#xff1a;位运算#xff08;异或性质、二进制操作#xff09; #x1f4d6; 一、位运算简介
位运算是计算机底层优化的重要手段#xff0c;利用二进制操作可以大大提高运算速度。常见的位运算包括#xff1a;
与#xff08;#xff09;#xff1a;a 位运算异或性质、二进制操作 一、位运算简介
位运算是计算机底层优化的重要手段利用二进制操作可以大大提高运算速度。常见的位运算包括
与a b如果两个二进制位都为 1结果为 1否则为 0。或|a | b如果两个二进制位中至少有一个为 1结果为 1否则为 0。异或^a ^ b如果两个二进制位不同结果为 1否则为 0。取反~~a按位取反0 变 11 变 0。左移a n将 a 的二进制表示向左移动 n 位相当于 a * 2^n。右移a n将 a 的二进制表示向右移动 n 位相当于 a / 2^n保留符号位。无符号右移不保留符号位即高位补 0。 二、只出现一次的数字Single Number 1. 题目描述
给定一个非空整数数组除了某个数字只出现一次以外其他数字均出现两次。请找出这个只出现一次的数字。
示例
输入: nums [4, 1, 2, 1, 2]
输出: 42. 思路与分析
利用异或运算 ^ 性质1a ^ a 0任意数与自身异或为 0。性质2a ^ 0 a任意数与 0 异或仍是自身。性质3异或满足交换律和结合律即 a ^ b ^ c a ^ c ^ b顺序无关。性质4a ^ b ^ b a某个数字 b 出现偶数次它们会相互抵消。
因此将所有数字进行异或操作所有成对出现的数字都会抵消为 0最终结果就是那个只出现一次的数字。 3. 代码实现只出现一次的数字
public class SingleNumber {public int findSingleNumber(int[] nums) {int result 0;for (int num : nums) {result ^ num; // 利用异或运算找出唯一的数}return result;}public static void main(String[] args) {SingleNumber solution new SingleNumber();int[] nums {4, 1, 2, 1, 2};System.out.println(只出现一次的数字: solution.findSingleNumber(nums)); // 输出 4}
}4. 代码讲解
result ^ num将数组中的所有数字进行异或。成对的数字会被消除只剩下唯一出现一次的数字。
✅ 时间复杂度O(n)只需遍历一次数组。 ✅ 空间复杂度O(1)只使用一个变量存储结果。 三、二进制中 1 的个数Hamming Weight 1. 题目描述
编写一个函数计算一个整数的二进制表示中 1 的个数。
示例
输入: n 9 (1001)
输出: 22. 思路与分析
方法 1️⃣位运算逐位检查
每次检查 n 的最低位是否为 1n 1。右移 n 一位n 1直到 n 变为 0。
方法 2️⃣n (n - 1) 高效算法
性质n (n - 1) 可以移除 n 最右边的 1这样 1 的个数就等于操作 n (n - 1) 多少次。 3. 代码实现方法 1逐位检查
public class HammingWeight {public int countOnes(int n) {int count 0;while (n ! 0) {count (n 1); // 检查最低位是否为1n 1; // 右移一位}return count;}public static void main(String[] args) {HammingWeight solution new HammingWeight();int n 9; // 二进制: 1001System.out.println(二进制中 1 的个数: solution.countOnes(n)); // 输出 2}
}4. 代码实现方法 2n (n - 1)
public class HammingWeightOptimized {public int countOnes(int n) {int count 0;while (n ! 0) {n (n - 1); // 清除最低位的1count;}return count;}public static void main(String[] args) {HammingWeightOptimized solution new HammingWeightOptimized();int n 9; // 二进制: 1001System.out.println(二进制中 1 的个数: solution.countOnes(n)); // 输出 2}
}5. 代码讲解
方法 1
时间复杂度 O(log n)因为 n 的二进制长度最多为 log n。空间复杂度 O(1)。
方法 2
时间复杂度 O(k)其中 k 是 n 中 1 的个数比 O(log n) 更快。空间复杂度 O(1)。
n (n - 1) 计算次数等于 1 的个数比 O(log n) 更快。 四、位运算总结
1. 常用位运算技巧
运算作用a 1判断 a 是否为奇数a(1 k)a ~(1 k)将 a 的第 k 位置 0a ^ (1 k)翻转 a 的第 k 位n (n - 1)清除 n 的最低位 1n (-n)获取 n 的最低位 1
2. 位运算的常见应用
判断奇偶数n 1 1奇数n 1 0偶数。求 n 的二进制中 1 的个数。交换两个数a a ^ b; b a ^ b; a a ^ b;不使用额外空间。判断 n 是否是 2 的幂n 0 (n (n - 1)) 0。 练习建议
理解异或运算的性质练习 只出现一次的数字。熟练掌握 n (n - 1)用于清除最低位 1 的优化技巧。多做位运算相关题目包括位掩码、二进制操作。
