首頁  >  文章  >  Java  >  N 個數字的異或

N 個數字的異或

Patricia Arquette
Patricia Arquette原創
2024-09-21 20:15:32308瀏覽

Xor of N numbers

給定一個整數 N,找出 1 到 N 範圍內的異或
1 ^ 2 ^ 3 ^4 ^.....N 的異或;

暴力方法:
Tc:O(n)
Sc:O(1)

public int findExor(int N){

        //naive/brute force approach:
        int val  = 0;
        for(int i=1;i<5;i++){
            val =  val^ i;
        }
        return val;
    }

最佳方法:
Tc:O(1)
Sc:O(1)

    public int getExor(int N){
        //better approach

        /**
         * one thing to observe is 
         * 1 = 001  = 1
         * 1 ^2 = 001 ^ 010 = 011=       3
         * 1^2^3 = 011 ^ 011 = 0=        0
         * 1^2^3^4 = 000^100 = 100=      4
         * 1^2^3^4^5 = 100^101 = 001=    1
         * 1^2^3^4^5^6 = 001^110 =111=   7
         * 1^2^3^4^5^6^7 = 111^111=000=  0
         * 
         * what we can observer is : 
         * 
         * N%4==0 then result is: N
         * N%4 ==1 then result is: 1
         * N%4 ==2 then result is: N+1
         * N%4==3 then result is: 0
         * 
         * */
         if(N%4==0) return N;
         else if(N%4 ==1) return 1;
         else if(N%4==2) return N+1;
         else return 0;

    }

如果我們必須找到 L 和 R 等範圍之間的 異或怎麼辦
例如找出數字 4 和 7 之間的異或,即 4^5^6^7。

為了解決這個問題,我們可以利用與 getExor() 相同的最佳解決方案

首先我們將得到exor直到L-1,即getExor(L-1) = 1 ^ 2 ^ 3(因為L-1 = 3)…方程式(1)

然後我們會發現 getExor(R) = 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ----equation(2)

最後,

Result  = equation(1) ^ equation(2)
        = (1 ^ 2 ^ 3) ^ (1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7)
        = (4^5^6^7)

public int findExorOfRange(int L, int R){
        return getExor(L-1) ^ getExor(R);
    }

public int getExor(int N){
        //better approach

        /**
         * one thing to observe is 
         * 1 = 001  = 1
         * 1 ^2 = 001 ^ 010 = 011=       3
         * 1^2^3 = 011 ^ 011 = 0=        0
         * 1^2^3^4 = 000^100 = 100=      4
         * 1^2^3^4^5 = 100^101 = 001=    1
         * 1^2^3^4^5^6 = 001^110 =111=   7
         * 1^2^3^4^5^6^7 = 111^111=000=  0
         * 
         * what we can observer is : 
         * 
         * N%4==0 then result is: N
         * N%4 ==1 then result is: 1
         * N%4 ==2 then result is: N+1
         * N%4==3 then result is: 0
         * 
         * */
         if(N%4==0) return N;
         else if(N%4 ==1) return 1;
         else if(N%4==2) return N+1;
         else return 0;

    }

以上是N 個數字的異或的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn