Leetcode|位运算

常用位运算总结⁍

作用	公式	代码（JAVA）	举例
改变num第i位（1->0，0->1）	num^(1<<i)	num^=(1<<i)	num: 1001(9) i: 3 1<<i: 1000 –> num = 1
判断num的第i位是不是0	num&(1<<i) == 0		000001(0)000
获得一个二进制数最右边的一个1	b &(-b) = b&(~b+1)	num = b&(-b)	b: 10100 -b: 01100 –> num = 00100b
(接上)最右边的1在第几位		Integer.bitCount(num - 1)	num-1就相当于把1000变成了111，1的个数就相当于第几位（从0开始）
无进位相加	a^b	r = a^b	a: 1001(9) b: 1111(15) a^b: 110
计算（保存）进位	(a&b)<<1	c = (a&b)<<1	a&b: 1001 –> c: 10010(和列竖式一样，第1位和第4位进1，在和a^b相加继续操作)
将二进制数的最后一个1变成0(最后一个1，不是最后一位)	x&(x-1)	x = x&(x-1)	x: 1010 x-1: 1001 –> 1000
$2^n$	1<<n	1<<n	1000(8)(n=3)
0~(1111)的遍历		i< (1<<n)

剑指 Offer II 001. 整数除法⁍

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

注意：

• 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
• ⭐ 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2³¹, 2³¹−1]。本题中，如果除法结果溢出，则返回 2³¹ − 1

思路与注意事项

最大的正数为 2^31-1,最小的负数为 -2^31,如果将负数转化为正数会溢出，所以可以 将正数都转化为负数计算

注意处理成负数之后，后面的大于号小于号都要变！

当被除数大于除数时，继续判断是不是大于除数的 2 倍？ 4 倍？ 8 倍？…如果被除数大于除数的 2^k 倍，那么将被除数减去除数的 2^ k 倍，之后再重复以上步骤。

15=2*4+2*2+2*1=2*(4+2+1)=2*7

class Solution {

  public int divide(int a, int b) {
    if (a == Integer.MIN_VALUE && b == -1) {
      return Integer.MAX_VALUE;
    }
    if (b == -1) return -a;

    int negative = 1; //记录正负
    //如果两个都是负数，则negative=1
    //一正一负，则negative==0
    //都是正数，则negative=-1
    if (a > 0) {
      negative--;
      a = -a; //正数转成负数
    }
    if (b > 0) {
      negative--;
      b = -b;
    }

    int res = dev(a, b);
    return negative == 0 ? -res : res;
  }

  int dev(int a, int b) {
    if (a == b) return 1;
    if (a == 0 || a > b) return 0;
    int n = getShift(a, b);

    return (1 << n) + dev(a - (b << n), b);
  }

  int getShift(int a, int b) {
    int n = 0;
    while (a <= b && b >= (Integer.MIN_VALUE >> 1)) {
      int tmp = b << 1; //a>b,b就左移
      if (tmp < a) break;
      b = tmp;
      n++;
    }
    return n;
  }
}

剑指 Offer II 002. 二进制加法⁍

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

输入为 非空 字符串且只包含数字 1 和 0。

思路

• 把 a 和 b 转换成整型数字 x 和 y，在接下来的过程中，x 保存结果，y 保存进位。
• 当进位不为 0 时
  • 计算当前 x 和 y 的无进位相加结果：answer = x ^ y
  • 计算当前 x 和 y 的进位：carry = (x & y) << 1
  • 完成本次循环，更新 x = answer，y = carry
• 返回 x 的二进制形式

class Solution:
    def addBinary(self, a, b) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            answer = x ^ y
            carry = (x & y) << 1
            x, y = answer, carry
        return bin(x)[2:]#"0b101"去掉"0b"

JAVA递归写法： 但是Integer大小有限制，所以大数无法通过

class Solution {

  public String addBinary(String a, String b) {
    int na = Integer.parseInt(a, 2);
    int nb = Integer.parseInt(b, 2);
    return Integer.toBinaryString(addBin(na, nb));
  }

  public int addBin(int na, int nb) {
    if (nb == 0) {
      return na;
    }
    int ans = na ^ nb;
    int cin = (na & nb) << 1; //进位
    return addBin(ans, cin);
  }
}

