N 个数字的异或

今天golang学习网给大家带来了《N 个数字的异或》，其中涉及到的知识点包括等等，无论你是小白还是老手，都适合看一看哦~有好的建议也欢迎大家在评论留言，若是看完有所收获，也希望大家能多多点赞支持呀！一起加油学习~

给定一个整数 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 个数字的异或》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！