使网站有流量,上海 网站工作室,长沙域名注册,网站开发职能前言
幂运算为常见的数学运算#xff0c;形式为 a b a^b ab #xff0c;其中a为底数#xff0c;b为指数#xff0c;
力扣中#xff0c;幂运算相关的问题主要是判断一个数是不是特定正整数的整数次幂#xff0c;以及快速幂的处理。
1.求2的幂
力扣231题#xff0c;给…前言
幂运算为常见的数学运算形式为 a b a^b ab 其中a为底数b为指数
力扣中幂运算相关的问题主要是判断一个数是不是特定正整数的整数次幂以及快速幂的处理。
1.求2的幂
力扣231题给你一个整数 n请你判断该整数是否是 2 的幂次方。如果是返回 true否则返回 false 。
分析第一种方法是我们可以用通过逐渐缩小n值来判断是否是2的幂次方只需要循环用除的方法就可以了还需要判断一下n是否是正整数如果不是就直接返回false。第二种方法是位运算如果n是2的幂次方那么n的二进制表示就只有一个1如果存在非负整数 k 使得 n 2 k n2^k n2k则 n 的二进制表示为 1 后面跟 k 个0比如n4其二进制表示为 ( 0100 ) 2 (0100)_2 (0100)2,n-1也就是3的二进制表示则为 ( 0011 ) 2 (0011)_2 (0011)2 使用位运算n (n - 1)如果结果为0就说明n是2的幂次方否则不是。
代码如下
/*** 采用除法* param n {number}* return {boolean}* */
function isPowerOfTwo(n) {if (n 0) {return false;}// 这里2可以替换为任意正整数m就是计算m的幂次方while (n % 2 0) {n parseInt(n / 2);}if (n 1) {return true;} else {return false;}
}/*** 采用位运算* param n {number}* return {boolean}* */function isPowerOfTwo(n) {if (n 0) {return false;}// 如果存在非负整数 k 使得 n2^k则 n 的二进制表示为 1 后面跟 k 个0return n (n - 1) 0;
}拓展知识采用循环除法的方法中2可以替换为任意正整数m就是计算m的幂次方。
2.求3的幂
力扣326题 给定一个整数写一个函数来判断它是否是 3 的幂次方。如果是返回 true 否则返回 false 。整数 n 是 3 的幂次方需满足存在整数 x 使得 n 3 x n 3^x n3x
分析用除法思路与上题一样。这里说一下还可以用位运算的解决办法。我们知道 3 0 1 , 3 1 3 , 3 2 9 , . . . , 3 19 1162261467 3^01,3^13,3^29,...,3^{19}1162261467 301,313,329,...,3191162261467 ,在最大正整数范围之内如果是3的幂就一定是1162261467的除数。
代码如下
function isPowerOfThree(n) {if (n 0) {return false;}// 2^31 - 1内最大的3的幂为3^191162261467,只要n为1162261647的除数就说明是3的幂次方return (1162261467 % n) 0;
}3.求4的幂
力扣342 题给定一个整数写一个函数来判断它是否是 4 的幂次方。如果是返回 true 否则返回 false 。整数 n 是 4 的幂次方需满足存在整数 x 使得 n 4 x n 4^x n4x 。
分析第一种方法还是可以用循环除法。第二种方法就是位运算这种方法可以在求2的幂的位运算解法进一步得出 4 k 4^k 4k其实就是 2 2 k 2^{2k} 22k 2的偶数次幂,判断二进制表示中1的位置是否出现在从低位开始的第偶数位上即可,这里规定最低位为第0位。比如n16,其二进制表示为 ( 00010000 ) 2 (00010000)_2 (00010000)21的位置为第4位。创建一个32位有符号整数 ( 10101010101010101010101010101010 ) 2 (10101010101010101010101010101010)_2 (10101010101010101010101010101010)2让其偶数为0奇数位为1与n进行位与运算如果结果为0说明n为4的幂次方数否则不是。为了使代码更简洁还可以将创建的32位有符号整数用16进制表示即 ( a a a a a a a a ) 16 (aaaaaaaa)_{16} (aaaaaaaa)16 , 也就是0xaaaaaaaa
代码如下
function isPowerOfFour(n) {if (n 0) {return false;}return (n (n - 1)) 0 (n 0xaaaaaaaa) 0;
}
