小挑战

计算机的底层并不存在我们生活中常用的加、减、乘、除；其底层都是通过位运算实现的，所以了解并掌握位运算是程序员不可或缺的能，本专题就带着大家一起联系位运算！

题目1

在java中你能输出一个int类型整数的二进制表示吗？

例如：

int 类型的整数1，输出为 0000 0000 0000 0000 0000 0000 0000 0001

int 类型的整数2，输出为 0000 0000 0000 0000 0000 0000 0000 0010

题目2

你能通过位运算设计一个Bitmap 吗？需要实现add，remove，check 方法。

题目3

你能通过位运算实现我们生活中常用的加法吗？

题目4

你能通过位运算实现我们生活中常用的减法吗？

题目5

你能通过位运算实现我们生活中常用的乘法吗？

题目6

你能通过位运算实现我们生活中常用的除法吗？

---------------------- 我是优美的分割线----------------------

题目1

在java中你能输出一个int类型整数的二进制表示吗？

例如：

int 类型的整数1，输出为 0000 0000 0000 0000 0000 0000 0000 0001

int 类型的整数2，输出为 0000 0000 0000 0000 0000 0000 0000 0010

参考题解：

 public static void printBinary(int num) {
        for (int i = 31; i >= 0; i--) {
            System.out.print((num & 1 << i) == 0 ? 0 : 1);
        }
        System.out.println();
    }

题目2

你能通过位运算设计一个Bitmap 吗？需要实现add，remove，check 方法。

参考题解：

public  class Bitmap {

    private long[] bits;
    private int size;

    public Bitmap(int size) {
        this.bits = new long[(size >> 6) + 1];
        this.size = size;
    }


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

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

    public boolean check(int num) {
        return (bits[num >> 6] & (1L << (num & 63))) != 0 ? true : false;
    }


}

TIPS：

1. num >> 6 等价于 num/64
2. num & 63 等价于 num%65
3. 将整数的每一个bit设置为1，可以利用 "|" （或运算）
4. 需要用 1L ，而不是1 ；因为long的长度是64个bit，而int的长度是32个bit
5. ~ （取反）是将包括符号位 0变1 ，1变0
6. 利用~ 后，再做& 可以将某位设置为0
7. 判断整型的某个bit是0还是1，可以与该位为1的数做&运算，
   然后判断结果是否等于0，如果等于0则该位为0，如果不等于0则该位为1

题目3

你能通过位运算实现我们生活中常用的加法吗？

参考题解：

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;
}

TIPS

关键点： 

熟悉^(抑或)运算；抑或相当于不进位的加法。

思路：

a+b = (a不进位加b) + (a与b相加的进位信息)；
不能用"+"，加法得循环转换成抑或。

题目4

你能通过位运算实现我们生活中常用的减法吗？

参考题解：

public static int neg(int n){
   return add(~n,1);
}

public static int minus(int a,int b){
   return add(a,neg(b));
}

TIPS：

关键点：获得b的相反数

思路：
a-b 等价于 a + b的相反数；

~b = -(b+1)
所以, b的相反数等于 ~b+1

题目5

你能通过位运算实现我们生活中常用的乘法吗？

参考题解：

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;
}

TIPS

乘法可以转换成加法，每位的计算结果相加，对应为的计算需要移位；

计算 b 的 1 位置：
  1 1 0
* 1 0 1
--------
  1 1 0

计算 b 的 0 位置：
  1 1 0 0
*     1 0
---------
  0 0 0 0

计算 b 的 1 位置：
  1 1 0 0 0
*         1
-----------
  1 1 0 0 0

结果相加

110 + 0000 + 11000 = 11110

代码的过程也是类似如此，判断b的低位是不是1，是累加a的值，然后a左移1位，
b无符号右移1位。

题目6

你能通过位运算实现我们生活中常用的除法吗？

参考题解：

public static int div(int a, int b){
    int x = isNeg(a)? neg(a): a;
    int y = isNeg(b)? neg(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);
        }
    }
    return isNeg(a) ^ isNeg(b) ? neg(res) : res;
}

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

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==neg(1)){
            return Integer.MAX_VALUE;
         }else{
            int c = div(add(a,1),b);
            return add(c,div(minus(a,multi(a,c)),b));
         }
    }else {
         return div(a,b);
    }
}

TISP

除法的实现过程有一个关键点是边界的处理：
1. 如果a，b都是int 类型最小值，则返回1
2. 如果b是int类型最小值，则返回0
3. 如果a是int类型最小值，因为除法的运算过程是不带符号位的，相当于绝对值运算；但是int类型的最小值取绝对值以后的数字，会溢出；
运算规则：a = c*b +x*b
所以 先执行a+1，结果再除以b得到c；
（a - c*b）/b = x
最终结果为： c+x
4. a与b均不是int类型最小指，正常运算。

除法示例运算过程:

1110000   =a = 64 + 32 + 16 = 92
/    10   =b = 2

== >

  1110000   =a 
/ 1000000   =b<<5
-------------- 
   110000

以上即代表 a = b*2的5次方 + 110000

== > 以下计算 110000 除以b

   110000
/  100000  =b<<4
----------------
    10000
至此：  a = b*2的5次方 + b*2的4次方 + 10000

== > 以下计算 10000 除以b

    10000
/   10000 = b<<3
-----------------
    00000

至此： a= b*2的5次方 + b*2的4次方 + b*2的3次方

所以： a/b = 2的5次方 + 2的4次方 + 2的3次方 = 11100 = 32+16+8= 46