Weitanai

# 位运算

# 1 基本原理

  • 1 位与运算技巧

  • 2 不用额外变量交换两个整数

# 2例题

  • 1 只出现一次的数字

  • 2 找出数组中缺失的那个数

  • 3 位1的个数

  • 4 数字范围按位与

  • 5 比特位计数

  • 6 两整数之和

位操作（Bit Manipulation）是程序设计中对位模式或二进制数的一元和二元操作。
在许多古老的微处理器上，位运算比加减运算略快，通常位运算比乘除法运算要快很多。
在现代架构中，情况并非如此：位运算的运算速度通常与加法运算相同（仍然快于乘法运算）。

位操作包括：
¬¬ 取反（NOT）
∩∩ 按位或（OR）
⊕⊕ 按位异或（XOR）
∪∪ 按位与（AND）


移位
移位是一个二元运算符，用来将一个二进制数中的每一位全部都向一个方向移动指定位，溢出的部分将被舍弃，
而空缺的部分填入一定的值。
移位又分为:
算术移位
逻辑移位

# 1 基本原理

  • 0s 表示一串 0，1s 表示一串 1。
x ^ 0s = x      x & 0s = 0      x | 0s = x
x ^ 1s = ~x     x & 1s = x      x | 1s = 1s
x ^ x = 0       x & x = x       x | x = x

  • 利用 x ^ 1s = ~x 的特点，可以将位级表示翻转；

  • 利用 x ^ x = 0 的特点，可以将三个数中重复的两个数去除，只留下另一个数。

  • 利用 x & 0s = 0 和 x & 1s = x 的特点，可以实现掩码操作。

  • 一个数 num 与 mask：00111100 进行位与操作，只保留 num 中与 mask 的 1 部分相对应的位。

  • 利用 x | 0s = x 和 x | 1s = 1s 的特点，可以实现设值操作。

  • 一个数 num 与 mask：00111100 进行位或操作，将 num 中与 mask 的 1 部分相对应的位都设置为 1。

# 1 位与运算技巧：

  • n&(n-1) 去除 n 的位级表示中最低的那一位。例如对于二进制表示 10110100，减去 1 得到 10110011，这两个数相与得到 10110000。
  • n&(-n) 得到 n 的位级表示中最低的那一位。-n 得到 n 的反码加 1，对于二进制表示 10110100，-n 得到 01001100，相与得到 00000100。
  • n-n&(~n+1) 去除 n 的位级表示中最高的那一位。

# 2 不用额外变量交换两个整数

a = a ^ b;

b = a ^ b;

a = a ^ b;

# 2

# 1 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]

输出: 1

示例 2:

输入: [4,1,2,1,2]

输出: 4

利用 x ^ x = 0 的特点，可以将数组中重复的两个数去除，只留下出现一次的数

利用 x ^ x = 0 的特点，可以将数组中重复的两个数去除，只留下出现一次的数

class Solution {
    public int singleNumber(int[] nums) {
        int len = nums.length;
        if(len == 1) return nums[0];
        int ans = nums[0];
        for(int i = 1; i<len; i++){
            ans ^=nums[i];
        }
        return ans;
    }
}

# 2 找出数组中缺失的那个数

268. Missing Number (Easy)

Input: [3,0,1]

Output: 2

public int missingNumber(int[] nums) {
    int ret = 0;
    for (int i = 0; i < nums.length; i++) {
        ret = ret ^ i ^ nums[i];
    }
    return ret ^ nums.length;
}

# 3 位1的个数

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

示例 1：

**输入：**00000000000000000000000000001011

**输出：**3

**解释：**输入的二进制串 **00000000000000000000000000001011** 中，共有三位为 '1'。

  • idea: n$(n-1) 消去低位的1， n为零为止。
class Solution{
public int hammingWeight(int n) {
    int sum = 0;
    while (n != 0) {
        sum++;
        n &= (n - 1);
    }
    return sum;
}
}

#

# 4 数字范围按位与

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

示例 1:

输入: [5,7]

输出: 4

示例 2:

输入: [0,1]

输出: 0

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        while(n>m) 
            n = n&(n-1);
        return n;
    }
}

# 5 比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

输入: 2

输出: [0,1,1]

示例 2:

输入: 5

输出: [0,1,1,2,1,2]

class Solution {
    public int[] countBits(int num) {
        int[] arr = new int[num+1];
        for(int i =0; i<=num; i++){
            arr[i] = pop(i);
        }
        return arr;
    }
    private int pop(int x){
        int count= 0;
        while(x != 0){
            count++;
            x&=(x-1);
        }
    
    return count;
  }
}

# 6 两整数之和

不使用运算符 + 和 - ，计算两整数 a 、b 之和。

示例 1:

输入: a = 1, b = 2

输出: 3

示例 2:

输入: a = -2, b = 3

输出: 1

a + b 的问题拆分为 (a 和 b 的无进位结果) + (a 和 b 的进位结果)
无进位加法使用异或运算计算得出
进位结果使用与运算和移位运算计算得出
循环此过程，直到进位为 0

class Solution {
    public int getSum(int a, int b) {
    //进位
    int jw = a & b;
        
    //相加位
    a  = a ^ b;
        
    while(jw != 0){
        //左移进位作为新的b
        b = jw << 1;
        //进位
        jw = a & b;
        //相加位
        a = a ^ b;
    }
    return a;
}
}

← 字符串 →