[剑指offer] 位运算篇

JZ65 不用加减乘除做加法⭐

 1 /* ^模拟不进位相加, &模拟进位(递归) */
 2 public class JZ65_1
 3 {
 4     public static int Add(int num1, int num2)
 5     {
 6         if (num2 == 0) return num1;
 7         return Add(num1 ^ num2, (num1 & num2) << 1);
 8     }
 9 }
10 
11 /* ^模拟不进位相加, &模拟进位(非递归) */
12 public class JZ65_2
13 {
14     public static int Add(int num1, int num2)
15     {
16         int add = num1 ^ num2;
17         int up = (num1 & num2) << 1;
18         while (up != 0)
19         {
20             add = add ^ up;
21             up = ((add ^ up) & up) << 1;
22         }
23         return add;
24     }
25 }

JZ15 二进制中1的个数

 1 /* 模拟1 */
 2 public class JZ15_1
 3 {
 4     public static int NumberOf1(int n)
 5     {
 6         int res = 0;
 7         while (n != 0)
 8         {
 9             if ((n & 1) == 1)
10                 res++;
11             n >>>= 1;
12         }
13         return res;
14     }
15 }
16 
17 /* ⭐模拟2⭐ */
18 public class JZ15_2
19 {
20     public static int NumberOf1(int n)
21     {
22         int res = 0;
23         while (n != 0)
24         {
25             n = n & (n - 1);
26             res++;
27         }
28         return res;
29     }
30 }
31 
32 /* 模拟3 */
33 public class JZ15_3
34 {
35     public static int NumberOf1(int n)
36     {
37         int res = 0;
38         for (int i = 0; i < 32; i++)
39         {
40             if ((n & (1 << i)) != 0)
41                 res++;
42         }
43         return res;
44     }
45 }
46 
47 /* 模拟4 */
48 public class JZ15_4
49 {
50     public static int NumberOf1(int n)
51     {
52         String s = Integer.toBinaryString(n);
53         return (int) s.chars().filter(c -> c == '1').count();
54     }
55 }

JZ16 数值的整数次方

 1 /* 减治 */
 2 public class JZ16_1
 3 {
 4     public static double Power(double base, int exponent)
 5     {
 6         if (exponent == 0)
 7             return 1;
 8         else if (exponent == 1)
 9             return base;
10         if (exponent == -1)
11             return 1.0 / base;
12         double half = Power(base, exponent / 2);
13         return half * half * Power(base, exponent % 2);
14     }
15 }
16 
17 /* 快速幂 */
18 public class JZ16_2
19 {
20     public static double Power(double base, int exponent)
21     {
22         if (exponent < 0)
23         {
24             base = 1 / base;
25             exponent = -exponent;
26         }
27         return quick(base, exponent);
28     }
29 
30     public static double quick(double base, int exponent)
31     {
32         double ans = 1;
33         while (exponent != 0)
34         {
35             if (exponent % 2 == 1) ans *= base;
36             exponent /= 2;
37             base *= base;
38         }
39         return ans;
40     }
41 }

JZ56 数组中只出现一次的两个数字⭐

 1 /* hash */
 2 public class JZ56_1
 3 {
 4     public static int[] FindNumsAppearOnce(int[] nums)
 5     {
 6         HashMap<Integer, Object> map = new HashMap<>();
 7         int[] res = new int[2];
 8         for (int num : nums)
 9         {
10             if (map.containsKey(num))
11                 map.remove(num);
12             else
13                 map.put(num, null);
14         }
15         ArrayList arrayList = new ArrayList(map.keySet());
16         res[0] = (int) arrayList.get(0);
17         res[1] = (int) arrayList.get(1);
18         return res;
19     }
20 
21 }
22 
23 /* 根据只出现一次的两个数字的异或结果的"1"位置作为分组条件 */
24 public class JZ56_2
25 {
26     public static int[] FindNumsAppearOnce(int[] nums)
27     {
28         int res1 = 0, res2 = 0, temp = 0, flag = 1;
29         for (int num : nums)
30             temp ^= num;
31         while (((temp & flag) ^ flag) != 0)
32             flag <<= 1;
33         for (int num : nums)
34         {
35             if ((num & flag) == 0)
36                 res1 ^= num;
37             else
38                 res2 ^= num;
39         }
40         return new int[]{Math.min(res1, res2), Math.max(res1, res2)};
41     }
42 }

JZ64 求1+2+3+...+n

1 /* 这题意义不大 */
2 public class JZ64_1
3 {
4     public static int Sum_Solution(int n)
5     {
6         boolean b = (n != 0) && ((n += Sum_Solution(n - 1)) > 0);
7         return n;
8     }
9 }