資訊專欄INFORMATION COLUMN
摘要：整除法復(fù)雜度時(shí)間空間思路最簡(jiǎn)單的解法，不斷將原數(shù)除以，一旦無法整除，余數(shù)不為，則說明不是的冪，如果整除到，說明是的冪。二進(jìn)制位計(jì)數(shù)法復(fù)雜度時(shí)間空間思路的冪有一個(gè)特性，就是它的二進(jìn)制表達(dá)中只有開頭是，后面全是。
Power of Two
整除法 復(fù)雜度Given an integer, write a function to determine if it is a power of two.
時(shí)間 O(1) 空間 O(1)
思路最簡(jiǎn)單的解法，不斷將原數(shù)除以2，一旦無法整除，余數(shù)不為0，則說明不是2的冪，如果整除到1，說明是2的冪。
二進(jìn)制位計(jì)數(shù)法 Count Set Bits 復(fù)雜度時(shí)間 O(1) 空間 O(1)
思路2的冪有一個(gè)特性，就是它的二進(jìn)制表達(dá)中只有開頭是1，后面全是0。比如4是100。所以我們只要數(shù)出有多少個(gè)1，就可以判斷是不是2的冪。
注意利用位操作解題時(shí)，要注意符號(hào)位的判斷，由于2的冪一定是正數(shù)，我們需要加以判斷。
代碼public class Solution {
public boolean isPowerOfTwo(int n) {
return Integer.bitCount(n) == 1 && n > 0;
}
}
減一相與法
復(fù)雜度
時(shí)間 O(1) 空間 O(1)
思路對(duì)于剛所說的特性，其實(shí)我們不一定要數(shù)出幾個(gè)1，實(shí)際上對(duì)于1000這種形式的二進(jìn)制數(shù)，我們只要將它減1得到111，再做位與，一定是0。
代碼public class Solution {
public boolean isPowerOfTwo(int n) {
return ((n & (n-1))==0 && n>0);
}
}
Power of Four
整除法 復(fù)雜度Given an integer, write a function to determine if it is a power of four.
時(shí)間 O(1) 空間 O(1)
思路最簡(jiǎn)單的解法，不斷將原數(shù)除以4，一旦無法整除，余數(shù)不為0，則說明不是4的冪，如果整除到1，說明是4的冪。
代碼private boolean bruteForceMod(long num){
if(num <= 0) return false;
while(num % 4 == 0){
num = num / 4;
}
return num == 1;
}
位計(jì)數(shù)法
復(fù)雜度
時(shí)間 O(1) 空間 O(1)
思路1 0 0000 0001 4 0 0000 0100 16 0 0001 0000 64 0 0100 0000 256 1 0000 0000
仔細(xì)觀察可以發(fā)現(xiàn)，4的冪的二進(jìn)制形式中，都是在從后向前的奇數(shù)位有一個(gè)1，所以只要一個(gè)數(shù)符合這個(gè)模式，就是4的冪。
代碼private boolean bruteForceBit(long num){
boolean res = false;
if(num <= 0) return res;
for(int i = 1; i <= 64; i++){
// 如果該位是0，則不操作
if((num & 1) == 1){
// 如果是偶數(shù)位為1，說明不是4的冪
if(i % 2 == 0) return false;
// 如果是奇數(shù)位為1，如果之前已經(jīng)有1了，則也不是4的冪
if(res){
return false;
} else {
// 如果是第一次出現(xiàn)技術(shù)位為1，則可能是4的冪
res = true;
}
}
num = num >>> 1;
}
return res;
}
位與法
復(fù)雜度
時(shí)間 O(1) 空間 O(1)
思路在Power of Two中，我們有一個(gè)解法是通過判斷n & (n - 1)是否為0來判斷是否為2的冪，因?yàn)?的冪肯定也是2的冪，所以這也可以用到這題來。那4的冪和2的冪有什么區(qū)別呢？根據(jù)上一個(gè)解法，我們知道4的冪的1只可能在奇數(shù)位，而2的冪的1可能在任意位，所以我們只要判斷是不是奇數(shù)位是1就行了。因?yàn)楦鶕?jù)n & (n - 1)我們已經(jīng)篩出來那些只有1個(gè)1的數(shù)了，所以和010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101 也就是0x5555555555555555相與就能知道1是在奇數(shù)位還是偶數(shù)位了。
代碼private boolean smartBit(long num){
return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0x5555555555555555l) == num);
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66169.html
三道基本相同的題目，都可以用位操作、遞歸和迭代來做。 Power of Two 1. Bit Manipulation -- 2 ms beats 21.88% public class Solution { public boolean isPowerOfTwo(int n) { return n>0 && (n&(n-1))==0; } } 2. Iterat...
摘要：描述給定一個(gè)整數(shù)位有符號(hào)整數(shù)，請(qǐng)編寫一個(gè)函數(shù)來判斷它是否是的冪次方。出現(xiàn)在奇數(shù)位，那么此數(shù)與與運(yùn)算為本身。何睿何睿數(shù)字不為零的二級(jí)制只有一個(gè)中的位置出現(xiàn)在第位，或第位，或第位源代碼文件在這里。 Description Given an integer (signed 32 bits), write a function to check whether it is a power of...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...
摘要：題目要求判斷一個(gè)整數(shù)是否是的冪。思路和代碼當(dāng)我們從二進(jìn)制的角度來看，這個(gè)題目就非常簡(jiǎn)單了。其實(shí)題目的要求等價(jià)于該整數(shù)對(duì)應(yīng)的二進(jìn)制數(shù)中，一共有幾個(gè)。該題目的難點(diǎn)在于考慮邊界情況，比如，即。 題目要求 Given an integer, write a function to determine if it is a power of two. 判斷一個(gè)整數(shù)是否是2的冪。 思路和代碼 當(dāng)我...
閱讀 1332·2021-10-27 14:14
閱讀 3583·2021-09-29 09:34
閱讀 2488·2019-08-30 15:44
閱讀 1733·2019-08-29 17:13
閱讀 2577·2019-08-29 13:07
閱讀 880·2019-08-26 18:26
閱讀 3351·2019-08-26 13:44
閱讀 3217·2019-08-26 13:37
