算法学习位运算：快速幂

<h2 id="异或运算的笔记技巧：">异或运算的笔记技巧：</h2> <p><strong>1.如果 <code>a ^ b = c</code> 成立，那么<code>a ^ c = b</code> 与 <code>b ^ c = a</code> 均成立</strong></p> <p>如果有三个数，满足其中两个数的异或值等于另一个值，那么这三个数的顺序可以任意调换。</p> <p><strong>2.把nums存入hashMap,如果随便定义一个a，并把a与hashMap里面的b操作。a ^ b = c , 如果c在hashMap里也有，那么hashMap里面，可以挑两个数来^出a出来，随便定义的a就是可证实的a了。</strong></p> <p>参考题目：</p> <p>幂运算：</p> <p>x^n，</p> <p>暴力法：自己乘自己，乘n遍</p> <p>快速幂的运算，x^n = x^0.5n * x^0.5n 所以，求出x^0.5n，再对自己运算一次，就能得出答案，节省了很多的运算量。</p> <p>算法的核心，就是x^n 当n为偶数的时候，执行上面写的转换，当n为奇数的时候，就可以执行x^n = x^(n - 1)  * x;，就可以继续递归执行（n-1的偶数）的运算了</p> <p>注意：n是负数的时候，让x = 1/x,然后n就可以变成正数进行运算</p> <p>递归算法：</p> <pre><code>var myPow = function (x, n) { // console.log("遍历到了",n);
if (n == 0) { return 1; } if (n == 1) { return x; } if (n < 0) { x = 1 / x; n = -n; } if ((n % 2) == 0) { let A = myPow(x, n / 2); return A * A; } else { let A = myPow(x, n - 1); return A * x; } }</code></pre> <p>迭代算法：</p> <p>主要就是根据n，除以二一次，自己就乘以自己一次，假如碰到了奇数，执行x^n = x^(n-1) * x，再执行x^n = x^0.5n * x^0.5n</p> <pre><code>var myPow = function (x, n) { let N = n; if (N < 0) { x = 1 / x; N = -N; } let ans = 1; let current_product = x; for (let i = N; i; i /= 2) { if ((i % 2) == 1) { ans = ans * current_product; } current_product = current_product * current_product; } return ans; }</code></pre>