第 1 天整数

1 整数除法

1、循环减除数法

2、循环减除数指数次递增

3、位运算

2 二进制加法

1. 模拟法

1.1 模拟2

3. 位运算（官方）（Python）

3 前 n 个数字二进制中 1 的个数

1. i & (i-1)思想

2. i & (i-1)类似DP

3. i / 2 思想

第 1 天整数

1 整数除法
剑指 Offer II 001. 整数除法https://leetcode-cn.com/problems/xoh6Oh/

1、循环减除数法

2、循环减除数指数次递增

package zxtp.Day01;


public class _001 {
    public static void main(String[] args) {
        System.out.println(new _001().divide(2, 1));
        System.out.println(new _001().divide(-2, 1));
        System.out.println(new _001().divide(22, 3));
        System.out.println(new _001().divide(22, -3));
        System.out.println(new _001().divide(-22, -3));
        System.out.println(new _001().divide(-22, 3));
        System.out.println(new _001().divide(Integer.MIN_VALUE, 1));
    }
    public int divide(int a, int b) {
        if(a == Integer.MIN_VALUE && b == -1 )
            return Integer.MAX_VALUE;

        int negative = 2;
        if(a > 0){
            negative--;
            a = -a;
        }
        if(b > 0){
            negative--;
            b = -b;
        }

        int result = divideCore(a, b);
        return negative == 1 ? -result : result;
    }
    public int divideCore(int a, int b){
        int result = 0;
        while(a <= b){
            int value = b;
            int quotient = 1;//商
            while(value >= 0xc0000000 && a <= value + value){
                quotient += quotient;
                value += value;
            }
            result += quotient;
            a -= value;
        }
        return result;
    }
}

三点：

java中输入16进制 0xc0000000 是0x 不是Ox负数个数那里可以优化一下不必像书中那样分出一个函数

class Solution { 
    public int divide(int a, int b) {
        if(a == 0x80000000 && b == -1 )
            return Integer.MAX_VALUE;

        int negative = (a > 0) ^ (b > 0) ? -1 : 1;
        if (a > 0) a = -a;
        if (b > 0) b = -b;
        int result = 0;
        while(a <= b){
            int value = b;
            int quotient = 1;//商
            while(value >= 0xc0000000 && a <= value + value){
                quotient += quotient;
                value += value;
            }
            result += quotient;
            a -= value;
        }
        return negative == 1 ? result : -result;
    } 
}

注意：

^运算，相同则为0，不同则为1。在三目运算符中，判断 1 即为 true 赋值negative 为 -1，0 为 false 赋值negative 为 1。

3、位运算

步骤其实和循环减法差不多不够巧用位运算，也是一个解决思路。通过右移a，来判断最合适那个移动次数i，用a减去b左移i次。res加上移动次数也就是商。

// 时间复杂度：O(1)
public int divide(int a, int b) {
    if (a == Integer.MIN_VALUE && b == -1)
        return Integer.MAX_VALUE;
    int sign = (a > 0) ^ (b > 0) ? -1 : 1;
    a = Math.abs(a);
    b = Math.abs(b);
    int res = 0;
    for (int i = 31; i >= 0; i--) {
        // 首先，右移的话，再怎么着也不会越界
        // 其次，无符号右移的目的是：将 -2147483648 看成 2147483648

        // 注意，这里不能是 (a >>> i) >= b 而应该是 (a >>> i) - b >= 0
        // 这个也是为了避免 b = -2147483648，如果 b = -2147483648
        // 那么 (a >>> i) >= b 永远为 true，但是 (a >>> i) - b >= 0 为 false
        if ((a >>> i) - b >= 0) { // a >= (b << i)
            a -= (b << i);
            res += (1 << i);
        }
    }
    // bug 修复：因为不能使用乘号，所以将乘号换成三目运算符
    return sign == 1 ? res : -res;
}

凡是不能用乘除法，或者要求优化乘除法的性能问题，都可以优先考虑位运算

借鉴作者：leetcoder-youzg 、作者：tangweiqun

’>>'表示右移，如果该数为正，则高位补0，若为负数，则高位补1；'>>>'表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0

2 二进制加法
剑指 Offer II 002. 二进制加法https://leetcode-cn.com/problems/JFETK5/

转换成整数加容易溢出！

1. 模拟法

按运算法则，从右到左，增加一个carry位（进位），计算sum和carry即可。

注意：

