3.9 位运算算法

主要是利用位运算解决一些巧妙的问题。

1 基础

位运算基础

符号	说明	特性
&	按位与	只要有0，返回0
|	按位或	只要有1，返回1
^	按位异或	相同返回0。不同返回1
~	按位取反	全部反转。不重复的数字
>>	右移
<<	左移

负数在计算机中使用补码表示，主要目标就是实现了最小值到最大值之间，位运算的连续性。

在字面数字运算中，-2 加1为-1，-1 加1为0，0+1为1。是连续计算的。
在二级制补码计算中。也满足上述的计算规则。1111表示-1，加一通过溢出一位，变为0000，成为0.

实际上-1是按位绝对值最大的数，即1111。

特殊性质

操作	性质
n & (n - 1)	n中的最后一个1变成0。
n & (~n + 1) n&(n^(n-1))	lowbit()运算，n中最后一个1保留。
(~n) + 1== -n	计算机中补码表示的-n。位运算取反
n/2	等价于 右移一位 n >> 1
n*2	等价于 左移一位 n << 1
n % 2	等价于 判断二进制最右一位值 n & 1

2 常见算法

快速幂

• 使用二进制方法，将幂转换成二进制。二进制每个位的权重就是可以递推计算，与二分法效果相同。

double myPow(double x, int n) {
    long long N=n;
    if(N<0){
        x=1/x;
        N=-N;
    }
    double result=1;
    double temp=x;
    while(N!=0){
        if( N & 1)
            result=result*temp;
        temp *=temp;
        N= N>>1;
    }
    return result;

• 使用二分法、递归的方式求解快速幂。

//数学类题目。使用快速幂
long long multi(long long x,int n){
    if(n == 0) return 1;
    if(n == 1) return x;
    long long half = multi(x, n / 2);
    long long mod = multi(x, n % 2);
    return (half * half * mod)%1000000007;
}

快速乘法

• 二进制的列竖式思想。

int quickMulti(int A, int B) {
    int ans = 0;
    while(B) {
        if (B & 1) ans += A;
        A <<= 1;
        B >>= 1
    }
    return ans;
}

快速加法

• 利用按位与和按位异或运算。求解加法。
• 循环加余法。

int add(int a,int b){
    cout<<(unsigned int)-1<<endl;
    while(b != 0) { // 当进位为 0 时跳出
        int c = ((unsigned int)(a & b)) << 1;  // c = 进位
        a ^= b; // a = 非进位和
        b = c; // b = 进位
    }
    return a;
}

3 位运算与编码

• 编码有两种计算方式，一种是数值上计算负数的补码。另一种是按位运算计算负数的补码。前者是运算关系。后者是根据定义。

数值运算关系-补码

• $2^n$减去X的绝对值。X表示一个十进制数字。
• 负数越大，绝对值越小，减去的数越小，表示的值越大。
  $$
  (X)_b=
  \left{
  \begin{array}{lr}
  X & 0 \leq X < 2^{n-1}\
  2^{n} - |X| & -2^{n-1} < X \leq 0
  \end{array}
  \right.
  $$

位运算关系

• X表示十进制的负数。
  $$
  X = (\sim |X|)+1
  $$

• 为了满足数值计算，使得正数负数能够在同一的编码下进行加减计算。正数的机器数，原码，反码，补码，都是在固定字长下讨论的负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1。机器中只有加法而没有减法。

4 位运算实现加减乘除

1️⃣ 加法（Addition）

基本思路

加法的本质：
1. XOR(^)用来计算不进位的加法
2. AND(&)用来计算进位
3. 左移(<<)用来进位

例如：5 + 3 = 8
5 = 0101
3 = 0011

步骤1：不进位加法 (5 ^ 3)
0101 ^ 0011 = 0110 = 6

步骤2：进位 (5 & 3) << 1
(0101 & 0011) << 1 = 0001 << 1 = 0010 = 2

步骤3：继续加法 6 + 2
重复上述步骤直到进位为0

实现

public class BitwiseOperations {
    
    // ✅ 位运算实现加法
    public static int add(int a, int b) {
        while (b != 0) {
            // 计算进位
            int carry = (a & b) << 1;
            
            // 计算不进位的和
            a = a ^ b;
            
            // 进位加到结果中
            b = carry;
        }
        return a;
    }
    
    public static void main(String[] args) {
        System.out.println("5 + 3 = " + add(5, 3));      // 8
        System.out.println("10 + 20 = " + add(10, 20));  // 30
        System.out.println("-5 + 3 = " + add(-5, 3));    // -2
    }
}

/* 执行过程演示：5 + 3
第一次循环：
  a = 0101, b = 0011
  carry = (0101 & 0011) << 1 = 0010 = 2
  a = 0101 ^ 0011 = 0110 = 6
  b = 2

第二次循环：
  a = 0110, b = 0010
  carry = (0110 & 0010) << 1 = 0100 = 4
  a = 0110 ^ 0010 = 0100 = 4
  b = 4

第三次循环：
  a = 0100, b = 0100
  carry = (0100 & 0100) << 1 = 1000 = 8
  a = 0100 ^ 0100 = 0000 = 0
  b = 8

第四次循环：
  a = 0000, b = 1000
  carry = (0000 & 1000) << 1 = 0
  a = 0000 ^ 1000 = 1000 = 8
  b = 0

b = 0，退出循环
结果 a = 8
*/

简洁版本

public class BitwiseAdd {
    public static int add(int a, int b) {
        return b == 0 ? a : add(a ^ b, (a & b) << 1);
    }
    
    public static void main(String[] args) {
        System.out.println(add(5, 3));    // 8
        System.out.println(add(-1, 1));   // 0
    }
}

---

2️⃣ 减法（Subtraction）

基本思路

减法的本质：a - b = a + (-b)

-b的补码计算：
-b = ~b + 1

例如：5 - 3 = 5 + (-3) = 5 + (~3 + 1) = 5 + (-4) = 1
3 = 0011
~3 = 1100 = -4（补码表示）
-3 = ~3 + 1 = 1101 = -3

5 - 3 = 5 + (-3)（使用位运算加法）

实现

public class BitwiseSubtraction {
    
    // ✅ 位运算实现加法
    private static int add(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
    
    // ✅ 位运算实现减法
    public static int subtract(int a, int b) {
        // a - b = a + (-b)
        // -b = ~b + 1 = ~b + add(0, 1)
        return add(a, add(~b, 1));
    }
    
    public static void main(String[] args) {
        System.out.println("5 - 3 = " + subtract(5, 3));      // 2
        System.out.println("10 - 20 = " + subtract(10, 20));  // -10
        System.out.println("-5 - 3 = " + subtract(-5, 3));    // -8
    }
}

/* 执行过程演示：5 - 3
1. 计算 -3 = ~3 + 1
   ~3 = 1111...1100 （补码）
   ~3 + 1 = 1111...1101 = -3
   
2. 计算 5 + (-3) = 2
*/

简洁版本

public static int subtract(int a, int b) {
    return add(a, add(~b, 1));
}

---

3️⃣ 乘法（Multiplication）

基本思路

乘法的本质：a * b = a * (2^n + ... + 2^1 + 2^0)

例如：5 * 3 = 5 * 2 + 5 * 1 = 10 + 5 = 15

3 的二进制：0011
= 2^1 + 2^0
= 2 + 1

所以 5 * 3 = 5 * 2 + 5 * 1
           = 5 << 1 + 5 << 0
           = 10 + 5
           = 15

算法：
1. 检查b的每一位
2. 如果该位是1，就把a左移相应位数，加到结果中
3. 重复直到b变为0

实现

public class BitwiseMultiplication {
    
    private static int add(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
    
    // ✅ 位运算实现乘法
    public static int multiply(int a, int b) {
        if (b == 0) return 0;
        
        int result = 0;
        int absA = a < 0 ? add(~a, 1) : a;  // 获取绝对值
        int absB = b < 0 ? add(~b, 1) : b;
        
        // 遍历b的每一位
        while (absB != 0) {
            // 如果b的最低位是1
            if ((absB & 1) == 1) {
                result = add(result, absA);
            }
            
            // a左移，b右移
            absA = absA << 1;
            absB = absB >> 1;
        }
        
        // 处理符号
        if ((a < 0) ^ (b < 0)) {  // 异号
            result = add(~result, 1);
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println("5 * 3 = " + multiply(5, 3));      // 15
        System.out.println("5 * 0 = " + multiply(5, 0));      // 0
        System.out.println("-5 * 3 = " + multiply(-5, 3));    // -15
        System.out.println("5 * -3 = " + multiply(5, -3));    // -15
    }
}

/* 执行过程演示：5 * 3
5 = 0101
3 = 0011

第一次循环（b最低位是1）：
  result = 0 + 5 = 5
  absA = 5 << 1 = 10
  absB = 3 >> 1 = 1 (0001)

第二次循环（b最低位是1）：
  result = 5 + 10 = 15
  absA = 10 << 1 = 20
  absB = 1 >> 1 = 0

b = 0，退出
结果 = 15
*/

高效版本（利用左移快速乘以2）

public static int multiply(int a, int b) {
    if (b == 0) return 0;
    
    int result = 0;
    
    while (b != 0) {
        // 如果b的最低位是1
        if ((b & 1) == 1) {
            result = add(result, a);
        }
        
        a = a << 1;  // 相当于a * 2
        b = b >> 1;  // 相当于b / 2
    }
    
    return result;
}

---

4️⃣ 除法（Division）

基本思路

除法的本质：a / b = 找出最大的q，使得 b * q <= a

例如：15 / 3 = ?
找最大的q，使得 3 * q <= 15
3 * 5 = 15 <= 15 ✓
3 * 6 = 18 > 15 ✗
所以 15 / 3 = 5

使用二分查找或逐步减法：
15 - 3 = 12
12 - 3 = 9
9 - 3 = 6
6 - 3 = 3
3 - 3 = 0
共减了5次，所以15 / 3 = 5

实现版本1：逐步减法（效率低）

public class BitwiseDivision {
    
    private static int add(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
    
    private static int subtract(int a, int b) {
        return add(a, add(~b, 1));
    }
    
    private static int multiply(int a, int b) {
        if (b == 0) return 0;
        int result = 0;
        while (b != 0) {
            if ((b & 1) == 1) {
                result = add(result, a);
            }
            a = a << 1;
            b = b >> 1;
        }
        return result;
    }
    
    // ✅ 位运算实现除法（逐步减法）
    public static int divide(int a, int b) {
        if (b == 0) throw new ArithmeticException("除数不能为0");
        
        int absA = a < 0 ? add(~a, 1) : a;
        int absB = b < 0 ? add(~b, 1) : b;
        
        int result = 0;
        
        // 逐步减法
        while (absA >= absB) {
            absA = subtract(absA, absB);
            result = add(result, 1);
        }
        
        // 处理符号
        if ((a < 0) ^ (b < 0)) {
            result = add(~result, 1);
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println("15 / 3 = " + divide(15, 3));      // 5
        System.out.println("10 / 3 = " + divide(10, 3));      // 3
        System.out.println("20 / 4 = " + divide(20, 4));      // 5
    }
}

实现版本2：二分查找（效率高）⭐⭐⭐⭐⭐

public class BitwiseDivisionBinary {
    
    private static int add(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
    
    private static int subtract(int a, int b) {
        return add(a, add(~b, 1));
    }
    
    private static int multiply(int a, int b) {
        if (b == 0) return 0;
        int result = 0;
        while (b != 0) {
            if ((b & 1) == 1) {
                result = add(result, a);
            }
            a = a << 1;
            b = b >> 1;
        }
        return result;
    }
    
    // ✅ 位运算实现除法（二分查找，高效）
    public static int divide(int a, int b) {
        if (b == 0) throw new ArithmeticException("除数不能为0");
        
        boolean negative = (a < 0) ^ (b < 0);
        
        long absA = a < 0 ? -(long)a : a;
        long absB = b < 0 ? -(long)b : b;
        
        long result = 0;
        
        // 从高位到低位进行二分
        for (int i = 31; i >= 0; i--) {
            // 如果 absB << i <= absA，则第i位为1
            if ((absB << i) <= absA) {
                absA = subtract(absA, absB << i);
                result = result | (1L << i);  // 设置第i位为1
            }
        }
        
        return (int)(negative