最近碰到很多通过巧妙着运用位运算来巧妙解决复杂问题的算法，今天分享的这道题，或许能够开拓你的一些算法思维。 题目描述 有一组存放 ID 的数据。...并且 ID 取值为 0 - (N-1) 之间，其中只有一个 ID 出现的次数为 1，其他的 ID 出现的次数都等于 2，问如何找到这个次数为 1 的 ID 解法一：巧用数组下标 我的第一想法便是采用下标法来解决...这个方法最好的情况下空间复杂度可以降低到 O(1)，最坏的情况仍然了 O(N)。 解法三：巧用位运算 那究竟有没办法让空间复杂度在最坏的情况下也是 O(1) 呢？ 答是有的，按就是采用异或运算。...这个方法的空间复杂度为 O(1)，巧妙利用了位运算，而且运算的效率是非常高效的。 问题拓展 假如有 2 个 ID 出现的次数为 1，其他 ID 出现的次数都为 2 呢？有该如何解决呢？...由于 A 和 B 是不一样的值，所以 A@B 的结果不为 0，也就是说，这个异或值的二进制中某一位为1。显然，A 和 B 中有且仅有一个数的相同位上也为 1。
最近碰到很多通过巧妙着运用位运算来巧妙解决复杂问题的算法，今天分享的这道题，或许能够开拓你的一些算法思维。 题目描述 有一组存放 ID 的数据。...我的第一想法便是采用下标法来解决，把 ID 作为数组 arr 的下标，在遍历 ID 的过程中，用数组记下每个 ID 出现的次数，即每次遍历到 ID = n，则 arr[n]++。...这个方法最好的情况下空间复杂度可以降低到 O(1)，最坏的情况仍然了 O(N)。 解法三：巧用位运算 那究竟有没办法让空间复杂度在最坏的情况下也是 O(1) 呢？ 答是有的，按就是采用异或运算。...这个方法的空间复杂度为 O(1)，巧妙利用了位运算，而且运算的效率是非常高效的。 问题拓展 假如有 2 个 ID 出现的次数为 1，其他 ID 出现的次数都为 2 呢？有该如何解决呢？...由于 A 和 B 是不一样的值，所以 A@B 的结果不为 0，也就是说，这个异或值的二进制中某一位为1。显然，A 和 B 中有且仅有一个数的相同位上也为 1。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。 ...题目分析我们需要从一个一个非空数组中找出只出现一次的数字，并且题目限制了必须以线性时间复杂度的算法实现来解决此问题，且该算法只使用常量额外空间。...也就是时间复杂度必须为 O(n)，空间复杂度必须为 O(1)。...但是上面的解法都需要额外使用 O(n) 的空间，其中 n 是数组长度。那么如何才能做到线性时间复杂度和常数空间复杂度呢？答案是使用位运算。我们可以使用异或运算 ⊕ 来解题。...异或运算有以下三个性质：任何数和 0 做异或运算，结果等于其本身，即 a⊕0=a。任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
使用按位异或（^）操作找出 x 和 y 的二进制表示中不同的位，结果是一个新整数 s。 调用 hammingWeight 函数统计 s 中的 1 的个数，即为汉明距离。...最终返回汉明距离：2 输出 2 4.3 时间复杂度和空间复杂度 时间复杂度 异或操作：按位异或操作的时间复杂度为 O(1)。...优势： 时间复杂度为 O(n)，一次遍历解决问题。 空间复杂度为 O(1)，无需额外存储空间。 适用场景：数组中有且只有一个数字出现一次，其余数字均出现两次 6....空间复杂度：O(1)，原地排序（如果排序算法是原地的） 6.4.3 解法对比总结 6.5 总结 异或法是解决此类问题的核心思想，利用异或的性质实现高效解法。...总结要点 异或运算 是位运算解决重复出现问题的核心思想： 相同为0，0与任何数异或等于数本身。 位统计 + 取模：通过逐位统计 1 的个数，可以解决 K次出现问题。
具体请见下图所示： 问题：数字1和2如何相互转换 当某一位上的任意值a（0或1）与1执行按位异或操作时，具有“按位翻转”的作用。即：0翻转为1，1翻转为0。...而当某一位上的任意值a（0或1）与0执行按位异或操作时，则会将a原样输出。...具体如下所示： 0 ^ 1 = 1（0被按位翻转为1） 1 ^ 1 = 0（1被按位翻转为0） 0 ^ 0 = 0（0被原样输出） 1 ^ 0 = 1（1被原样输出） 当我们了解到了异或的按位翻转功能...，就可以通过采用与3进行异或方式将数字1和2相互转换。...时间复杂度：O(n)，其中 n 为字符串 s 的长度。
位运算常用的运算符包括&（按位与）， | （按位或），~（按位非），^（按位异或），>（有符号右移位）。 下面用几个例子说明其应用，希望对你有所启发。...2，右移一位相当于除以2 在面试的过程中，通常会遇到的一个问题是写二分查找代码。...这里，总结下异或运算的特性：任意数和自身异或结果为0；0和任意数异或结果还是其本身。 4、寻找数据列表中的独一无二 有一个数据列表（2N+1个整数），只有一个数出现了1次，其余N个数都出现了2次。...如何找到这个独一无二的数据？ 看到这个题目，相信大家第一次想到的算法肯定是计数，建立列表，循环整个数据并计数，然后遍历这个列表找到出现次数为1的数据。 这样，空间复杂度为O（N）。...如何降低空间复杂度呢？ 注意看一下刚刚讲过的异或的特性：任意数和自身异或结果为0；0和任意数异或结果还是其本身。 那么，出现了2次的N个数异或的结果是0，再与出现次数为1次的数异或的结果即为该数。
33.常见位运算 1.基础位运算 << 左移操作符 > >右移操作符号 ~取反 &按位与：有0就是0 |按位或：有1就是1 ^按位异或：相同为0，不用的话就是1 /无进位相加 0 1 0 0...1 1 0 1 0 按位与结果 0 1 1 按位或结果 0 0 1 按位异或结果 2.给一个数n，确定他的二进制表示中的第x位是0还是1 n: 0 1 1 0 1 0 1 0 0 1 右边是最低位...>>x）&1== 3.将一个数n的二进制表示的第x位修改成1 我们先让这一位上的数按位或上1，那么原本这一位是0的，现在0|1得到的就是1了，但是我们得让其他位的数字不变，其他位的数按位或上一个0就行了...我们可以利用一个哈希表进行问题对的解决，但是时间复杂度是O(N)的，空间复杂度一样 我们也可以利用高斯求和进行问题解决，时间复杂度是O(N)的，空间复杂度是O（1） 我们这里使用位运算（异或运算的运算律...你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
这类问题通常是为了考察应聘者对算法的深入理解以及对编程语言的掌握程度。 如果涉及到数组或者运算，经常就需要使用位运算来巧妙的解决这些问题。...那么接下来我们来学习这个算法 2 位运算 我们熟知的位运算以下几种： & 按位或 ：有 0 就为 0 | 按位与 ：有 1 就为 1 ^ 按位异或 ：相同为 0 ，不同为 1 / 无进位相加 ~ 按位取反...算法思路 这道题有很多解法：哈希表 ， 双指针 ， 位运算 我们采取位运算的位图来解决问题，让面试官眼前一亮。...算法思路 这道题也有很多算法：哈希表，数学方法，位运算 这里也是采取位运算的方法，我们将[0 ， n]的所有元素都进行按位异或。然后再把数组中的元素进行按位异或。...//[0 , n] 进行按位异或 //数组元素进行按位异或 //他们再进行按位异或 int tmp = 0; for(int
按位或 | 运算 有1就是1，巧计：|本身就像一个1 按位异或^运算（两种解释方法） 相同为0，相异为1，或者解释成无进位相加。...你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。 解析： 这是一道很典型的运用^的题目，我们只需要理解异或运算符，这题就迎刃而解啦。...你可以按 任意顺序 返回答案。 你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。...解析： 本题是上一题的升级版， 把nums中的元素全部异或起来的结果eor就是那两个只出现一次的数字的异或结果。...将所有的数异或在一起，记为tmp 找到tmp中，比特位上为1的那一位 根据不同的那一位，划分为两类异或 原码 class Solution { public: vector missingTwo
具体内容包括： 位运算简介：博客首先回顾了基本的位运算符，如按位与（&）、按位或（|）、按位异或（^）、按位非（~）等，并简单解释了它们的作用和应用。...优化与挑战：通过一些算法的优化（如通过异或运算实现加法），博客强调了位运算如何帮助减少计算时间，并简化代码实现。 接下来可以在下篇博客中深入探讨 位运算的更高级应用！！！ 2....缺点： 位运算的实现较为复杂，需要一定的理解和推理。 3.3.3 总结 常见解法： 位运算（按位统计）：通过统计每一位 1 的出现次数来解决问题，时间复杂度 O(n)，空间复杂度 O(1)。...4.5 总结 这个算法通过异或运算和最低有效位（lsb）分组来有效地找出缺失的两个数字，时间复杂度为 O(n)，空间复杂度为 O(1)，是一个高效且简洁的解决方案。 5....总结 异或运算： 异或是解决这类问题的常见技巧，特别适用于找到数组中唯一的、缺失的或者出现异常次数的元素。 异或满足自反性和交换律，非常适合用来消除重复的数字或找到不重复的元素。
，异或的规则是转换成二进制比较，相同为0，不同为1....一个数a与另一个数b异或的结果等于a^b，用结果（ a^b)异或a，就会得到b； 上面的结果，我们用代码来验证。代码( a=a^b; b=a^b; a=a^b;)可以转换成二进制计算。...a=a^b ; ———— 01=10^11 第一步得到结果C（ a^b)赋值给a，所以a此时等于01 b=a^b; ———— 10=01^11 第二步 用结果（ a^b)异或b，即用C（01）异或b（...a=a^b; ————-11=01^10 第三步，a（01）异或b（10），等于11。转为十进制a等于3. 最后打印出来，a等于3， b等于2. 第二种：用异或规则计算。 （规则：可以移动。...相同数异或等于0,任何数异或0等于本身） 第一步没变化，直接代入后面的代码进行计算。 第二步中b=a^b的 a^b转化为 a^b ^b ，其中让b^b等于0， a^0等于a。
所以将要比较的数 n 的第x位右移x位，与1按位与&，如果是0，第x位为0；如果是1，第x位是1 1.3 将一个数 n 的二进制表示的第 x 位修改成 1 要修改数n第x位为1就不能破坏原来的数，所以将...1移动x位，与1按位或|，只修改了我们想要修改的那一位 1.4 将一个数 n 的二进制表示的第 x 位修改成 0 要修改数n第x位为0就不能破坏原来的数，所以将1移动x位，取反~为0，与1按位与&，只修改了我们想要修改的那一位...1.6 提取一个 n 二进制表示中最右侧的 1 将数n取反后+1得到相反数-n，然后两数按位与&得到最右侧的1。...+无进位相加解决 我们知道无进位相加就是只相加不进位，所以我们只要解决了进位问题，那么问题就迎刃而解了，那么进位也只会在两个位都为1的情况下才会进位，观察发现进位的操作就是按位与&，注意要进位的是下一位...那么我们现在就是把有差异的那一位和nums异或并分类了，所以我们还要和一个完整的数组分类异或，抵消掉别的数，因为相同异或为0，不同异或为1，由于前面的分类，除了丢失的数，其他的数都抵消了，丢失的数也在异或的过程中把剩余位数补上了
要求时间复杂度是O(n)，空间复杂度是O(1)。...输出：对应每个测试案例，输出数组中只出现一次的两个数。输出的数字从小到大的顺序。九度OJ 样例输入：8 2 4 3 6 3 2 5 5 样例输出：4 6 分析： 按位异或^具有如下性质： 1....故用两次异或运算特点可以解决此问题： (1) 先从头到尾依次异或原数组中的每一个数字，那么最终的结果刚好只出现一次的数字的异或结果，因为成对出现的两次的数字全部在异或中抵消了。...(2) 原数组中有两个数字只出现一次，且两个只出现一次的数肯定不相等，它们的异或结果一定不为0，一定有一个数在某位(记作倒数第k位)上有1，另外一个数的此位上没有1。...因此，我们可以再次运用按位异或运算，分别得到两部分只出现一次的数。
n的二进制表示的第X位修改成1： 那修改之前第X位就是0；先右移，然后直接对X位进行|(按位或)，0|1=1；就是(n>>x)|1; 3.将一个数的n的二进制表示的第X位修改成0： 上面我们说了0&1=...7.异或(^):消消乐 a^a=0;能用异或解决的题，都非常的巧妙。...8 是丢失的数字，因为它没有出现在 nums 中。 算法思想 直接使用异或，全部的数字是0到nums.size();将全部的数字和数组中的都异或一次，就转化成了单身狗的问题了。...，我们需要异或后然后异或加上进位，那么进位怎么来呢，1和1才产生进位,因此我们把两个数a,b按位与，就得到了进位的二进制，还需要将1左移，因为要进到前面的高位，然后异或上刚才无进位相加的结果，循环此操作...你必须设计并实现线性时间复杂度的算法(O(N))且使用常数级空间(O(1))来解决此问题。
使用位运算，通过 1 位，生成一个只有第 i 位为 1 的数（其余位均为 0），再与 n 进行按位与运算 n & (1 << i)。...时间复杂度分析： 我们只需要遍历数组两次：一次遍历 nums 数组，一次遍历从 0 到 n，每次异或操作的时间复杂度为 O(1)，因此整体时间复杂度为 O(n)。...对于每一位（从第 0 位到第 31 位），进行以下操作： 统计数组中所有数字在该位上 1 的个数，称为 sum。...通过理解异或运算的特性，我们可以高效地解决这类问题。 相关异或运算的特性： 相同的数异或为 0：a ^ a = 0。 任意数与 0 异或结果为该数本身：a ^ 0 = a。...通过这些题目可以看到，异或操作 在处理查找、去重和加法等问题时非常高效，尤其适合那些与数字位操作相关的场景。
位掩码：权限管理、分组操作。 优化求和：连续数组求和、K次出现问题。 面试中的价值 考察代码功底：理解位运算需要扎实的基础。 解决实际问题：在性能敏感场景中，位运算常用于算法优化。...如果把 0 ~ n 所有数字的异或结果与数组中的所有数字的异或结果再次异或，它们成对的数字会互相抵消为 0，只剩下缺失的数字。 核心思路： 将数组中的所有元素进行异或。...适用场景：数字缺失、数组中重复元素等问题，异或法都可以高效解决。...n) 空间复杂度：O(n) 3.4.5 解法总结 3.5 总结 异或法 是解决 缺失数字 问题的最优解之一，利用位运算性质，简单高效，时间复杂度为 O(n)，空间复杂度为 O(1)。...总结要点 异或运算 是位运算解决重复出现问题的核心思想： 相同为0，0与任何数异或等于数本身。 位统计 + 取模：通过逐位统计 1 的个数，可以解决 K次出现问题。
一、常见位运算总结 在讲解例题前，我们先来看一下位运算一般会出现在什么场景中，以及如何使用，需要注意的是本篇学习的前提是你要掌握基本的位运算的知识点，比如运算符及二进制等 1.1 基础位运算 按位与 &...:有0就是0 按位或|:有1就是1 按位异或^:相同为0，相异为1（其实就是无进位相加） 1.2 确定一个数的二进制表示中第x位是0还是1 比如数n:0110101001 我们要判断它的第x位是0还是1...我们只需要让它左移x位然后按位与1 1.3 将一个数二进制表示中的第x位修改成1 比如数n:0110101001 我们要让第x位修改位1 我们只需要让1左移x位然后与它按位或 1.4 将一个数二进制表示中的第...你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。...消失的两个数字 给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？ 以任意顺序返回这两个数字均可。
看题目描述很简单，那么，如何解决呢？ 2. 思路1 — 双重循环查找 最简单的方案是两层循环比较。...思路4 — 按位异或 如果题目变成一个数组里除了一个数字之外，其他数字都出现两次，找到这一个数字，我们很容易就可以实现了。...办法是有的，既然两个数字是不同的，那么最终的异或结果一定不为 0，而这个结果数字中，为 1 的位表示两个出现一次的数中，这两位不同。...假设异或结果的数字中，第 n 位为 1，则说明两个只出现一次的数字中，一个第 n 位为 1，一个第 n 位为 0，我们可以将原数组划分为两个数组，分别是所有第 n 位为 0 的数组成的数组和所有第 n...位为 1 的数组成的数组，这样既可以保证所有相同的数都被放入同一个数组，也可以保证两个只出现了一次的数分别被放入两个不同的数组，于是，最终我们将问题转化为找到分别在两个数组找到每个数组中只出现一次的一个数字
按位判断与添加： 通过位移和按位或操作，确保每个字符的状态准确记录在位图中。 时间复杂度和空间复杂度 时间复杂度：O(n)，其中 n 是字符串的长度，需要遍历字符串一次。...提示： n == nums.length 1 n <= 10^4 0 n nums 中的所有数字都独⼊无二 进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题...如果我们把数组中的所有数，以及 [0, n] 中的所有数全部「异或」在一起，那么根据「异或」运算的「消消乐」规律，最终的异或结果应该就是缺失的数。...时间复杂度和空间复杂度 时间复杂度：O(n)，其中 n 是数组的长度，需要遍历数组两次。 空间复杂度：O(1)，仅使用一个整数变量来存储异或结果。...通过以下步骤找到缺失的两个数字： 初始异或操作 将 nums 数组中所有数与 [1, n + 2] 区间内的所有数依次异或。
我们知道所有数字包括字母、符号等在计算机中都是以二进制形式存储的，而位运算就是直接对二进制进行操作，常见的位运算包括以下几种： 按位与:& 按位或:| 按位异或:^ 左移:<< 右移:>> 取反:~ 这些位运算符号按照优先级顺序排序如下...按位或(|) 按位或运算法则可以概括成“同假才假，反之则真”，在0和1之间的运算，有以下形式： 1 | 1 = 1 1 | 0 = 1 0 | 0 = 0 同样还用数字5和数字6举例，利用上述相同方式在二者之间做按位或运算...按位异或(^) 按位异或运算法则可以概括成“相同则假，不同则真”，在0和1之间的运算，有以下形式： 1 | 1 = 0 1 | 0 = 1 0 | 0 = 0 仍然还是数字5与数字6为例利用上述相同方式在二者之间做按位异域运算...已经介绍完了这六个位运算符是如何对二进制进行操作的，可是简单的介绍并不能体现出位运算的高大上，下面利用位运算的技巧解决一些问题，这些问题并不是很难，但是我们从中可以认识到位运算的便捷，以及加深对位运算操作的印象...而利用按位异或运算只需引入一个第三变量就可以解决这个问题，利用上文提及的异或性质1和3、以及“相同则假”的法则即可。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
即时通信 IM
云直播
实时音视频
