0x00. 预备知识

异或是逻辑运算符中的一种，基本的定义是：对于两个操作数，如果他们不相同（一个为true，另一个为false）那么输出为true。大多数编程语言都提供这样的操作符（^）。

运算见下表：

0 = FALSE

1 = TRUE

0x01. 性质

从数学的角度来看，此运算符符合

（4）的性质可从(2)以及(3)轻松证明，而（4）这条的性质可以用来进行加密。A为原文，B为秘钥。A⊕B为密文。这种简单的加密方法具有的优点是速度快，缺点也很明显，就是A与B要有一样的长度。

学过矩阵的同学应该记得单位矩阵，单位矩阵类似于我们数字乘法中的1。它的性质就是AXB = B，数字中相对的概念就是1XN = N。延伸到异或的概念中，这里的单位异或（大概应该这么叫吧）就是0，因为（3），A⊕0 = A。

十进制　　　　二进制

0^1 = 1　　000^001 = 001

1^2 = 3　　001^010 = 011

2^3 = 1　　010^011 = 001

3^4 = 7　　011^100 = 111

4^5 = 1　　100^101 = 001

5^6 = 3　　101^110 = 011

更进一步，我们来试试0^1^2^3^4^5...

我们将A[n]定义为0^1...^n-1^n

(第一个操作数为前一轮的结果，第二个操作数为递增数，由于0的单位属性，我们从0开始)

由上面的例子我们可以发现，对于我们定义的A[n]，有以下规律

A=[0,1,3,0,4,1,7,0,8,1,11,…]

我们发现这个规律是以4为周期的,通俗一点：

A[3] = 0^1^2^3 = 0

A[7] = 0^1^2^3^4^5^6^7 = 0

A[11] = 0^1^2^3^4^5^6^7^8^9^10^11 = 0

...

是不是发现我们算A[7]的时候只要算4^5^6^7就可以了？因为0^4^5^6^7 = 4^5^6^7

同样A[11]也只要算8^9^10^11

那么对于任意大的数我们都可以对应到上面的表格来计算出来

#define ll long longll xorp(ll x) {    ll ans = 0;    while (x) {        if (x % 4 == 3) break;        ans ^= x;        --x;    }    return ans;}

根据上面定义的A[n]，我们再定义B[n] = A[0]^A[1]^A[2]...A[n-1]^A[n]

例如 B[2] = 0 ^ 1 ^ 3

我们会发现对于B[n]也有很好玩的规律：

ll xorpp(ll x) {    ll ans = 0;    while (x) {        if (x % 8 == 7) break;        ans ^= xorp(x);        --x;    }    return ans;}

用这张表来对比上面的那张表，是不是很相似呢？

从上面的两个例子，我们发现了异或对于特定数列有一些很好玩的特性。

好了，如果你看到了这里，为何不看看这道题呢？

https://www.hackerrank.com/contests/hourrank-5/challenges/xor-se

参考：https://en.wikipedia.org/wiki/Exclusive_or

转载于:https://www.cnblogs.com/rushyourmind/p/5183507.html

你可能感兴趣的文章