数学

四则运算

大数加法

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addStrings = function(num1, num2) {
    // 将较短的字符串填充为等长的字符串，并在前面补零。
    const length1 = num1.length
    const length2 = num2.length
    const length = Math.max(length1,length2) + 1
    num1 = new Array(length - length1).fill("0").join("") + num1
    num2 = new Array(length - length2).fill("0").join("") + num2
    // 转换为字符数组 
    let stack1 = num1.split("")
    let stack2 = num2.split("")
    let c = 0 // 存储进位
    let result = "" // 存储最终的计算结果
    // 逐位相加
    for(let i = length - 1; i >= 0; i--){
        let a = Number(stack1[i])
        let b = Number(stack2[i])
        let sum = a + b + c
        if(sum >= 10){
            sum = sum - 10
            c = 1 
        }else {
            c = 0
        }
        result = sum + result
    }
    if(/^0+$/.test(result)) return "0"
    // 处理前导零
    return result.replace(/^0+/,"")
};

位运算

移位

异或

其他

最大公约数

求最大公约数一般使用辗转相除法

// 递归
function gcd(a, b) {
  if (b) {
    return gcd(b, a % b);
  }
  return Math.abs(a);
}
// 迭代
function gcd(a,b) {
    a = Math.abs(a);
    b = Math.abs(b);
    if (b > a) {var temp = a; a = b; b = temp;}
    while (true) {
        if (b == 0) return a;
        a %= b;
        if (a == 0) return b;
        b %= a;
    }
}

快速幂取模

(a ^ b) \mod c

// 常规算法 O(n)
function mod(a, b, c) {
  let ans = 1;
  for (let i = 0; i < b; i++) {
    ans = (ans * a) % c;
  }
  return ans;
}
console.log(mod(79, 587, 391));

// 快速算法 O(log2n)
function quickMod(a, b, n) {
  let ans = 1;
  while (b) {
    if (b & 0x1) ans = (ans * a) % n;
    a = (a * a) % n;
    b >>= 1;
  }
  return ans;
}
console.log(quickMod(79, 587, 391));