算法

异或（Exclusive OR，简称 XOR）是一种数学运算符，常用于逻辑运算与计算机中的位运算。当且仅当两个输入值不同时，异或运算输出为真（1），否则输出为假（0），即“同为 0，异为 1”。异或运算可以通过数学符号“⊕”表示， 具有交换律、结合律、恒等律等性质。 异或运算常见的应用包括奇偶校验、加法器设计、密码学中的加密与解密操作以及变量交换等。异或运算的一个重要特性是自反性：任何值与自身异或的结果为0，任何值与 0 异或的结果为其本身。 异或广泛应用于现代信息技术的多个领域，如数据加密、错误检测和纠正、图像处理等，尤其在数字电路设计与密码学中发挥着至关重要的作用。此外，异或运算在代数领域也扮演了关键角色。它所构成的系统是阿贝尔群， 与合取（AND）运算共同构成了著名的两元素域 F2，这是描述布尔函数的代数标准型的重要基础。 定义 异或是一个数学运算符，它应用于逻辑运算与计算机中的位运算。 令 p 和 q 为命题。p 和 q 的异或是这样一个命题：当p 和 q 中恰好只有一个为真时命题为真，否则为假。 p 异或 q 通常记作 p XOR q 或 p⊕ q。在编程语言中通常为 p^q。 如 p、q 两个值不相同，则异或结果为 1。如果 p、q 两个值相同，异或结果为 0，即异或的运算法则为：0 ⊕ 0 = 0，1 ⊕ 0 = 1，0 ⊕ 1 = 1，1 ⊕ 1 = 0（同为 0，异为 1）。这种运算捕捉了输入位的“排他性”，即输入不能同时为真。 异或也叫半加运算，其运算法则相当于不带进位的二进制加法：二进制下用1 表示真，0 表示假，这些法则与加法是相同的，只是不带进位，所以异或常被认作不进位加法。 应用 交换两个变量的值 int a int b a = a^b b = a^b a = a^b console.log(a) console.log(b)

什么是哈夫曼编码 在数据传送时，信息表现为0和1的二进制形式。为了提高传输的速度，可以采用变长的编码方式，寻找更优的编码方式。同时，必须要保证编码不存在二义性（任意字符编码都不是其它字符编码的前缀）。 哈夫曼编码就是符合上述要求的编码方式，采用自底向上的形式构造哈夫曼树。按照字符的概率分配码长，实现平均码长最短的编码。 如何进行哈夫曼编码 使用需要传送的字符构造字符集C = {c1, c2, … cn}，并根据字符出现的频率构建概率集W = {w1, w2, … wn}。哈夫曼编码的流程如下： 将字符集C作为叶子节点； 将频率集W作为叶子节点的权值； 使用C和W构造哈夫曼树； 对哈夫曼树的所有分支，左子树分支编码为0，右子树分支编码为1； 通过上述流程，即完成了哈夫曼编码。 void HuffmanCode(Node *p, const int numLeafs, string *codes) { // p为节点数组的指针，codes为string数组的指针 // 用于存储每个节点的哈夫曼码 // parent表示父节点位置 int parent; // 每次对一个叶子节点进行编码 // i表示当前叶子节点位置 for (int i=0; i < numLeafs; i++) { // j表示当前节点位置，i是不能在下面循环中改变的 // 使用j来记录节点的移动过程 int j = i; // 当前节点的父节点位置 parent = p[i].parent; // 从当前叶子节点p[i]开始，找到哈夫曼树的根节点 // 循环结束条件是此时parent为0，即达到哈夫曼树的根节点 while(parent != -1) { // 如果当前节点是父节点的左子树，则此分支编码为0 if (p[parent].left == j) { codes[i].push_back('0'); } // 如果当前节点是父节点的右子树，则编码为1 else { codes[i].push_back('1'); } j = parent; parent = p[j].parent; } cout << codes[i] << endl; } }