使用位运算实现加减乘除(+、-、*、/)及比较器的用法

一、使用位运算实现+、-、*、/

1 实现加法

我们分为两步：
第一步：先算出不带进位的结果
第二步：算出加之后的进位
不带进位 + 进位 = res

代码实现：

/** * 位运算实现加法 * @return */
 public static int add(int a, int b){
    
     int sum = a;
     //只要有进位b，就一直循环
     while(b != 0){
    
         sum = a ^ b;//a 与 b异或
         b = (a & b) << 1;//b表示进位，需要左移一位
         a = sum;
     }
     return sum;
 }

2 实现减法

减法思路其实很简单：直接加上相反数即可【在计算机底层：负数使用补码来存储的，补码：反码+1】

取相反数代码：

/** * 取相反数 * @param n * @return */
 public static int negNum(int n){
    
 // 相反数：取反 + 1；因为不能有加号，所以直接调用函数【负数在计算机中用补码表示】
     return add(~n, 1);
    }

减法代码：

/** * 减法 a - b * @param a * @param b * @return */
 public static int minus(int a, int b){
    
     return add(a, negNum(b));
 }

3 实现乘法

res = a * b
判断b最低位为是否为1，如果为1，加上a，然后b左移，a右移；
如果为0就直接跳过，b左移，a右移

乘法代码：

 /** * 乘法 * @param a * @param b * @return */
  public static int multi(int a, int b){
    
      int res = 0;
      while(b != 0) {
    
          if((b & 1) != 0){
    
              res = add(res, a);
          }
          a <<= 1;//a带符号右移
          b >>>= 1;//b不带符号左移
      }
      return res;
  }

4 实现除法

res = x / y
用x向y靠拢【防止y将符号位丢失】，找到小于等于y的最大值，然后减去该值

div代码（用于实现普通的除法）：

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;
        // x / y 用x取靠y，防止y将符号位移除
        //方法中不能使用-号，用函数代替
        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;
    }

除法代码：

a/ b:需要考虑最小值的情况【系统最小值转绝对值】
如果是最小值 / -1 结果会越界，因此我们将最小值+1，然后再除得到临时结果c，除完之后用a - (c * b) 得到差值e，用差值e除以b，得到补偿值d，将补偿值d与之前值c相加得到最后结果res

a / b
//a 是最小值， b是1
// (a + 1) / b = c
// a  - (c * b) = e
// e / b = d
// c + d = res

/** * 除法实现【解决系统最小值转绝对值问题】 a / b * @param a * @param b * @return */
 public static int divide(int a, int b){
    
     if(a == Integer.MIN_VALUE && b == Integer.MIN_VALUE){
    
         //两个都是最小值，直接返回1
         return 1;
     } else if (b == Integer.MIN_VALUE){
    
         // 如果除数是最小值，直接返回0
         return 0;
     } else if (a == Integer.MIN_VALUE){
    
         if(b == negNum(1)){
    
             // b如果是-1，直接返回最大值【规定】
             return Integer.MAX_VALUE;
         } else {
    
             //a 是最小值， b是1
             // (a + 1) / b = c
             // a - (c * b) = e
             // e / b = d
             // c + d = res
             int c = div(add(a, 1), b);
             return add(c, div(minus(a, multi(c,b)), b));
         }
     } else {
    
         return div(a, b);
     }
 }

二、 拓展：比较器的用法

通常我们在使用集合的时候，都会涉及到元素顺序的问题，通常来说，基本数据类型在java内部已经帮我们实现了，那么我们自己定义的类该如何排序呢？这个时候就会涉及到比较器【自定义比较器需要实现Comparator<>接口】

例如：我们自定义学生类，我们想要按照要求给学生排序

public static class Student{
    
   private String name;
   private Integer id;
   private Integer age;
   public Student(String name, Integer id, Integer age){
    
       this.name = name;
       this.id = id;
       this.age = age;
   }

   @Override
   public String toString() {
    
       return "Student{" +
               "name='" + name + '\'' +
               ", id=" + id +
               ", age=" + age +
               '}';
   }
}

• 重写compare方法后：
  返回负数：第一个参数在前
  返回正数：第二个参数在前
  返回0：顺序无所谓

/** * 根据id排序【id大的在前面】 */
 public static class MyIdComparator implements Comparator<Student>{
    

     //返回 负数：第一个参数在前面
     //返回 正数：第二个参数在前面
     //返回 0：谁在前面无所谓
     @Override
     public int compare(Student o1, Student o2) {
    
         return -(o1.id - o2.id);
     }
 }

此处我们拓展一下优先级队列：PriorityQueue，底层实现是小根堆（默认记住最小值）
同时，String的排序是根据字典序来排列，如果两个字符串长度相同，挨个比较；
如果不同，补齐之后再比较
①"abc" “bca”
②"bca" “bc”【长度不同，补齐（用最小字典序补）,“bc0”】

全部代码：

package com.ali.test;

import java.util.*;

public class ComparatorTest {
    

    public static class Student{
    
        private String name;
        private Integer id;
        private Integer age;
        public Student(String name, Integer id, Integer age){
    
            this.name = name;
            this.id = id;
            this.age = age;
        }

        @Override
        public String toString() {
    
            return "Student{" +
                    "name='" + name + '\'' +
                    ", id=" + id +
                    ", age=" + age +
                    '}';
        }
    }

    /** * 根据id排序【id大的在前面】 */
    public static class MyIdComparator implements Comparator<Student>{
    

        //返回 负数：第一个参数在前面
        //返回 正数：第二个参数在前面
        //返回 0：谁在前面无所谓
        @Override
        public int compare(Student o1, Student o2) {
    
            return -(o1.id - o2.id);
        }
    }

    public static void main(String[] args) {
    
        Student s1 = new Student("张三", 4, 43);
        Student s2 = new Student("李四", 1, 16);
        Student s3 = new Student("王五", 3, 25);
        Student s4 = new Student("赵六", 2, 20);
        List<Student> list = new ArrayList<Student>();
        list.add(s1);
        list.add(s2);
        list.add(s3);
        list.add(s4);
        //使用自己构建的比较器排序
        list.sort(new MyIdComparator());
        for (Student s : list) {
    
            System.out.println(s.name + " " + s.id + " " + s.age);
        }
        System.out.println("--------------");
        PriorityQueue<Integer> queue1 = new PriorityQueue<>();
        queue1.add(2);
        queue1.add(7);
        queue1.add(8);
        queue1.add(1);
        System.out.println(queue1.peek());//1 优先级队列（小根堆），默认堆顶是最小值

        //优先级队列
        PriorityQueue<Student> queue2 = new PriorityQueue<>(new MyIdComparator());
        queue2.add(s1);
        queue2.add(s2);
        queue2.add(s3);
        queue2.add(s4);
        System.out.println(queue2.peek());//Student{name='张三', id=4, age=43}
    }
}