データ構造—ビット演算

1シフト演算子

<<     (  )：   0
>>     ：     ，   ， 0；   ， 
>>>       
<<<      

1.1 offer 10は、バイナリの1の個数を計算します.
エラー解法:負の値を入力すると、プログラムはデッドサイクルの問題解決過程に陥ります.入力数numを右に動かすことで、1と「和」演算をして、このビットのバイナリが1かどうかを判断します.負の数の最高位は1に設定され、右に0 x FFFFFFに移行して死のサイクルに陥る.

    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を引いて、元の整数と“和”の演算をしたら、元の整数の一番右側の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;
    }