算法 按位运算

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

按位与（&）

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

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

示例：

5 & 3

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

按位异或（^）

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

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

示例：

5 ^ 3

5 的二进制：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 | 3

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

特性：

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

2. 按位非（Bitwise NOT） ~

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

规则：0变1，1变0。

示例：

~5

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

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

3. 左移（Left Shift） <<

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

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

示例：

5 << 2

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

4. 右移（Right Shift） >>

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

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

示例：

5 >> 1

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

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

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

示例：

-5 >>> 1 (在32位系统中)

-5 的二进制：11111111111111111111111111111011
无符号右移1位：01111111111111111111111111111101 (一个大正数)

复合赋值运算符

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

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

应用总结

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

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);
        }
    }

}