leetcodeブラシノート————ビット演算

一.Javaでよく見られるビット演算
1.リード
ビット演算は、デジタル0および1に特化した演算であるバイナリの各ビットに対する演算である.プログラム内のすべての数は、コンピュータメモリにバイナリ形式で格納されます.ビット演算は、メモリ内の整数のバイナリビットを直接操作するコードであり、ビット演算はメモリを節約し、プログラムの速度をより速く効率的にすることができます.
2.javaでのビット演算
Javaビット用演算子はまた論理演算子と変位演算子に分けることができる.論理演算子には、ビットと&、ビットまたは|、逆～、ビット別異または^;シフト演算子には、左シフト<>、符号なし右シフト>>>>があります.すべてのビット演算子において、～以外は二元演算子オペランドであり、ビット演算の演算対象は整数型と文字型データである
二.論理演算子
1^(または演算)
演算ルール:バイナリ用、同じ0、異なる1

public static void main(String[] args) {
    System.out.println("3^4       :"+(3^4));
    //3 =======>011
	//4 =======>100
	//     ：7(111)
}

特徴:1.どの数字も彼自身も0に等しい.2.いずれの数字も0と異なるか、それ自体である.3.a^bは、aとbが加算された後、その進位の場所が進位しない結果である.4.指定されたビットとすべて1で^異或演算を行い、そのビット反転(1が0になり、0が1になる)を実現することができる.
2&(演算)
演算ルール:2つの数が一致し、1つが0であれば0であり、同時に1である.

public static void main(String[] args) {
    System.out.println("3&4       :"+(3&4));
    //3 =======>011
	//4 =======>100
	//    ：0(000)
}

特徴:1.対応するデータビット全1の数&演算と、そのビット自体の値を取得することができる.2.対応するデータビット全0の数&演算と、その位置を0とすることができる.
3|(または演算)
演算規則:2数相または、1つが1であれば1であり、同時に0であれば0である.

public static void main(String[] args) {
    System.out.println("3|4       :"+(3|4));
    //3 =======>011
	//4 =======>100
	//    ：7(111)
}

特徴:1.対応するデータビット全1の数|と演算すると、その位置1
4~(取反演算)
演算規則:取反演算は1つのデータに対してのみ操作され、バイナリが0であれば取反は1、バイナリが1であれば取反は0である.

public static void main(String[] args) {
    System.out.println("~3       :"+(~3));
    //3 =======>11
	//    ：0(00)
}

三.シフト演算子
1.<
演算ルール:バイナリに対して、バイナリに変換して左に移動し、低位は0で補正し、高位オーバーフローは捨て、シンボルビットに遭遇し、シンボルビットは変わらず、演算に参加しない

public static void main(String[] args) {
         System.out.println("2<<3       :"+(2<<3));
         //      :   2  3         :16
     }

特徴:1.左シフト1ビットは*2に相当します.左に何桁移動するかは何桁乗るかに相当する.
1.>>(右への記号のシフト)
演算規則:バイナリに対して、バイナリに変換して右に移動し、シンボルビットに遭遇し、シンボルビットは変わらず、演算に参加せず、低位オーバーフローして捨て、損失した高位[すなわち負数補1、正数補0]をシンボルビットで補う.

public static void main(String[] args) {
         System.out.println("4>>2       :"+(4>>2));
         //      :   4            :1
     }

特徴:1.右シフト1ビットは/2に相当します.右シフト数位は/数2に相当する.
3.>>>>(符号なしで右へシフト)
演算規則:符号なし右シフト演算は、オペランドのすべてのバイナリ値をビットごとにいくつかのビットを右シフトし、最高位記号ビットも含め、右シフトに従い、低位オーバーフローして捨て、高位補0である.なお、符号なし右シフト(>>>>)における符号ビット(最高位)も変化する.

public static void main(String[] args) {
         System.out.println("4>>>2       :"+(4>>2));
         //      :   4               :1
     }