append后要记得反转最后要加一个判断进位是否需要append一个1

package zxtp.Day01;


public class _002 {
    public static void main(String[] args) {
        System.out.println(new _002().addBinary("11", "10"));
    }
    public String addBinary(String a, String b) {
        StringBuilder res = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
       while(i >= 0 || j >= 0){
            int digitA = i >= 0 ? a.charAt(i--) - '0' : 0;
            int digitB = j >= 0 ? b.charAt(j--) - '0' : 0;
            int sum = digitA + digitB + carry;
            carry = sum >= 2 ? 1 : 0;
            sum = sum >= 2 ? sum - 2 : sum;
            res.append(sum);
        }
        if(carry == 1)
            res.append(1);
        return res.reverse().toString();
    }
}

1.1 模拟2

和利用三目运算符判断求和是否大于等于2 不同，可以用%方法来计算。carry同理。

public String addBinary(String a, String b) {
        StringBuffer ans = new StringBuffer();

        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; ++i) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            ans.append((char) (carry % 2 + '0'));
            carry /= 2;
        }

        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();

        return ans.toString();
    }

遍历一遍即可。

3. 位运算（官方）（Python）

把 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:]

3 前 n 个数字二进制中 1 的个数
剑指 Offer II 003. 前 n 个数字二进制中 1 的个数https://leetcode-cn.com/problems/w3tCBm/

1. i & (i-1)思想

package zxtp.Day01;

import java.util.Arrays;


public class _003 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new _003().countBits(4)));
    }
    public int[] countBits(int num){
        int[] result = new int[num+1];
        for (int i = 0; i <= num; i++) {
            int j = i;
            while(j != 0){
                result[i]++;
                j = j & (j - 1);
            }
        }
        return result;
    }
}

2. i & (i-1)类似DP

利用整数i的二进制中1比i & (i-1)多一个的转移关系。

package zxtp.Day01;

import java.util.Arrays;


public class _003 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new _003().countBits(4)));
    }
    public int[] countBits(int num){
        int[] result = new int[num+1];
        for (int i = 1; i <= num; i++) {
            result[i] = result[i & (i - 1)] + 1;
        }
        return result;
    }
}

3. i / 2 思想

正整数i是一个偶数，那么i/2和i的二进制形式中1的个数相同。正整数i是一个奇数，那么i相当于i/2左移一位再将最右边设为1 ，i的二进制形式比i/2中多1个。

package zxtp.Day01;

import java.util.Arrays;


public class _003 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new _003().countBits(4)));
    } 
    public int[] countBits(int num){
        int[] result = new int[num+1];
        for (int i = 0; i <= num; i++) {
            result[i] = result[i>>1]+(i&1);
        }
        return result;
    }
}

注意：

位运算优化代码

i&1 计算奇偶性i>>2 计算 i/2

时间：22年01月21日 ~ 22年01月22日

阿翰剑指offer专项突破Day01

第 1 天整数

1 整数除法
剑指 Offer II 001. 整数除法https://leetcode-cn.com/problems/xoh6Oh/

1、循环减除数法

2 二进制加法
剑指 Offer II 002. 二进制加法https://leetcode-cn.com/problems/JFETK5/

转换成整数加容易溢出！

3 前 n 个数字二进制中 1 的个数
剑指 Offer II 003. 前 n 个数字二进制中 1 的个数https://leetcode-cn.com/problems/w3tCBm/

Java相关栏目本月热门文章

阿翰剑指offer专项突破Day01

第 1 天 整数

1 整数除法 剑指 Offer II 001. 整数除法https://leetcode-cn.com/problems/xoh6Oh/

1、循环减除数法

2 二进制加法 剑指 Offer II 002. 二进制加法https://leetcode-cn.com/problems/JFETK5/ 转换成整数加容易溢出！

3 前 n 个数字二进制中 1 的个数 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数https://leetcode-cn.com/problems/w3tCBm/

Java相关栏目本月热门文章

第 1 天整数

1 整数除法
剑指 Offer II 001. 整数除法https://leetcode-cn.com/problems/xoh6Oh/

2 二进制加法
剑指 Offer II 002. 二进制加法https://leetcode-cn.com/problems/JFETK5/

转换成整数加容易溢出！

3 前 n 个数字二进制中 1 的个数
剑指 Offer II 003. 前 n 个数字二进制中 1 的个数https://leetcode-cn.com/problems/w3tCBm/