算法 按位运算

按位与（Bitwise AND）和按位异或（Bitwise XOR）

按位与（&）

按位与是对两个数的二进制表示的每一位进行逻辑与操作。

规则：两个对应位都为1时，结果位才为1，否则为0。

示例：

5 & 35 的二进制：0101
3 的二进制：0011
-----------
按位与：0001 (即1)

按位异或（^）

按位异或是对两个数的二进制表示的每一位进行逻辑异或操作。

规则：两个对应位不同时，结果位为1，相同时为0。

示例：

5 ^ 35 的二进制：0101
3 的二进制：0011
-----------
按位异或：0110 (即6)

特性

按位与特性：

• x & 0 = 0
• x & x = x
• x & ~x = 0
• 可用于检查奇偶性：x & 1（结果为1则是奇数，0则是偶数）

按位异或特性：

• x ^ 0 = x
• x ^ x = 0
• x ^ y = y ^ x（交换律）
• (x ^ y) ^ z = x ^ (y ^ z)（结合律）
• 可用于交换两个变量的值（不使用临时变量）：

  a ^= b;
  b ^= a;
  a ^= b;
  

应用场景

按位与常见用途：

1. 掩码操作（提取特定位）
2. 判断奇偶性
3. 权限系统中检查权限

按位异或常见用途：

1. 交换两个变量的值
2. 加密算法
3. 查找唯一出现一次的数字（其他数字都出现两次）
4. 图形学中的颜色混合

这两种位操作在底层编程、算法优化和嵌入式系统中经常使用。

完整的按位运算

除了按位与（AND）和按位异或（XOR）外，还有以下几种常见的按位运算：

1. 按位或（Bitwise OR） |

对两个数的二进制表示的每一位进行逻辑或操作。

规则：两个对应位中只要有一个为1，结果位就为1。

示例：

5 | 35 的二进制：0101
3 的二进制：0011
-----------
按位或：0111 (即7)

特性：

• x | 0 = x
• x | x = x
• x | ~x = ~0（全1）
• 常用于设置特定位为1

2. 按位非（Bitwise NOT） ~

对一个数的二进制表示的每一位进行取反操作（一元运算符）。

规则：0变1，1变0。

示例：

~55 的二进制：0101
-----------
按位非：1010 (在4位表示中为-6，具体取决于数据类型长度)

注意：结果取决于数值的位数和表示方式（补码表示法）。

3. 左移（Left Shift） <<

将二进制数向左移动指定位数，右侧补0。

效果：相当于乘以2的n次方（无溢出时）。

示例：

5 << 25 的二进制：0101
左移2位：010100 (即20)

4. 右移（Right Shift） >>

将二进制数向右移动指定位数，左侧补符号位（算术右移）或补0（逻辑右移，取决于语言）。

效果：相当于除以2的n次方（向下取整）。

示例：

5 >> 15 的二进制：0101
右移1位：0010 (即2)

5. 无符号右移（Zero-fill Right Shift） >>>（某些语言如Java、JavaScript）

将二进制数向右移动指定位数，左侧总是补0。

示例：

-5 >>> 1 (在32位系统中)-5 的二进制：11111111111111111111111111111011
无符号右移1位：01111111111111111111111111111101 (一个大正数)

复合赋值运算符

所有位运算符都有对应的复合赋值形式：

• &= (按位与赋值)
• |= (按位或赋值)
• ^= (按位异或赋值)
• <<= (左移赋值)
• >>= (右移赋值)
• >>>= (无符号右移赋值)

应用总结

运算符	名称	用途示例
&	按位与	掩码操作、权限检查
l	按位或	设置特定位
^	按位异或	交换值、加密、找唯一数
~	按位非	取反操作
<<	左移	快速乘以2的幂
>>	右移	快速除以2的幂（算术右移）
>>>	无符号右移	处理无符号数的右移（逻辑右移）

这些位运算在底层编程、算法优化、嵌入式系统开发、图形处理和加密算法中都有广泛应用。

Java 实现：查找唯一出现一次的数字（其他数字都出现两次）

方法思路

1. 异或运算特性：

   • 任何数和 0 异或等于它本身：x ^ 0 = x ， 0 在异或运算中相当于“无影响”
   • 任何数和自身异或等于 0：x ^ x = 0
   • 异或运算满足交换律和结合律：a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

2. 算法步骤：

   • 初始化 result = 0。
   • 遍历数组，对每个元素执行 result ^= num。
   • 最终 result 就是唯一出现一次的数字。

代码实现

public class SingleNumber {public static int singleNumber(int[] nums) {int result = 0; // 初始时 result=0，不影响第一次运算for (int num : nums) {result ^= num;}return result;}public static void main(String[] args) {int[] nums = {4, 1, 2, 1, 2};System.out.println("唯一出现一次的数字是: " + singleNumber(nums)); // 输出: 4}
}

代码解释

1. 方法 singleNumber：

   • 初始化 result 为 0。
   • 使用增强 for 循环遍历数组 nums，对每个元素 num 执行异或操作 result ^= num。
   • 最终返回 result，即唯一出现一次的数字。

2. 主方法 main：

   • 定义一个测试数组 nums，其中 4 是唯一出现一次的数字。
   • 调用 singleNumber 方法并打印结果。

复杂度分析

• 时间复杂度：O(n)，只需遍历数组一次。
• 空间复杂度：O(1)，仅使用常数空间存储 result。

示例运行

输入：[4, 1, 2, 1, 2]
输出：唯一出现一次的数字是: 4

进阶问题

如果数组中有两个数字只出现一次，其他数字都出现两次，如何找出这两个数字？
提示：

1. 先异或所有数字得到 xorSum。
2. 找到 xorSum 的任意一个为 1 的位（如最低位的 1）。
3. 根据该位将数组分成两组，分别异或得到两个唯一数字。

Java 实现示例：

public static int[] findTwoSingleNumbers(int[] nums) {int xorSum = 0;for (int num : nums) {xorSum ^= num;}int diffBit = xorSum & -xorSum; // 找到最右边的不同位int[] result = new int[2];for (int num : nums) {if ((num & diffBit) == 0) {result[0] ^= num;} else {result[1] ^= num;}}return result;
}

二进制数1

牛客网 ： 二进制数1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class Main{public static void main(String[] args) throws IOException {BufferedReader br=new BufferedReader(new InputStreamReader(System.in));long lnum=Long.parseLong(br.readLine());br.close();System.out.println(Long.bitCount(lnum));}
}

二进制不同位数

牛客网 ： 二进制不同位数

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));String s = null;while ((s = reader.readLine()) != null) {String[] cs = s.split(" ");//int n = Integer.parseInt(s);//异或，相同是0，不同是1,先异或，再统计1的个数int a = Integer.parseInt(cs[0]);int b = Integer.parseInt(cs[1]);int c = a ^ b;int res=0;while (c!=0){res+=c&1;c=c>>>1;}System.out.println(res);}}}