位运算和数学

位运算的基本知识

进制

进制的概念

任何一种进位制都有一个基数，基数为X的进位计数称为X进制，表示每一个数位上的数运算都是逢X进一。

对于一个X进制的数，其具体数值由其中的每个数码和数码所在的数位决定。整数部分从右往左的第m个数位表示的权重是$X^m$，其中m最小值为0；小数部分从左往右的第n个数位表示的权重是$X^{-n}$，其中n最小为1。

十进制的123.45可以写成如下形式：$123.45=1\times10^2+2\times10^1+3\times10^0+4\times10^{-1}+5\times10^{-2}$

八进制的720.5可以写成如下形式：$720.5_{(8)}=7\times8^2+2\times8^1+0\times8^0+5\times8^{-1}$

常见的进制

二进制、八进制、十进制、十六进制

进制间的转换

非十进制转十进制

将非十进制数转成十进制数，只要将每个数位的加权和即可。

例如：八进制的720.5可以写成如下形式：$720.5_{(8)}=7\times8^2+2\times8^1+0\times8^0+5\times8^{-1}=464.625$

十进制转非十进制

将十进制转成X进制，需要对整数部分和小数部分分别转换。

对于整数部分，转换方式为将十进制的整数部分每次除以X直到变成0，并记录每次的余数，反向遍历每次的余数即可得到X进制表示。

例如：将十进制数50转成二进制：

$50/2=25…0;25/2=12…1;12/2=6…0;6/2=3…0;3/2=1/…1;1/2=0…1$

反向遍历得110010

对于小数部分，转换方式是将十进制的小数部分乘以X直到变成0，并记录每次的整数部分，正序遍历每次的整数部分即可得到X进制表示。

例如：将十进制数0.6875转成二进制

$0.6875\times2=1.375整1;0.375\times2=0.75整0;0.75\times2=1.5整1;0.5\times2=1整1$

正向遍历得到1011。

需要注意的是，在一种进制下的有限小数，转成另一种进制之后可能变成无限循环小数。例如十进制数0.2转成二进制数是0.0011。

其他进制间的转换

如果需要在两个不同的非十进制之间转换，常规思路是先转成十进制，再转成目标进制数。在一些特殊情况下，也可以不经过十进制，直接进行转换。

一位八进制可以表示成三位二进制，一位十六进制可以表示成四位二进制。

整数在计算机中的表示方式

计算机中的二进制

计算机采用的是二进制，二进制包括两个数码：0，1

一位二进制数可能取值有2个，k位二进制数的可能取值就有$2^k$个

有符号整数和无符号整数

计算机中的数据类型包括有符号类型和无符号类型，有符号类型的整数称为有符号整数，无符号类型的整数称为无符号整数。

• 有符号整数的取值范围包括负整数、零、正整数，无符号的整数取值范围包括零和正整数，不包括负整数
• 在位数相同的情况下，有符号整数可以表示的最大值比无符号整数小了一半
• 在对于k位整数，有符号整数的取值范围是$-2^{k-1}到2^{k-1}-1$，无符号整数的取值范围是$0到2^{k}-1$

原码、补码和反码

机器数和真数

一个数在计算机中的二进制表示形式称为这个数的机器数。机器数是有符号数，机器数的最高位是符号位，0表示0或者整数，1表示负数。

以八位二进制数为例。十进制数+10转换成二进制数是00001010，十进制数-10转换成二进制数是10001010。这里二进制数为机器数。

例如10001010的形式值是138，真正数值是-10，形式值和真正数值是不同的。为了加以区分，将机器数的真正数值称为机器数的真值。

原码

原码是机器数的符号位加上机器数的真值的绝对值，最高位是符号位，其余表示数值。

以八位二进制为例：+10的原码是00001010，-10的原码是10001010。

八位二进制的原码表示的最大值是01111111，即+127，最小值是11111111，即-127，因此八位二进制的原码表示的取值范围为-127到127。

反码

反码是在原码的基础上得到的。

0和正数的反码与原码相同，负数的反码为将原码的除了符号位之外的每一位取反。

以八位二进制为例：

• +10的原码是00001010；反码是00001010
• -10的原码是10001010；反码是11110101

