Xor bagi N nombor

Diberi nombor integer N, cari exor julat 1 hingga N
exor of 1 ^ 2 ^ 3 ^4 ^.....N;

Pendekatan kekerasan:
Tc:O(n)
Sc:O(1)

public int findExor(int N){

        //naive/brute force approach:
        int val  = 0;
        for(int i=1;i



<p>Pendekatan optimum:<br>
Tc:O(1)<br>
Sc:O(1)<br>
</p>

<pre class="brush:php;toolbar:false">
    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;

    }

Bagaimana jika kita perlu mencari exor antara julat seperti L dan R
contoh cari exor antara nombor 4 dan 7 iaitu 4^5^6^7.

Untuk menyelesaikannya, kami boleh memanfaatkan penyelesaian optimum yang sama di atas getExor()

mula-mula kita akan dapatkan exor hingga L-1 iaitu getExor(L-1) = 1 ^ 2 ^ 3 (sejak L-1 = 3)......persamaan(1)

maka kita akan dapati getExor(R) = 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ----persamaan(2)

akhirnya,

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;

    }

Atas ialah kandungan terperinci Xor bagi N nombor. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!