算法-位运算和位图

位运算

相关概念：

• 在Java中，int数据底层以补码形式存储，int型变量使用32bit存储数据，其中最高位是符号位，0表示正数，1表示负数

  • 为何要用补码：

    • 在计算机世界中，为了统一加法，减法之间的运算指令，使得计算机不用考虑两数相加和两数相减两套逻辑，用了补码的概念。

    • 补码：在补码的概念中，对二进制用了权重的概念，满足公式：

      $B2T_2\vec{x}=-x_{w-1}2^{w-1}+\sum_{i = 0}^{w-2} {x_i2^i}$，使的这个二进制表示的数值是由最高位的数和其低位的数之和，保证了这个数在正数和负数的情况下，都能用同一套逻辑处理，并且0也存在唯一值。

位级运算

• |:OR(或)，当p=1或q=1时，p|q等于1
• &:AND(与)，当p=1且q=1时，p&q等于1
• ~:NOT(反)，当p=0时，~p等于1
• ^:EXCLUSIVE-OR(异或)(又称无进位相加)：当p=1且q=0，或者p=0且q=1时，p^q等于1
  • 性质：
    1. 0^N = N
    2. N ^ N = 0
    3. 满足交换律和结合律

移位运算

• 左移位：$x<<k$,x向左移动k位，丢掉最高的k位
• 右移位：分为逻辑右移和算数右移。
  • $x>>>k$：逻辑右移，向右移动k位，左端补k个0
  • $x>>k$：算数右移，向右移动k位，左端补最高位

---

位运算相关算法

1.如何不用额外变量交换两个数

思路：

• 根据异或运算的三个性质，设变量a=x，b=y
  • a = x ^ y;
  • b = a ^ b = x ^ y ^ y = x;
  • a = a ^ b = x ^ y ^ x = y;
  • tips：a，b变量存储的都是一个地址的内容，导致a，b对该变量使用异或操作，第一步操作就将该内存地址的内容刷成0，导致数据有问题

public static void swap(int[] arr,int i ,int j){
    if (i == j){
        return;
    }
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

---

2.一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数

思路：

一：用hashMap存储数组，然后对数字个数+1,最后遍历hashMap，打印奇数的数子

二：用^异或运算，因为异或运算满足交换律和结合律，偶数的数字异或必定结果是0，奇数的数字最后结果是 0 ^ N = N,所以直接用异或运算即可

public static void printOddTimesNum1(int[] arr){
    int eor = 0;
   	for(int i = 0;i < arr.length;i++){
        eor ^= arr[i];
    }
    System.out.println(eor);
}

---

3.怎么把一个int类型的数，提取出最右侧的1来

思路：

a&(-a)=a&(~a+1):

• 首先对a取反，相当于a上的二进制位全部是相反的数，然后+1，就能确保原先a右侧都是0的情况，取反后变成1，在+1，则进位，直到原先a最右侧的1取反后的位置是0，然后进位变成1，又因为a & (-a)，则保证了最右侧1的位置的左侧全是0，右侧全是0

public static int rightOne(int x) {
     x = x & (-x);
     return x;
}

---

4.一个数组中又两种数出现了奇数次，其他数都出现了偶数次，

思路：

1. 假设奇数次是a和b，对数组中所有数做异或运算，eor = a ^ b;
2. 找到eor的二进制最右侧为1的数，设为x，
   • 根据x & arr[i] ！= 0这个特性，可以在数组中分出两个部分，一个部分该位置上是0，一个部分该位置上是1
3. x & arr[i] ！= 0，取onlyOne ^= arr[i],可以知道a -> onlyOne的值
4. 最后，根据a的值和a ^ b的值，可以推断出b的值

public static void printOddTimesNum2(int[] arr){
    int eor = 0;
    for(int i = 0;i<arr.length;i++){
        eor ^= arr[i];
    }
    int rightOne = eor & (~eor + 1);
    int onlyOne = 0;
    for(int i = 0;i<arr.length;i++){
        if((arr[i] & rightOne) != 0){
            onlyOne ^= arr[i];
        }
    }
    System.out.println(onlyOne + " " + (eor ^ onlyOne));
}

---

5.一个数组中有一种数出现k次，其他数都出现M次，找到出现了K次的数，

要求，额外空间复杂度O(1),时间复杂度O(N),M > 1,K < M

思路：

    1. 用HashMap记录数组中所有数字的词频，然后统计
    2. 声明一个数组，长度32，arr，0~31位置上分别记录每个数字对应的1的总数
            1. 对当前数组上每个位置进行判断，如果当前的累加值sum对M取余正好等于0，说明这个位置上的1正好都是k次的数。反之，则是M次的数的1.
            2. 遍历循环当前数组，假设ans = 0，分别对M次的数和ans做或运算，最后，就能得到M次的数

//这个方法用hashMap统计词频
public static int onlyKTimes(int[] arr,int k,int m){
    HashMap<Integer,Integer> map = new HashMap<>();
    for(int num :arr){
        if(map.containsKey(num)){
            map.put(num,map.get(num) + 1);
        } else {
            map.put(num,1);
        }
    }
    
    for(int num:map.KeySet()){
        if(map.get(num) == k){
            return num;
        }
    }
    return -1;
}



    
//这个方法是用32位数组统计对应的二进制位置上的情况
public static int onlyKTimes1(int[] arr,int k,int m){
    int[] t = new int[32];
    //t[0] 0位置的1出现了几个
    //t[i] i位置的1出现了几个
    for(int num:arr){
        for(int i = 0;i <= 31;i++){
            //if( (num>>i)&i) != 0){
                //t[i]++;
            //}
            t[i] += (num >> i) & 1;
        }
    }
    
    int ans = 0;
    for(int i = 0;i < 32; i++){
        ans |= (1 << i);
    }
    return ans;
}

---

6.两数相除

题目含义：

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/divide-two-integers 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

位运算加法：

1. 两个数a和b，a和b无进位相加用a^b获得，如果此时a和b没有进位数，则和是a异或b，

2. 如果有进位信息，则获取他的进位信息，进位信息是a&b<<1,

3. 拿进位数和无进位数相加，就能得到a和b的值

把第3步替换成1，2两步，就能得到a+b的值

public static int add(int a,int b){
    int sum = 0;
    while(b!=0){
        sum = a ^ b;
        b = (a&b)<<1; 
        a = sum;
    }
    return sum;
}

对整数取反：

就是补码运算：反码+1

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

两个整数相减：

$a-b=a+(-b)$

public static int minus(int a, int b){
    return add(a,negNum(b));
}

两正整数相乘：

$a * b$：相当于b的二进制表达式上凡是n=1的，取a <<n的值相加

对b的二进制表达式做循环，凡是n位上1的，对应的值是a << n,然后对所有n位上值是1的数相加

public static int multi(int a,int b){
    int res = 0;
    while(b != 0){
        if((b&1)!=0){
            res = add(res,a);
        }
        a << = 1;
        b >>> = 1;
    }
    return res;
}

两数相除,向下取整：

$a/b=c.....d$:如果$c=01110,d=0$,那么$a=2^1b+2^2b+2^3*b$

反过来，如果对a进行右移位操作，每次往右移一位，得到数$a'$,当$a'>b$,则能得到当前商二进制的1的位置，将这个二进制数位置赋值1，

然后拿$a-(b<<i)'$的值重复完成上述操作，直到最后取得的值小于b，就得到了商c

public static int div(int a,int b){
    int x = isNeg(a)?:negNum(a):a;
    int y = isNeg(b)?:negNum(b):b;
    int res = 0;
    for(int i = 30;i >= 0;i = minus(i,1)){
        if((x >> i)>y){
            res |= (1<<i);
            x = minus(x,y<<i);
        }
    }
    return isNeg(a) ^ isNeg(b)? negNum(res):res;
}

tips:b往左移1位，可能会越界到符号位，导致b<0的情况

两整数相除（考虑系统最小值边界情况）：

考虑系统最小值的边界情况：因为根据补码的定理，系统最小值是无法取相反数的

第一种情况：两数都是系统最小值，则返回1

第二种情况：b是系统最小值，因为向下取整，商必定返回0

第三种情况：a是系统最小值，

​ 第一种情况：b=-1，则直接返回系统最大值

​ 第二种情况：a是除数，b是被除数，拿a+1作为除数与b相除，得到c

​ $a/b = c ...... d$:再拿这个c和b相乘的数$c'$,拿$a-c'$的值d,去和b相除，得到余数1或0，相加，就是结果res

第四种情况：a不是系统最小，b不是系统最小。

public static int divide(int a, int b) {
    if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
        return 1;
    } else if (b == Integer.MIN_VALUE) {
        return 0;
    } else if (a == Integer.MIN_VALUE) {
        if (b == negNum(1)) {
            return Integer.MAX_VALUE;
        } else {
            int c = div(add(a, 1), b);
            return add(c, div(minus(a, multi(c, b)), b));
        }
    } else {
        return div(a, b);
    }
}