补码

补码是在反码的基础上得到的。

0和正整数的补码与原码、反码相同，负数的补码是在反码的基础上+1得到的。

以八位二进制为例：

• +10的原码是00001010；反码是00001010；补码是00001010
• -10的原码是10001010；反码是11110101；补码是11110110

计算机中的表示

原码存在的问题：

• 同时存在+0和-0的表示
• 用原码进行减法运算，会导致错误的结果

反码的引入，解决了源码的减法运算结果错误的问题，但是仍然没有解决存在+0和-0的问题。

补码的引入同时解决了减法运算错误和同时存在+0和-0的问题，而且可以多表示一个最小值。10000000表示-128

位运算的概念和性质

位运算概述

与、或、异或、取反、左移、右移

与、或、异或、取反

移位运算

移位运算按照移位方向可以分成左移或右移，按照是否带符号分类可以分成算术位移和逻辑位移。

左移运算的符号是<<。左移运算时，将全部二进制位向左移动若干位，高位丢弃，低位补0。对于左移运算，算数位移和逻辑位移是相同的。

右移运算的符号是>>。右移运算时，将全部二进制向右移动若干位，低位丢弃，高位的补位由算术位移或逻辑位移决定：

• 算术右移，高位补最高位
• 逻辑右移，高位补0

对于Java而言，不存在无符号类型，所有的表示整数的类型都是有符号类型，因此需要区分算术右移和逻辑右移。在Java中，算术右移的符号是>>，逻辑右移的符号是>>>

移位运算与乘除法的关系

左移运算对应乘法。将一个数左移k位，等价于将这个数乘以$2^k$。当乘数不是2的整数次幂时，可以将乘数拆成若干项2的整数次幂之和，例如$a\times6等价于(a<<2)+a(<<1)$。对于任意整数，乘法运算都可以用左移运算实现，但是需要注意溢出的情况。

算术右移运算对应除法运算。将一个数右移k位，相当于将这个数除以$2^k$。对于0和正数，将一个数右移K位，和这个数除以$2^k$等价。但对于负数来说是不等价的。

位运算性质

• 幂等律：a&a=a，a|a=a
• 交换律：a&b=b&a，a|b=b|a，$a\bigoplus b=b\bigoplus a$
• 结合律：(a&b)&c = a&(b&c)，(a|b)|c= a|(b|c)，$(a\bigoplus b)\bigoplus c=a\bigoplus(b\bigoplus c)$
• 分配律：(a&b)|c = (a|c)&(b|c)，(a|b)&c=(a&c)|(b&c)，$(a\bigoplus b) \& c=(a\&c)\bigoplus(b\&c)$
• 德·摩根律：~(a&b) = (~a)|(~b)，~(a|b)=(~a)&(~b)
• 取反运算性质：-1=~0，-a=~(a-1)
• 与运算性质：a&0=0，a&(-1)=a，a&(~a)=0
• 或运算性质：a|0=a，a|(~a)=-1
• 异或运算性质：$a\bigoplus0=a$，$a\bigoplus a=0$
• 其他性质：
  • a&(a-1)结果为将a的二进制表示的最后一个1变成0；
  • a&(-a)的结果为只保留a的二进制的最后一个1，其余的1都变成0。

七进制数

递归

class Solution {
    public String convertToBase7(int num) {
        //判断num是否小于0，小于则添-取反
        if(num < 0){
            return "-" + convertToBase7(-num);
        }
        //递归出口
        if(num < 7){
            return ""+num;
        }

        //递归调用
        return convertToBase7(num/7) + convertToBase7(num%7);
    }
}

迭代

class Solution {
    public String convertToBase7(int num) {
        //边界条件是否为0
        if(num == 0){
            return "0";
        }
        //判断正负号
        boolean negative = num < 0;
        //创建一个StringBuilder存放结果
        StringBuilder res = new StringBuilder();
        //对num取绝对值，保证为正
        num = Math.abs(num);
        //除7法
        while(num != 0){
            res.append(num%7);
            num /= 7;
        }

        //是否需要添加负号
        if(negative){
            res.append("-");
        }
        //结果需要反转
        return res.reverse().toString();
    }
}

