首页 > 其他分享 >异或的一些性质

异或的一些性质

时间:2024-09-05 17:26:39浏览次数:10  
标签:dots 右移 异或 4k 4i 一些 oplus 性质

1.异或:

相同为0
不同为1

\[0 \oplus n = n \]

\[n \oplus n = 0 \]

2.异或定理

\[4i \oplus (4i + 1) \oplus (4i + 2) \oplus (4i + 3) = 0 \]

证明:
由于异或按位进行操作,将\(4i\)、\(4i+1\)、\(4i+2\)、\(4i+3\)二进制右移两位之后,得到\(4\)个偶数,其数值都为\(i\),因此,右移之后的异或和为\(0\)。
对于右移后的低位,其二进制异或为:

\[00 \oplus 01 = 01 \]

\[01 \oplus 10 = 11 \]

\[11 \oplus 11 = 00 \]

因此,上式成立。

3.\(0\)到\(n\)的异或和

记\(f(n)\)为\(0\)到\(n\)的异或和,即:

\[f(n) = 0\oplus 1 \oplus 2 \oplus \dots \oplus (n - 1) \oplus n \\ \]

\[f(n)= \begin{cases} n,&n = 4k\\[2ex] 1,&n = 4k+1\\[2ex] n + 1,&n = 4k+2\\[2ex] 0,&n = 4k+3 \end{cases} \]

证明:
\(0、1、2、3\)的异或和为\(0\),因此当\(n=4k+3\),即有\(4\)的倍数个数字时其异或和为\(0\)。
当\(n=4k+2\),$f(n) = (n - 2) \oplus (n - 1) \oplus n $,将其右移两位之后,得到\(3\)个为\(k\)的数字,其异或和为\(k\),左移两位为\(4k\)。而\(00\oplus01\oplus10 = 11\),因此,异或和为\(f(n)=4k+3 = n + 1\)

当\(n=4k+1\)时,$f(n) = (n - 1) \oplus n $,将其右移两位之后,得到\(2\)个为\(k\)的数字,其异或和为\(0\),因此,异或和为\(f(n)=0+ 1= 1\)。
当\(n=4k\)时,$f(n) = n $。

4.\(a\) 到\(a+n\)的异或和

\[\begin{aligned} f(a,n) &= a \oplus (a + 1) \oplus (a + 2) \oplus \dots \oplus(a+n) \\ &=(0\oplus0)\oplus (1\oplus1)\oplus \dots \oplus((a-1) \oplus (a-1)) \oplus a \oplus (a + 1) \oplus (a + 2) \oplus \dots \oplus(a+n)\\ &= (0\oplus 1 \oplus 2 \oplus \dots \oplus (a+n) )\oplus (0\oplus 1 \oplus 2 \oplus \dots \oplus (a-1))\\ &= f(a+n) \oplus f(a-1) \end{aligned} \]

标签:dots,右移,异或,4k,4i,一些,oplus,性质
From: https://www.cnblogs.com/ymh126/p/18398684

相关文章

  • 分享一些懒人程序员的工作经验
    ......
  • 服务器 Debian 安装初使用一些设定记录
    通常拿到服务器root和密码后,我们进行一些安全首选项必备,开启BBR,注意Debian12默认支持BBR,只需要开启即可需要服务器内核支持uname-r//内核版本高于4.9就行。安装#一键开启echo-e"\nnet.core.default_qdisc=fq\nnet.ipv4.tcp_congestion_control=bbr">>......
  • 关于智能指针的一些疑问/
    首先先来一段代码,说明我的自主删除器:template<typenameT>classFFmpegDeleteer{public:voidoperator()(T*ptr)const{if(ptr){ deleteptr; }}};template<>classFFmpegDeleteer<AVFormatContext>{public:voidoperator()(AVFormatConte......
  • C语言练习:扫雷游戏(排除了一些bug,放心食用!)
    游戏规则只有雷被全部排查出来,游戏结束。每当排查一个坐标,如果不是雷,此坐标上就会显示周围一圈上有几个雷。 游戏实现代码讲解开始前的准备首先我们假定一个9*9的棋盘格展示在玩家面前(如下图所示,坐标从0开始)但是对于玩家来说,第一个编号是从0开始的不太习惯,所以我们要在......
  • 关于Java链表的一些操作以及力扣原题刷刷刷——反转链表、删除链表的倒数第N个节点
    1、反转链表1.1环境准备,可以自己先尝试实现/***@AuthorMiku*@Date2024/09/0209:54*@DescriptionTODO*@Version1.0*/publicclassSolution{staticclassListNode{intval;ListNodenext;ListNode(intval){......
  • 软件研发效能的一些指标
    项目报表数据来源:Jira项目数概览总项目数日均项目数完成项目数日均完成项目数总Bug数日均Bug数总参与人数平均交付量第x周交付数量(项目完成)交付耗时Top7项目交付耗时(created->Done)项目待解决Bug数待解决总Bug数项目平均待解决Bug数待解决Bug列表......
  • 数域的性质
    数域的性质数域是数学中的一个代数结构,定义为一个集合,其中定义了两种运算:加法和乘法,并且这些运算满足一定的条件。具体来说,数域具有以下特性:封闭性:对于数域中的任意两个元素,加法和乘法的结果仍然在该数域中。加法和乘法的结合律:对于任意数域中的元素(a)、(b)和(c),有:......
  • Vue3 组件封装的一些技巧和心得 转载
    在日常开发的过程中,使用Vue的组件进行业务拆分,代码解耦是一个很好的选择;今天就来分享一下我在使用Vue3进行组件封装的一些技巧和心得,希望能够帮助到大家;1.组件特性在Vue中组件是一个独立的实例,每个组件都有共通点,就是:属性、插槽、事件、方法;在日常我们使用第三方组件库的时候......
  • 架构师备考的一些思考
    前言之前的python-pytorch的系列文章还没有写完,只是写到卷积神经网络。因为我报名成功了系统架构师的考试,所以决定先备考,等考完再继续写。虽然架构师证书不能证明技术水平,但在现实生活中的某些情况下是有意义的。考试虽然无聊,但有些考题还是蛮有意思的。思考看了几套架构师的......
  • 使用ESP8266-01s的一些知识点
    在这里发表自己并记录自己在做项目的一些问题以及注意事项关于ESP8266通过API接口物联网技术获取当前天气以及当前时间的步骤:1.AT (进入AT指令模式)应答:OK2.AT+CWMODE=1 (设置为STA模式)应答:OK//设置工作模式1:station模式2:AP模式3:兼容AP+station模式3.AT+RS......