目录

• 1. 二进制及其基本位运算
• 2. 打印一个数字的32位信息
• 3. 不用中间变量交换两个数
• 4. 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数
• 5. 怎么把一个int类型的数，提取出最右侧的1来
• 6. 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么 找到并打印这两种数
• 7. 一个数组中有一种数出现K次，其他数都出现了M次 M>1。 K<M 找到，出现了K次的数 要求，额外空间复杂度(1)，时间复杂度O(N）
• 8. N皇后问题
• 9. 位图
• 10. 位运算实现加、减、乘、除
• 11 .资源限制技巧汇总

1. 二进制及其基本位运算

2. 打印一个数字的32位信息

/**
 * 位运算 >> 表示带符号位移  >>> 表示不带符号位移
 **/
public class PrintB {
    public static void print(int num) {
        for (int i = 31; i >= 0; i--) {
            System.out.print((num & (1 << i)) == 0 ? "0" : "1");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int num = 4;
        print(num);
    }
}

3. 不用中间变量交换两个数

• 异或 运算 可以理解为 无进位相加

  /**
  - 0 ^ N = N   N ^ N = 0
  - 满足 交换率  结合率
  - a ^ b = b ^ a 交换率
  - (a ^ b) ^ c =  a ^ (b ^ c)  结合率
  */
  
  public class Test {
      public static void main(String[] args) {
          int a = 1; 
          int b = 2;
          System.out.println(a); // 1
          System.out.println(b); // 2
          a = a ^ b; // a = 1 ^ 2
          b = a ^ b; // b = 1 ^ 2 ^ 2 = 1
          a = a ^ b; // a = 1 ^ 2 ^ 1 = 2
          System.out.println(a); // 2
          System.out.println(b); // 1
      }
  }
  
  * 约束条件， a  b 不能指向同一块内存区域
  

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

public class Test {
    //arr 中 只有一种数， 出现了基数次
    public static void printOddTimesNum1(int[] arr) {
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        System.out.println(eor);
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 1, 1, 2, 2, 3, 3, 3};
        printOddTimesNum1(arr);
    }
}	

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

public class Test {
    public static void main(String[] args) {
        int a = 7;
        int b = a & (~a + 1);// a & (-a)
        System.out.println(b);
    }
}

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

public class Test {
    public static void printOddTimesNum2(int[] arr) {
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        // eor = 3 ^ 4 
        // 提取 eor 最右侧二进制位 为 1
        int right = eor & (~eor + 1); // 可以肯定  3  4  中 二进制位 某一位肯定不相等  我们假设 提取 最右边的 1。
        int eor1 = 0;
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & right) == 1) {
                eor1 ^= arr[i]; //必然等于 3 ^ 4 中的一个数
            }
        }
        int a = eor1;
        int b = eor ^ eor1; //获取另一个数
        System.out.println(a);
        System.out.println(b);
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4};
        printOddTimesNum2(arr);
    }
}