数字转换为十六进制数

class Solution {
    public String toHex(int num) {
        //边界条件
        if(num == 0){
            return "0";
        }

        //创建一个StringBuilder用来存放结果
        StringBuilder res = new StringBuilder();
        //一个num整数可以表示为32位的二进制，也可以是8位的16进制
        //从高位每4位为一组遍历num
        for(int i = 7; i >= 0; i--){
            int val = (num >> (4 * i))&0xf;
            //过滤之前的0
            if(res.length() > 0 || val > 0){
                char ch = hexChar(val);
                res.append(ch);
            }
        }

        return res.toString();
    }

    //将数字转换成16进制字符
    private char hexChar(int val){
        if(val < 10){
            return (char)(val + '0');
        }else{
            return (char)(val - 10 + 'a');
        }
    }
}

位1的个数

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        //记录变化的次数
        int res = 0;
        while(n != 0){
            //n & (n-1)可以将最后一个1变为0,全部变为0时跳出
            n &= (n-1);
            res++;
        }

        return res;
    }
}

颠倒二进制位

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        //将32位二进制分成两个16，交换
        n = (n >>> 16) | (n << 16);
        //将32位二进制分成4个8，交换
        n = ((n & (0xff00ff00)) >>> 8) | ((n & (0x00ff00ff)) << 8);
        n = ((n & (0xf0f0f0f0)) >>> 4) | ((n & (0x0f0f0f0f)) << 4);
        n = ((n & (0xcccccccc)) >>> 2) | ((n & (0x33333333)) << 2);
        n = ((n & (0xaaaaaaaa)) >>> 1) | ((n & (0x55555555)) << 1);
        return n;
    }
}

两整数之和

class Solution {
    public int getSum(int a, int b) {
        while(a != 0){
            //非进位部分，两个数不同时为1，相同时为0，可以看作是异或
            int temp = a ^ b;
            //进位部分，两个数都是1才发生进位，可以看作是相与左移一位
            a = (a & b) << 1;
            b = temp;
        }

        return b;
    }
}

格雷码

class Solution {
    public List<Integer> grayCode(int n) {
        //确定格雷码的个数
        int N = (1 << n);
        //创建一个list存放结果
        List<Integer> res = new ArrayList<>();
        //格雷码的构建i ^ i/2
        for(int i = 0; i < N; i++){
            res.add(i ^ (i >> 1));
        }

        return res;
    }
}

数字范围按位与

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        //边界条件
        if(left == 0){
            return 0;
        }
        //记录右移的位数，找到公共前缀
        int count = 0;
        while(left != right){
            left >>= 1;
            right >>= 1;
            count++;
        }
        //左移count位
        return left << count;
    }
}

比特位计数

class Solution {
    public int[] countBits(int n) {
        //构建一个bp数组用于存放结果
        int[] dp = new int[n+1];
        //记录上一次只含有1个1的数字
        int hightBit = 0;
        for(int i = 1; i <= n; i++){
            if((i & (i-1)) == 0){
                hightBit = i;
            }
            //状态转移方程为：
            dp[i] = dp[i-hightBit]+1;
        }

        return dp;
    }
}

只出现一次的数字

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        //0异或a为a，a异或a为0，遍历异或整个数组则可以得出结果
        for(int num : nums){
            res ^= num;
        }

        return res;
    }
}

只出现一次的数字II

class Solution {
    public int singleNumber(int[] nums) {
        //定义出现一次的异或值和出现两个异或值
        int ones = 0, twos = 0;
        for(int num : nums){
            ones = ones ^ num & (~ twos);
            twos = twos ^ num & (~ ones);
        }

        return ones;
    }
}

只出现一次的数组III

class Solution {
    public int[] singleNumber(int[] nums) {
        //定义一个xor表示将数组全部异或的结果，其结果为两个数的异或值
        int xor = 0;
        for(int num : nums){
            xor ^= num;
        }

        //保留最低为的1
        int mask = xor & (-xor);

        //构建一个数组用于存放结果
        int[] res = new int[2];
        for(int num : nums){
            //把数组分为两部分，分别进行异或
            if((num & mask) == 0){
                res[0] ^= num;
            }else{
                res[1] ^= num;
            }
        }

        return res;
    }
}