---

位图

概念

• 就是用一个bit位来标记某个元素所对应的value，而key即是该元素，由于BitMap使用了bit位来存储数据，因此可以大大节省存储空间。

实现

public class BitMap{
    
    private long[] bits;
    
    /**
    初始化位图，该位图是用long类型的数组存储数据，long类型有64位，意味着一个数组能存储64个数据。
    初始化的时候，填入你要存储的最大值，这个最大值用位运算进行运算，向右移6次，表明除64，+64则表明最起码有一个数组空间开辟出来
    */
    public BitMap(int max){
        bits = new long[(max + 64) >> 6];
    }
    
    /**
    num是你要添加的数，首先需要得到该数在数组中的哪个位置，num/64 = num >> 6 这步，可以得到该数据的位置。
    64的二进制：01000000
    63的二进制：00111111
    num % 64 = num & 63,因为要对当前num的64取余，则在二进制表明了凡是64的二进制1后面的数均是无法被整除的，也就是说与63进行&位运算，就能得到当前num的余数
    在将这个余数与num >> 6的上数组进行|或运算，凡是两个数中有一个是1的，则是1，这样就能不改变数组的情况下，标记该元素
    */
    public void add(int num){
        bits[num >> 6 ] |= (1L << (num & 63));
    }
    
    /**
   num >> 6 和 1L << (num & 63) 可以定位到该数据的具体位置，
   ~(1L << (num & 63))，对num的余数的标记位求反，则可以转化成非标志位均是1，标志位是0的情况
   在对这个数进行与运算，如果位图上该标志位是1，则变成0，并且其他标识位信息不变
    */
    public void delete(int num ){
        bits[num >> 6] &= ~(1L << (num & 63));
    }
    
    /**
   num >> 6 和 1L << (num & 63) 可以定位到该数据的具体位置的标识位，
   然后与位图进行与运算，如果标识位1，则是1，返回true，否则返回false
    */
    public boolean contains(int num){
        return (bits[num >> 6 ] & (1L << (num & 63))) != 0;
    }
}