653
作者：小傅哥
博客：https://bugstack.cn
源碼：https://github.com/fuzhengwei/java-algorithms
一、前言
二、判斷2次方數(shù)
1. 整除法
2. 二進制
3. 求對數(shù)
4. 位計算
三、單元測試
四、常見面試題
一、前言
每一個知識的索引都可能會牽扯出一片的內容
記得以前看到一個文章內容，說國外的小孩留一個很開放的作文題目，但如果想把這樣一個作業(yè)寫下來，則需要索引大量的資料才能完成。但在這個過程中其實會收獲很多，也學會了如何學習。
其實像小傅哥去編寫這樣的《程序員數(shù)學》資料時，也會去橫向和縱向的對比一些數(shù)學上的文章和內容，有的來自維基百科，有的來自于論文資料，現(xiàn)在還可以從 chatGPT 中探索。
另外還有一份斯坦福大學的課程資料，小傅哥把它轉成 PDF 有需要的伙伴可以下載學習使用?！?a class="article-link" target="_blank" href="/tag/%E8%AE%A1%E7%AE%97%E6%9C%BA/">計算機課程資料 - 斯坦福大學 @肖恩·埃隆·安德森》https://github.com/fuzhengwei/java-algorithms
二、判斷2次方數(shù)
如果說判斷一個數(shù)字是否滿足2的次方，首先我會想到二進制，因為二進制的每一位都是2的次方數(shù)字。那么判斷一個數(shù)字是否為2的次方可以從二進制中的數(shù)字特性下手，比如我們可以做二進制數(shù)字的判斷，也就是一個數(shù)字的二進制必須只有1位為1，其他位都為0，那么這個數(shù)字就是2次方的數(shù)字。
??那除此之外還有其他手段嗎？我們接下來就分別實現(xiàn)下
1. 整除法
代碼實現(xiàn)
public?boolean?isPowerOfTwo01(int?number)?{
????if?(number?<?1)?return?false;
??
????int?dividedNumber?=?number;
????while?(dividedNumber?!=?1)?{
????????if?(dividedNumber?%?2?!=?0)?{
????????????return?false;
????????}
????????dividedNumber?=?dividedNumber?/?2;
????}
??
????return?true;
}
- 循環(huán)數(shù)字除以2的結果與2求模計算看余數(shù)是否為0，只要有一次為0，那么就不是2的次方數(shù)。
2. 二進制
代碼實現(xiàn)
public?boolean?isPowerOfTwo02(int?number)?{
????if?(number?<?1)?return?false;
????return?(number?&?(number?-?1))?==?0;
}
-
- 在斯坦福大學的計算資料中，有這么一條關于判斷2的次方數(shù)的內容；
f = (v & (v - 1)) == 0;
-
- 錯位進行 & 與運算，結果為0則是2次方數(shù)【過程如圖】。此外這里我們過濾了小于的數(shù)字，如果不過濾則需要使用；
f = v && !(v & (v - 1));
3. 求對數(shù)
代碼實現(xiàn)
public?boolean?isPowerOfTwo03(int?number)?{
????if?(number?==?0)
????????return?false;
????//?log8?=?log2^3?/?log2?=?3
????double?x?=?Math.log(number)?/?Math.log(2);
????//?向上和向下取整的結果判斷
????return?(int)(Math.ceil(x))?==?(int)(Math.floor(x));
}
- 此方式為計算2為底數(shù)的對數(shù)，如果得到的數(shù)字向上和向下取整結果一致，那么則是2的次方。這里做一個簡單的推到，加入 number = 8，那么 log8 = log2^3 也就是用 log2^3 與 log2 做對比。這樣就能看出來一個結果3，這個3是一個整數(shù)數(shù)字，則這個 number 也就是2次方數(shù)。
4. 位計算
代碼實現(xiàn)
public?boolean?isPowerOfTwo04(int?number){
????int?cnt?=?0;
????while?(number?>?0)?{
????????if?((number?&?1)?==?1)?{
????????????cnt++;
????????}
????????number?=?number?>>?1;
????}
????return?cnt?==?1;
}
- 這個其實就是最開始說的，如果一個數(shù)字滿足2次方，那么只要在二進制的轉換中，它只有1位是1就可以了。
三、單元測試
@Test
public?void?test_IsPowerOfTwo(){
????IsPowerOfTwo?isPowerOfTwo?=?new?IsPowerOfTwo();
????System.out.println(isPowerOfTwo.isPowerOfTwo01(8));
????System.out.println(isPowerOfTwo.isPowerOfTwo02(8));
????System.out.println(isPowerOfTwo.isPowerOfTwo03(163));
????System.out.println(isPowerOfTwo.isPowerOfTwo04(12));
}
@Test
public?void?test_math(){
????System.out.println(Math.ceil(Math.log(8)?/?Math.log(2)));
????System.out.println(Math.log(1));
????System.out.println(Math.E);
????System.out.println(Math.pow(Math.E,?Math.log(2)));
}
- 在單元測試中除了驗證4種判斷2次方數(shù)的計算方式，也提供了關于log的計算，默認log是基于指數(shù)E的計算。讀者也可以進行測試驗證。a 的 x 次方 = N 那么 x = log(a)N
四、常見面試題
- 如何判斷一個數(shù)字是2的次方數(shù)在Java中怎么計算log公式
- END -