剑指 Offer II 003. 前 n 个数字二进制中 1 的个数⁍

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int last = i & 1;//判断最后一位是不是1
            bits[i] = bits[i >> 1] + last;
        }
        return bits;
    }
}

Brian Kernighan 算法⁍

对于任意整数 x，令 $x=x_&(x-1)$，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到x 变成 0，则操作次数即为 x 的「一比特数」。

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            bits[i] = countOnes(i);
        }
        return bits;
    }

    public int countOnes(int x) {
        int ones = 0;
        while (x > 0) {
            x &= (x - 1);
            ones++;
        }
        return ones;
    }
}

O(nlogn)

剑指 Offer II 004. 只出现一次的数字 ⁍

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。

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

思路

考虑位运算

❌ nums.length最大是3*10^4，也不可能用一个数的各个位数表示某个数是否出现（python可以？）

• num出现1次，则a的第num位置1
• 如果a的第num位为1，说明num出现了第2/3次，置b的第num位为1
• 用a-b，返回的一定类似0001…000的数，最右边的1对应的位数只出现了一次的数
• 位运算置第i位为1： 与数 1 << i 进行按位异或运算即可
• 位运算计算最低位的1是第几位： 可以通过一些语言自带的函数得到这个最低位的 1 究竟是第几位（即 i值） bin©.count(“0”) - 1
• 位运算计算第i位是否是1： 与 1<< i 相与，看是不是i

❌ 无法处理负数，如果条件是正数。。或许可以考虑这种方法

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        a = 0
        b = 0
        for num in nums:
            i = 1<<num
            if((a&i)!=i):
                a^=i
            elif((b&i)!=i):
                b^=i
        c=a^b

        return bin(c).count("0") - 1

✔️ 依次确定每一个二进制位

统计所有数第i个二进制位的和，模3，最终得到结果的第i个二进制位

巧用题目条件，最多的位数

时间复杂度：$O(n \log C)$，其中 $n$ 是数组的长度，$C$ 是元素的数据范围，本题中就是 $\log C=\log 2^{32} = 32$

• 得到x的第i个二进制位： ((x>> i) & 1)

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int total = 0;
            for (int num: nums) {
                total += ((num >> i) & 1);
            }
            if (total % 3 != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
}

剑指 Offer 15. 二进制中 1 的个数(汉明重量)⁍

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

提示：

• 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
• 在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        return countOne(n);
    }

    public int countOne(int n){
        int k = 0;
        while(n!=0){
            n=n&(n-1);
            k++;
        }
        return k;
    }
}

每轮消去一个1，时间复杂度O(M)，M为1的个数

剑指 Offer 56 - I. 数组中数字出现的次数⁍

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

class Solution {
    public int[] singleNumbers(int[] nums) {
        int n = 0;
        for(int num:nums){
            n^=num;
        }// n = a^b
        
        int lastOne = n&(-n); // 保留n最右边（第i位）一个1
        int a = 0;
        for(int num:nums){
            if((lastOne&num)==0){ // 说明num第i位为0
                a^=num; // a第i位为0，区分与b
            }
        }
        int b = a^n;
        return new int[]{b,a};
    }
}

78. 子集⁍

每个数对应二进制数mask的1位

class Solution {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) { // 遍历0~（1111..1)2 n个1
            t.clear();
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) { // mask的第i个数为1的话，就加入nums[i]
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
}

287. 寻找重复数⁍

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

思路：

数每一位的1相加是否相等

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        maxBit = 1
        n = len(nums) - 1
        while (n>>maxBit) != 0:
            maxBit+=1
        ans = 0
        for bit in range(maxBit):
            # 计算每一位的和
            sum_n = 0
            sum_num = 1 if nums[0]&(1<<bit)!= 0 else 0 # 初始时加上第一个数
            for i in range(1,n+1):
                if i&(1<<bit) != 0:
                    sum_n += 1
                if nums[i]&(1<<bit) != 0:
                    sum_num += 1
            # sum_num-sum_n 就是第i位为0/1的数
            if sum_num>sum_n:
                ans |= 1<<bit
        return ans

有其他更好解法，见 [快慢指针](寻找重复数 - 寻找重复数 - 力扣（LeetCode） (leetcode-cn.com))