2的幂

class Solution {
    public boolean isPowerOfTwo(int n) {
        //利用位运算的性质
        return n > 0 && (n & (n-1)) == 0;
    }
}

3的幂

class Solution {
    public boolean isPowerOfThree(int n) {
        //边界条件
        if(n <= 0){
            return false;
        }

        //模3判断是否为三的幂
        while(n % 3 == 0){
            n /= 3;
        }

        return n == 1;
    }
}

4的幂

class Solution {
    public boolean isPowerOfFour(int n) {
        //在2的幂条件上+模3为1的条件
        return n > 0 && (n & (n-1)) == 0 && n % 3 == 1;
    }
}

Pow(x,n)

class Solution {
    public double myPow(double x, int n) {
        //边界条件n为0则返回1.0
        if(n == 0){
            return 1.0;
        }
        //将n转为long型
        long N = n;
        //判断N的正负
        return N > 0 ? pow(x, N) : 1/pow(x, -N);
    }

    private double pow(double x, long n){
        //递归出口
        if(n == 0){
            return 1.0;
        }
        //递归调用
        double y = pow(x, (n>>1));
        //判断n是否为奇数还是偶数
        return n % 2 == 0 ? y*y : y*y*x;
    }
}

飞机座位分配概率

class Solution {
    public double nthPersonGetsNthSeat(int n) {
        return n == 1 ? 1.0 : 0.5;
    }
}

矩形重叠

class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        //判断面积是否为0，若面积为0则返回false,只有面积大于0才可能有重合
        if(rec1[0] == rec1[2] || rec1[1] == rec1[3] || rec2[0] == rec2[2] || rec2[1] == rec2[3]){
            return false;
        }
        //只有当水平坐标重合且竖直坐标重合才会重合
        return (rec1[0] < rec2[2] && rec1[2] > rec2[0]) && (rec1[1] < rec2[3] && rec1[3] > rec2[1]);
    }
}

矩形面积

class Solution {
    public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        //第一块矩形的面积
        int area1 = (ax2 - ax1) * (ay2 - ay1);
        //第二块矩形的面积
        int area2 = (bx2 - bx1) * (by2 - by1);
        //重叠部分的长和宽
        int width = Math.min(ax2, bx2) - Math.max(ax1, bx1);
        int heigh = Math.min(ay2, by2) - Math.max(ay1, by1);
        //重叠的面积
        int area3 = Math.max(width, 0) * Math.max(heigh, 0);
        return area1 + area2 - area3;
    }
}

缀点成线

class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        //边界条件若只有两个点则为true
        if(coordinates.length == 2){
            return true;
        }
        //Y的增量
        int delY = coordinates[1][1] - coordinates[0][1];
        //X的增量
        int delX = coordinates[1][0] - coordinates[0][0];

        for(int i = 2; i < coordinates.length; i++){
            //当前Y的增量
            int curDelY = coordinates[i][1] - coordinates[0][1];
            //当前X的增量
            int curDelX = coordinates[i][0] - coordinates[0][0];

            if((delY * curDelX) != (curDelY * delX)){
                return false;
            }
        }

        return true;
    }
}

有效的正方形

class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        //满足四个点是不同的点
        if(p1[0] == p2[0] && p1[1] == p2[1]){
            return false;
        }
        if(p1[0] == p3[0] && p1[1] == p3[1]){
            return false;
        }
        if(p1[0] == p4[0] && p1[1] == p4[1]){
            return false;
        }
        if(p2[0] == p3[0] && p2[1] == p3[1]){
            return false;
        }
        if(p2[0] == p4[0] && p2[1] == p4[1]){
            return false;
        }
        if(p3[0] == p4[0] && p3[1] == p4[1]){
            return false;
        }

        //计算各点之间的距离
        int[] dis = new int[6];
        dis[0] = computerDis(p1, p2);
        dis[1] = computerDis(p1, p3);
        dis[2] = computerDis(p1, p4);
        dis[3] = computerDis(p2, p3);
        dis[4] = computerDis(p2, p4);
        dis[5] = computerDis(p3, p4);
        //对距离排序
        Arrays.sort(dis);
        //有四个距离应该相同
        if(dis[0] != dis[1] || dis[1] != dis[2] || dis[2] != dis[3]){
            return false;
        }else if(dis[4] != dis[5]){
            return false;
        }else{
            return true;
        }
    }
    //计算距离
    private int computerDis(int[] p1, int[] p2){
        return (p2[0] - p1[0]) * (p2[0] - p1[0]) + (p2[1] - p1[1]) * (p2[1] - p1[1]);
    }
}

