排他的または効率的なアルゴリズム

沈殿伝播を聞く...微信公衆番号【アーキテクチャ技術の美】に注目し、より多くの技術と学習資料を学ぶ
文書ディレクトリ

I異或演算

II異或いは2つの数交換

を実現する

III異または効率的なアルゴリズム問題の解決

題1

題2

題3

題4

ⅠイソOR演算

1 ^ 0 = 1

1 ^ 1 = 0

0 ^ 0 = 0

0 ^ 1 = 1

0 ^ N = N

N ^ N = 0

異或いは結合律と交換律を満たす:A^B=B^A;A ^ B ^ C = A ^ (B ^ C)

II異種または2つの数の交換を実現する
通常は2つの数の交換を実現し、3番目の一時変数を使用して実現できます.

private static void swap(int[] arr, int i, int j) {
     
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

もちろん、3番目の一時変数を使用することなく、異和によって実現することもできます.

private static void swap(int[] arr, int i, int j) {
     
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

しかし、なぜ3回の異或演算で2つの数の交換を実現したのか知っていますか?异交换の2つの数はどれらの穴がありますか?
原理:aの値をv 1、bの値をv 2 a=a^b=v 1^v 2 b=a^b=v 1^v 2^v 2=v 1^(v 2^v 2)=v 1^0=v 1 a=a^b=v 1^v 1=(v 1^v 1)^v 2=0^v 2=v 2
しかし、どのように交換した2つの数が同じ数を指しているのか、どうなるのだろうか.aとbの値はいずれもvであると仮定する.a=a^b=v^v=0で、このときbも0になります.b=a^b=0^0=0 a=a^b=0^0=0は最終的にaとbの値が0になり、エラーが発生します.したがって,2個の数の交換を異種または実現する前提条件は,2個の数が同じデータ(メモリ)を指すことができないことである.
III異或いは効率的にアルゴリズム問題を解決する
タイトル1
1つの配列の中で、1つの数は奇数回しか現れず、他の数は偶数回も現れたが、どのようにしてこの数を迅速に見つけることができますか?
考え方:2つの同じ数が0であるため、偶数回数の数が0であるか、最終的な値も0であり、最後の0とその多く出た奇数回の数が0であるか、値はこの奇数回出た数の値である.

package com.nobody.eor;

import java.util.Arrays;

/**
 * @author Mr.nobody
 * @Description
 * @date 2020/9/6
 */
public class Code01_ {
     
    public static void main(String[] args) {
     
        //   4          
        int[] arr = {
     1, 2, 6, 4, 1, 2, 1, 1, 4, 4, 6};
        int eor = 0;
        for (int e : arr) {
     
            //         
            eor ^= e;
        }
        System.out.println(eor); //      4
    }
}

タイトル2
整数の場合、バイナリ形式の最も右側の1をどのように抽出しますか?例えば整数20、バイナリは00010100であり、最も右側の1、すなわち00000100を抽出する.
考え方:

簡単に言えば、最も右側の1の位置が1であることを除いて、他の位置は0になります.

では、2つの逆の数(0と1)が、操作値0、0と0と0と0と0と0、1と1と操作値1とを行う.

元データの最も右側のビットは必ず0で、逆を取るとすべて1になり、さらに1を加えると、キャリーの原因で再び0になります.

だからアルゴリズムを採用:N&(~N+1)

     N = 00010100
    ~N = 11101011
~N + 1 = 11101100
N & (~N + 1) : 00010100
             & 11101100
             = 00000100

package com.nobody.eor;

/**
 * @author Mr.nobody
 * @Description
 * @date 2020/9/6
 */
public class Code02 {
     
    public static void main(String[] args) {
     
        int N = 20;
        System.out.println(Integer.toBinaryString(N));
        int result = N & (~N + 1);
        System.out.println(Integer.toBinaryString(result));
    }
}

10100
100

タイトル3
1つの配列の中で、2つの数は奇数回しか現れず、他の数は偶数回しか現れません.どうやってこの2つの数を迅速に見つけますか?
考え方:

この2つの数がそれぞれaとbであると仮定し、2つの同じ数が0に等しいため、配列のすべての数を異ならせるか操作した後、result=a^bとなる.

は2種類の奇数なのでa!=b,だからresult=a^b!=0,それはresultという数のバイナリ数が必ず1存在し,この1はまたaとbが異なっていることを表す.そのaとbのバイナリビット対応位置では、それぞれ0と1であり、1を異にすることができる.

最右側位置(Liと仮定)の1をとると、その配列のすべての数は、それらのLi位置が1であるか、0であるかのいずれかである.また、aとbのLi位置は異なる(aのLi位置が1であると仮定し、bのLi位置が0であると仮定してもよい).

なので、配列のすべての数を2つのグループに分けることができます.Li位置は1のグループで、Li位置は0のグループです.同じ数は必ず同じグループ、すなわち他の偶数数の数が同じグループ(2つの異種または値が0であってもよい)にあるので、グループ内のすべての数をそれぞれ異種化すると、その2つの奇数を見つけることができる.

package com.nobody.eor;

/**
 * @author Mr.nobody
 * @Description
 * @date 2020/9/6
 */
public class Code03 {
     
    public static void main(String[] args) {
     
        //   4 11          
        int[] arr = {
     1, 2, 6, 4, 1, 2, 1, 1, 4, 4, 6, 11};

        //        a b
        //             ，  result = a ^ b;
        // a!=b, result!=0, result       1
        int result = 0;
        for (int e : arr) {
     
            result ^= e;
        }

        //       1
        int rightOne = result & (~result + 1);

        //      （Li   1）      ，
        int eor1 = 0;
        for (int e : arr) {
     
            if ((e & rightOne) != 0) {
     
                eor1 ^= e;
            }
        }
        System.out.println("       ：" + eor1 + " " + (eor1 ^ result));
    }
}

       ：11 4

タイトル4
整数のバイナリ形式で、1の個数をどのように計算しますか?
考え方:

一番右側の1から左に数えるだけで、1つ数えた後、この1を0にして、

を続けます.

実は毎回一番右側の1を抽出して+1を計算して、それからこの1を0にして、更に1を抽出し続けて、カウント...

package com.nobody.eor;

/**
 * @author Mr.nobody
 * @Description
 * @date 2020/9/6
 */
public class Code04 {
     
    public static void main(String[] args) {
     
        int num = 45;
        System.out.println("   ：" + Integer.toBinaryString(num));
        int count = 0;
        while (num != 0) {
     
            int rightOne = num & (~num + 1);
            count++;
            num ^= rightOne;
        }
        System.out.println("1   ：" + count);
    }
}

   ：101101
1   ：4