javascript - 所有整数的异或

Question

我是一名 jr web 开发人员，试图提高我的逻辑/算法技能，在学习时我发现了如下所示的编码挑战，对于这类问题，你能指出正确的方向吗，我的意思是我应该怎么做研究、检查、复习？对于下面的挑战，你能给我一个解决方法的想法吗，也许是一些伪代码？

CHALLENGE:

You are given Q queries. Each of the query contains two integers L and R. For each query print out the XOR of all integers in the given range which have only one bit in their binary representation.

Input format:

• The first line contains Q queries.
• Next Q lines contain two integers L and R

Output format:

Print one integer for each query denoting the answer

Constraints:

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

Sample input

1
60 - 130

Sample Output

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)
     }
    }
  }
} 

Answer 1

你的问题分为两部分，我会尽量分别回答。

1) 你应该学习什么来提高你的逻辑/算法技能？ 首先，你应该确定你这样做的目的(试图获得更好的工作/在 cs 中建立基础/学习特定系统或框架的功能等)。一旦你弄清楚你尝试改进的确切原因是什么，就可以更容易地确定你需要收集什么样的知识/技能。以下是我提到的路径的一些建议:

a) 试图找到一份更好的工作。如果是这样的话——我唯一的建议是练习你的编码面试问题。你的知识深度通常不如你在面试中解决这些问题的能力重要(根据我的个人经验)。您可以从以下几个地方着手:

• https://leetcode.com
• https://www.codewars.com/
• 破解编码面试(书籍)

b) 建立 CS 基础知识。有几种方法可以做到这一点(包括上学)。如果您正在寻找一个程序，我的建议如下:

• 免费提供完整的计算机科学类(class)大纲 ( https://github.com/ossu/computer-science )
• 著名的麻省理工学院免费类(class) ( https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/ )
• Coursera 中的付费数据结构和算法类(class) (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 所述 - 在给定整数范围内搜索 XOR 时，您只需考虑 2 的幂(因为它们是唯一具有一位二进制表示的整数)。
• 记下给定约束中 2 的所有幂 valid = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
• 确定其中哪些在给定范围内
• 将每个有效整数转换为二进制
• 使用此逻辑在每个有效 整数之间找到 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 比较的二进制代码转换为整数

祝你好运!