计算质数

class Solution {
    public int countPrimes(int n) {
        //使用筛选法
        //构建一个n个数的数组用于做标记
        int[] isPrime = new int[n];
        //用1填充，表示为素数
        Arrays.fill(isPrime, 1);
        //构建一个存放结果的计数器
        int count = 0;
        //遍历数，进行选择和筛选
        for(int i=2; i < n; i++){
            if(isPrime[i] == 1){
                count++;
                //将其进行以i为倍数进行排除
                if((long)i * i < n){
                    for(int j = i * i; j < n; j+=i){
                        isPrime[j] = 0;
                    }
                }
            }
        }

        return count;
    }
}

检查【好数组】

class Solution {
    public boolean isGoodArray(int[] nums) {
        int divisor = nums[0];
        for(int i = 1; i < nums.length && divisor != 1; i++){
            divisor = gcd(divisor, nums[i]);
        }
        //数组中最大公约数为1，则是好数组
        return divisor == 1;
    }

    //辗转相除法求公约数
    private int gcd(int num1, int num2){
        while(num2 != 0){
            //记录num1
            int temp = num1;
            //记录num2
            num1 = num2;
            //num2重新赋值为num1%num2
            num2 = temp % num2;
        }

        return num1;
    }
}

不同路径

class Solution {
    public int uniquePaths(int m, int n) {
        //组合数学
        //创建一个res用来存放结果
        long res = 1;
        for(int x = n, y = 1; y < m; x++, y++){
            res = res * x / y;
        }

        return (int)res;
    }
}

杨辉三角

class Solution {
    public List<List<Integer>> generate(int numRows) {
        //创建一个res用来存放结果
        List<List<Integer>> res = new ArrayList<>();
        //遍历每一层
        for(int i = 0; i < numRows; i++){
            //创建一个List数组存放每一层的数
            List<Integer> list = new ArrayList<>();
            //遍历每一层添加数字
            for(int j = 0; j <= i; j++){
                //每一行的最前和最后都添加1;
                if(j == 0 || j == i){
                    list.add(1);
                    //其他位置上为上一层该位置和其上一层位置前一个的和
                }else{
                    list.add(res.get(i-1).get(j) + res.get(i-1).get(j-1));
                }
            }

            //存储当前层
            res.add(list);
        }

        return res;
    }
}

杨辉三角II

class Solution {
    public List<Integer> getRow(int rowIndex) {
        //创建一个List用于粗放结果
        List<Integer> res = new ArrayList<>();
        res.add(1);
        for(int i = 1; i <= rowIndex; i++){
            //利用同一行相邻组合数的关系
            res.add((int)((long)res.get(i-1) * (rowIndex - i + 1) / i));
        }

        return res;
    }
}

巴什博弈

class Solution {
    public boolean canWinNim(int n) {
        //不是4的倍数必胜
        return n % 4 != 0;
    }
}

除数博弈

class Solution {
    public boolean divisorGame(int n) {
        //赢的是面对的偶数
        return n % 2 == 0;
    }
}

石子游戏

class Solution {
    public boolean stoneGame(int[] piles) {
        //先手必胜
        return true;
    }
}

你可以获得的最大硬币数目

class Solution {
    public int maxCoins(int[] piles) {
        //将数组paixu
        Arrays.sort(piles);
        //res用于存放结果
        int res = 0;
        //取的总次数
        int epoche = piles.length / 3;
        //第一次取的位置
        int index = piles.length - 2;
        //每次取最大的2个数和一个最小的数
        for(int i = 1; i <= epoche; i++){
            res += piles[index];
            //每一次取得位置为上一次取的位置的前2个
            index -= 2;
        }

        return res;
    }
}