所有整数的异或

Question

所有整数的异或

4

我是一名初级web开发人员，正在尝试提高自己的逻辑和算法技能。在学习过程中，我发现了像下面这样的编码挑战，请问对于这种问题，你能指导我应该研究、检查、复习哪些方面吗？对于下面的挑战，你能给我一个解决它的思路，例如一些伪代码吗？

挑战：

你会得到Q个查询。每个查询包含两个整数L和R。对于每个查询，请输出所有二进制表示中只有一个位为1的整数范围内所有整数的异或值。

输入格式：

第一行包含Q个查询。

接下来的Q行包含两个整数L和R。

输出格式：

每个查询输出一个整数，表示答案。

约束条件：

1 ≤ Q ≤ 105
1 ≤ L ≤ R ≤ 1018

示例输入：

1
60 - 130

示例输出：

192

我目前尝试过的方法：

const sumQuery = (q, n) => {
  let bitCount = [];
  //travers the bits
  for(let i = 0; i < 32; i++) {
    for(let j = 0; j < n; j++) {
     // check whether the current bit is
     let temp = Math.sqrt(arr[j]) * 2 );
     if(temp % 2 !== 0 ) {
      console.log(temp)
     }
    }
  }
}

- Antonio Salazar

1

只有2的幂次方在它们的二进制表示中只有一个位。因此，你只需要关心1、2、4、8、16、32、64、128、256、512这些数字。对于示例测试用例，结果为64 ^ 128 = 192。 - maazadeeb

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Artem K · Accepted Answer

您的问题有两部分，我将尝试分别回答它们。

1）为了提高逻辑/算法技能，您应该学习什么？首先，您应该确定自己这样做的目的（尝试获得更好的工作/建立计算机科学基础/学习特定系统或框架的功能等）。一旦确定了您想要提高的确切原因，确定需要收集哪种知识/技能将变得更加容易。以下是我提到的路径的一些建议：

a）尝试获得更好的工作。如果是这种情况-我的唯一建议是练习编码面试题。在面试中解决这些问题的能力往往比您的知识深度更重要（根据我的个人经验）。以下是您可以开始的几个地方：

https://leetcode.com
https://www.codewars.com/
破解编程面试（书）

b）建立计算机科学基础。有几种方法可以做到这一点（包括上学）。如果您正在寻找一个计划，我的建议如下：

免费的计算机科学课程大纲（https://github.com/ossu/computer-science）
著名的免费麻省理工学院课程（https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/）
Coursera 上的付费数据结构和算法课程（https://www.coursera.org/specializations/data-structures-algorithms）

c) 更好地理解某些系统。为此，我强烈建议阅读该系统的实现或进行更深入的教程。建议：

一个很好的js库，可以阅读和理解 - Immutable-js (https://github.com/immutable-js/immutable-js)
Rails教程 (https://www.railstutorial.org/book/beginning)

2) 如何解决您特定的编码挑战。这里有一个非常好的分解，描述了80%的挑战，由别人描述(https://www.codechef.com/PRJRF14/problems/XORSN)。我建议您对二进制数据和整数之间XOR的概念有一个扎实的理解。

可能的解决步骤(我不会用js为您编写它，因为您想自己解决它):

如Maaz Syed Adeeb所提到的-在搜索给定整数范围的异或值时，只需要考虑2的幂（因为它们是唯一具有一位二进制表示的数字）。
注意给定约束条件中所有的2的幂：valid = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
确定其中哪些在给定范围内
将每个valid整数转换为二进制
使用此逻辑找到每个valid整数之间的XOR值

Rule 1 : If both bits are 1 then XOR’ed bit will be 0.
Rule 2 : If both bits are 0 then XOR’ed bit will be 0.
Rule 3 : If one bit is 0 and one bit is 1 XOR’ed bit will be 1.

将您上次 XOR 比较的二进制代码转换为整数。

祝好运！