7. 一个数组中有一种数出现K次，其他数都出现了M次 M>1。 K<M 找到，出现了K次的数 要求，额外空间复杂度(1)，时间复杂度O(N）

public class TestKM {
    public static int test(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 (Integer num : map.keySet()) {
            if (map.get(num) == k) {
                return num;
            }
        }
        return -1;
    }
    public static int onlyKTimes(int[] arr, int k, int m) {
        int[] t = new int[32];
        for (int num : arr) {
            // t[0] 0位置的1出现了几个
            // t[i] i位置的1出现了几个
            for (int i = 0; i < 32; i++) { //统计数组中 二进制位的个数  如果个数   % m != 0  说明 k 在该位上 为 1
                t[i] += (num >> i) & 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            if (t[i] % m != 0) {
                ans |= 1 << i;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {2, 2, 2, 4, 4, 4, 5, 5};
        int k = 2;
        int m = 3;
        System.out.println(onlyKTimes(arr, k, m));
        System.out.println(test(arr, k, m));
    }
}

8. N皇后问题

N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）。

public class Test {
    public static void main(String[] args) {
        int n = 7;
        long start = System.currentTimeMillis();
        System.out.println(start(n));
        long end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + "ms");

    }

    // 算几个 皇后
    public static int start(int n) {
        // 最多算 32 个皇后
        if (n < 1 || n > 32) {
            return 0;
        }
        int limit = n == 32 ? -1 : (1 << n) - 1;
        return process(limit, 0, 0, 0);
    }

    /**
     * 7皇后问题
     * limit : 0....0 1 1 1 1 1 1 1
     * 之前皇后的列影响  col
     * 之前皇后的左下影响  left
     * 之前皇后的右下影响  right
     */
    public static int process(int limit, int col, int left, int right) {
        //说明列 都填满了 算一种情况
        if (col == limit) {
            return 1;
        }
        //pos 中为一的位置 是你可以尝试去填 皇后的位置
        int pos = limit & (~(col | left | right));
        int res = 0;
        while (pos != 0) {
            //提取最右侧1 并且抹掉
            int rightOne = pos & (~pos + 1);
            pos = pos - rightOne;
            res += process(limit, col | rightOne, (left | rightOne) << 1, (right | rightOne) >>> 1);
        }
        return res;
    }
}

9. 位图

如果我们知道 数字的最大值， 使用位图存储可以节省 很大的空间

import java.util.HashSet;

public class Test {
    public static class BitMap {
        private long[] bits;

        public BitMap(int max) {
//            bits = new long[(max + 64) / 64];
            bits = new long[(max + 64) >> 6];
        }

        public void add(int num) {
//            bits[num / 64] |= 1L << (num % 64);
            bits[num >> 6] |= 1L << (num & 63);
        }

        public void delete(int num) {
//            bits[num / 64] &= ~(1L << (num % 64));
            bits[num >> 6] &= ~(1L << (num & 63));
        }

        public boolean contains(int num) {
//            return (bits[num / 64] & 1L << (num % 64)) != 0;
            return (bits[num >> 6] & (1L << (num & 63))) != 0;
        }
    }

    public static void main(String[] args) {
        System.out.println("测试开始");
        int testTimes = 1000000;
        int max = 1000000;
        BitMap bitMap = new BitMap(max);
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < testTimes; i++) {
            int num = (int) (Math.random() * (max + 1));
            double decide = Math.random();
            if (decide < 0.33) {
                bitMap.add(num);
                set.add(num);
            } else if (decide < 0.66) {
                bitMap.delete(num);
                set.remove(num);
            } else {
                if (bitMap.contains(num) != set.contains(num)) {
                    System.out.println("判断错误");
                    break;
                }
            }
        }
        for (int num = 0; num < max; num++) {
            if (bitMap.contains(num) != set.contains(num)) {
                System.out.println("判断错误");
                break;
            }
        }
        System.out.println("测试结束");
    }
}

10. 位运算实现加、减、乘、除

public class Test {
    public static void main(String[] args) {
        System.out.println(divide(31, 2));
    }

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

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

    //减法
    public static int minus(int a, int b) {
//        a - b = a + -b  = a + (~b + 1) = a + (add(~b,1))
        return add(a, negNum(b));
    }

    //乘法
    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;
    }

    public static boolean isNeg(int a) {
        return a < 0;
    }

    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);
            }
        }
        // 判断原始 a  b  符号位 是否相同  ， 如果不同结果 取 负数
        return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
    }

    //除法
    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 {
                // a / b
                // (a+1) / b = c
                // a - (b * c) = d
                // d / b = e
                // return c + e
                int c = div(add(a, 1), b);
                int e = div(minus(a, multi(c, b)), b);
                return add(c, e);
            }
        } else {
            return div(a, b);
        }
    }
}

11 .资源限制技巧汇总

1. 布隆过滤器用于集合的建立与查询，并可以节省大量空间
2. 一致性哈希解决数据服务器的负载管理问题
3. 利用并查集结构做岛问题的并行计算
4. 哈希函数可以把数据按照种类均匀分流
5. 位图解决某一范围上数字的出现情况，并可以节省大量空间
6. 利用分段统计思想、并进一步节省大量空间
7. 利用堆、外排序来做多个处理单元的结果合并