例えば、10000000>>2結果10000001 100000111>>2結果100000100>>2結果0010000001 100000111>>2結果0010000001
四.leetcode経典ビット演算テーマ
1.ビット1の個数
タイトル:
符号なしの整数を入力する関数を作成し、そのバイナリ式の数値桁数が「1」の個数を返します.(leetcode191)
問題解決の考え方:
nとn−1の2つの数のバイナリ表現を観察すると、n−1という数のバイナリでは、nのバイナリに対して最下位の1つが0になり、最下位の1つが1になった後の0がすべて1になり、他のビットは同じになる.例えば、n=8888であり、そのバイナリが10001011000であればn−1=8887であり、そのバイナリが10001010111であり、ビットと操作後:n&(n−1)=10001010110000、すなわち、n&(n−1)という操作により、最後の1を除去する役割を果たすことができる.したがって,n&(n−1)操作を実行することでn末尾の1を除去することができ,何回除去したか,1が何個あるかを説明する.

public static int findOne(int n)
    {
        int countOne = 0;
        while (n > 0){
            count++;
            n = (n - 1) & n;
        }
        return countOne;
    }

2.2のべき乗
タイトル:
整数が与えられ、2のべき乗次数(LeetCode 231)であるか否かを判定する関数が記述される.
問題解決の考え方:

まず、2の次数を分析するバイナリ表記:0:0 2:10 4:100 8:1000…よく観察すると、2の次数はいずれも1つしかなく、残りはすべて0であることがわかります.この特徴によれば,最低位が1であるか否かを判断するたびに右にシフトし,最後に1の個数が1であるか否かを統計するだけで2の次数であるか否かを判断できる.

public static boolean isPowOfTwo(int n) {
		int CountOne = 0;
		while(n > 0) {
			CountOne += (n & 1);
			n >>= 1;
		}
		return CountOne == 1;
	}

は、例えば16のバイナリが10000である、15のバイナリが01111である、2つの数の相と結果が0であることを再観察する.すなわち、nが2の次べき乗であると、n&(n-1)は必ず0となる.コードは次の

です.

public static boolean isPowOfTwo(int n) {
		return ((n&(n-1))==0);
	}

3.数字の範囲はビットと
タイトル:
範囲[m,n]が与えられ、0<=m<=n<=2147483647であり、この範囲内のすべての数字のビットアンド(m,nの両端点を含む)が返される(LeetCode 201).
入力:[5,7]出力:4
入力:[0,1]出力:0
問題解決の考え方:
ビットアンドであるため,あるビットが0になると,そのビットは0になるに違いない.だからm,nはいずれも1の位置であることを考慮するだけである.では、直接高位から低位に進み、そのビットに対応する数字が等しくないまで、その後とその後の数を0、すなわち[m,n]の間のすべての数字をビットで加算した結果とする.
1.では、2桁を右にシフトさせてから、2桁が等しいかどうかを判断し、移動した桁数を記録し、2桁が等しいまで移動すると、2桁左の共通部分が見つかったので、その数の末尾を元の数と同じ長さにゼロにすればよい.

public static int solution(int m , int n) {
		int i = 0;
		while(m != n ) {
			m = m>>1;
			n = n>>1;
			i++;
			
		}
		
		return (m<<i);
	}

2.まず32ビットが1の最大数であることを確立し、その後、左に1ビット移動するたびに、mとnが同じかどうかを比較し、異なる場合は同じになるまで左に1ビット移動し続け、mとint_maxの相乗は最終結果である.

	public static int solution2(int m,int n) {
		  int int_max = Integer.MAX_VALUE ;//2147483647
	        while ((m & int_max) != (n & int_max)) {
	        	int_max <<= 1;
	        }
	        return m & int_max;
	    }

4.逆バイナリビット(leetcode 190)
タイトル:
与えられた32ビットの符号なし整数のバイナリビットを逆にします.
例1:入力:000000010100101000111101001100出力:0011001011110001010010100000解釈:入力されたバイナリ列00000010100101000111101001100は符号なし整数43261596を表すので、964176192を返し、そのバイナリ表現形式は0011001011110001010010100000である.
問題解決の考え方:
この問題に対して、私たちは反転する数を右から左に1桁取り出すだけで、もし1を取り出したら、私たちは結果resを左に1桁移動して1を加えます.0が取り出された場合、結果resを左にシフトし、反転する数nを右にシフトすれば、コードは次のようになります.

public static int reverseBit(int n) {
		int res = 0;
		for (int i = 0; i < 32; ++i) {
            if ((n & 1) == 1) {
                res = (res << 1) + 1;
            } else {
                res = res << 1;
            }
            n = n >> 1;
        }
        return res;
	}