数据结构—位运算

1 移位运算符

<<   左移(进位)：低位补0
>>   右移：若符号拓展，为正时，补0；为负时，补
>>>  无符号右移
<<< 无符号左移

1.1 offer10计算二进制中的1的个数

错误解法：若输入一个负数，则程序陷入死循环
解题过程：通过将输入数num右移操作，与1做“与”运算来判断此位二进制是否为1；负数的最高位会设为1，右移操作至0xFFFFFFFF陷入死循环

    public static int countNum1(int num) {
        //如果输入一个负数，则程序陷入死循环
        int count=0;
        while(num!=0){
            if((num&1)!=0){
                count++;
            }
            num>>=1;
        }
        return count;
    }

常规解法1：通过左移比较值1，来与输入值num进行“与”运算，直至0；

    public static int countNum2(int num) {
        //常规解法1
        int count=0,k=1;
        while(k!=0){
            if((num&k)!=0){
                count++;
            }
            k<<=1;
        }
        return count;
    }

巧妙解法2：当一个整数减去1，再和原整数做“与”运算，就会把原整数最右边的一个1变成0；

  public static int countNum3(int num) {
        //巧妙解法2
        int count=0;
        while(num!=0){
            count++;
            num&=(num-1);
        }
        return count;
    }

注意：在计算机中，负数以其正值的补码形式表达

2 按位运算符

   &  与：同时为1时，才为1
   |   或：有1存在时，即为1
   ^  异或：俩值不相同时，才为1
   ~  取反：取反+1为补码

2.1 位运算实现四则运算

加法

    public static int addComputing(int a,int b){
        //循环解法
        int answer=a;
        while(b!=0){
            answer=a^b; 
            b=(a&b)<<1;
            a=answer;
        }
        return answer;
    }

    public static int addComputing2(int a,int b){
        //递归解法
        return b!=0?addComputing(a^b, (a&b)<<1):a;
    }

减法：调用加法，a-b即a+(-b)；取反加1为补码

  public static int minusComputing(int a,int b){
        return addComputing(a, addComputing(~b,1));
    }

乘法：

    public static int multiComputing(int a,int b){
        //测试用例：(10,-10)(-10,10)(-10,-10)(0,10)(10,0)
        if(b<0&&a<0){
            a=addComputing(~a,1);
            b=addComputing(~b,1);
        }else if(b<0){
            int temp=b;
            b=a;
            a=temp;
        }
        int answer=0;
        while(b!=0){
            if((b&1)!=0){
                answer=addComputing(answer, a);
            }
            a<<=1;b>>=1;
        }
        return answer;
    }

除法：注意正负号

    public static int divideComputing(int a,int b){
        if(b==0){
            System.out.println("error data b");
            return 0;
        }
        boolean checksign=false;
        if(a<=0&&b<0){
            a=AddComputing.addComputing(~a, 1);
            b=AddComputing.addComputing(~b, 1);
        }else  if(b<0){
            b=AddComputing.addComputing(~b, 1);
            checksign=true;
        }else if(a<=0){
            a=AddComputing.addComputing(~a, 1);
            checksign=true;
        }
        int count=0;
        while(a>=b){
            a=MinusComputing.minusComputing(a, b);
            count++;
        }
        if(checksign){
            count=AddComputing.addComputing(~count, 1);
        }
        return count;
    }