Javascript 程序检查两个数字是否是彼此的位循环

什么是位循环？

位循环是指两个数的二进制数位相同且循环移位之后可以完全重合。比如数字 89 和数字 98 的二进制表示都是 1011001，因此它们是彼此的位循环。

Javascript 实现检查位循环

暴力枚举法

判断两个数是否为位循环，最初的想法可能是枚举其中一个数的所有循环移位，然后与另外一个数进行比较。

var isRotation = function(num1, num2) {
  if (num1 < 0 || num2 < 0) {
    return false;
  }
  
  var len1 = getNumberLength(num1),
      len2 = getNumberLength(num2);
  if (len1 !== len2) {
    return false;
  }
  var str1 = num1.toString();
  var str2 = num2.toString();
  for (let i = 0; i < len1; i++) {
    str1 = str1.substring(1) + str1[0];
    if (str1 === str2) {
      return true;
    }
  }
  return false;
}
var getNumberLength = function(num) {
  return num.toString().length;
}

该算法的时间复杂度是 O(n^2), 因为需要枚举其中一个数字的所有循环移位。该算法不够高效，因为它需要枚举很多次。

位运算法

我们可以使用位运算的方法优化暴力枚举法。具体地，我们可以枚举第一个数字的所有循环移位，而不是枚举所有的位数。

var isRotation = function(num1, num2) {
  if (num1 < 0 || num2 < 0) {
    return false;
  }
  
  var len1 = getNumberLength(num1),
      len2 = getNumberLength(num2);
  if (len1 !== len2) {
    return false;
  }
  
  var temp = num2;
  
  for (let i = 0; i < len1; i++) {
    if (temp === num1) {
      return true;
    }
    temp = ((temp << 1) | (temp >> (len2 - 1))) & ((1 << len2) - 1);
  }
  
  return false;
}
var getNumberLength = function(num) {
  return num.toString().length;
}

用位运算法来判断数字是否是彼此的位旋转，不仅时间复杂度低，且高效优化，时间复杂度是 O(n).

性能对比

我们利用下面的代码计算这两个算法的在不同位数下的运算时间。

function runBenchmark() {
  for (let i = 1; i < 17; i++) {
    const x = Math.pow(10, i);
    const y = Math.floor(Math.random() * x) + 1;
    const z = Math.floor(Math.random() * x) + 1;
    const totalTime1 = benchmark(isRotation1, x, y, z);
    const totalTime2 = benchmark(isRotation2, x, y, z);
    console.log(`${'\n'}X: ${x}. Y: ${y}. Z: ${z}`);
    console.log(`Total time isRotation 1: ${totalTime1} seconds.`);
    console.log(`Total time isRotation 2: ${totalTime2} seconds.`);
  }
}
function benchmark(fn, x, y, z) {
  const start = performance.now();
  fn(y, z);
  const end = performance.now();
  return ((end - start) / 1000).toFixed(4);
}

值得注意的是，位运算法的时间复杂度只与数字长度有关，而暴力枚举法则只改变了常数项。

我们可以看到，随着数字长度的增加，位运算法的运行时间维持在较低的水平，而暴力方法的运行时间则急剧增长。

总结

我们学会了如何使用位运算的方法来判断数字是否是彼此的位旋转。该方法可以优化时间复杂度。具体而言，用位运算法优化后，每个位移操作需要 O(1) 的时间复杂度，因此算法的总时间复杂度为 O(n)，可以很好地处理大数值。