math

Magic Exclusive OR

楔子 作为CS的学生,我们应该都了解异或(Exclusive OR),也许是位运算,也许是那张真值表: A B $\bigoplus$ F F F F T T T F T T T F 但最近CodeForces上的一道题又让我对它产生了新的思考。它和模有什么关系?这个运算的本质又是什么? 从群论上说: 异或是$\mathbb{Z}_2$群的加法运算,满足加法结合律和交换律。 emm,换一种数论的说法: 在模2剩余系中进行加法运算。 所以,它其实和加法有一些类似。 第一章 还记得那个不使用另外的变量交换两个变量的著名trick嚒? 没有深入理解的时候你也许会诧异, a = a ^ b b = a ^ b a = a ^ b 列个表也许更清楚? Expression a b init a b a = a ^ b a ^ b b b = a ^ b a ^ b a ^ b ^ b = a a = a ^ b a ^ b ^ a = b a result b a 所以它其实只是利用了异或的交换律和结合律,当然你不考虑溢出的话用加法也能轻松实现。