如何找到2的最大功率小於給定的數

Question

我需要找到2的最大功率小於給定的數。
而我堅持並找不到任何解決方案。

代碼：

public class MathPow 
{ 
    public int largestPowerOf2 (int n) 
    { 
     int res = 2;   
     while (res < n) { 
       res =(int)Math.pow(res, 2); 
     } 

     return res; 
    } 
} 

這並不正常工作。

測試輸出：

Arguments Actual Expected 
------------------------- 
9   16  8  
100  256 64  
1000  65536 512  
64  256 32  

如何解決這個問題？

Answer 1

更改res =(int)Math.pow(res, 2);到res *= 2;這將返回大於res的下一個2的冪。
您正在查找的最終結果因此在結束後最終將爲res/2。

爲了防止代碼溢出int值空間，您應該/可以將res的類型更改爲double/long，任何可以保存比int更高值的值。最後你必須投一次。

Answer 2

找到從左到右的第一組位，並使所有其他設置位0s。

如果只有一組位，則向右移一位。

Answer 3

您正在平方res每次，這意味着您計算2^2^2^2而不是2^k。
您的評估更改爲以下幾點：

int res = 2; 
while (res * 2 < n) { 
    res *= 2; 
} 

更新：

當然，你需要檢查的INT溢出，在這種情況下，檢查

而（RES < =（n-1）/ 2）

好像好多了。

Answer 4

public class MathPow 
{ 
    public int largestPowerOf2 (int n) 
    { 
     int res = 2;   
     while (res < n) { 
       res =res*2; 
     } 

     return res; 
    } 
} 

Answer 5

您可以使用此bit hack：

v--; 
v |= v >> 1; 
v |= v >> 2; 
v |= v >> 4; 
v |= v >> 8; 
v |= v >> 16; 
v++; 
v >>= 1; 

Answer 6

爲什麼不使用日誌？

public int largestPowerOf2(int n) { 
    return (int)Math.pow(2, Math.floor(Math.log(n)/Math.log(2)); 
} 

log(n)/log(2)告訴你2進入一個數字的次數。通過發言，獲得四舍五入的整數值。

Answer 7

Integer有一個很好的功能，numberOfLeadingZeros。

有了它，你可以做

0x80000000 >>> Integer.numberOfLeadingZeros(n - 1); 

哪個做奇怪的事情時n爲0或1，但對於那些投入有沒有明確的「兩個低於n最高權力」。

編輯：this answer甚至更​​好

Answer 8

Integer.highestOneBit(n-1); 

對於n <= 1的問題並沒有真正意義。有興趣的讀者可以在該範圍內做什麼。

在Hacker's Delight這是一個很好的收集bit twiddling算法。

Answer 9

p=2; 
while(p<=n) 
{ 
    p=2*p; 
} 
p=p/2; 

Answer 10

如果這個數是2的冪，那麼答案是顯而易見的。 （只是位移）如果不好，那麼它也可以通過位移來實現。

以二進制表示法查找給定數字的長度。 （在13二進制= 1101;長度爲4）

然後 變速2由（4-2） // 4是給定數目的二進制

下面的java代碼將解決這一長度對於BigIntegers（基本上所有數字都是如此）。

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));   

    String num = br.readLine(); 
    BigInteger in = new BigInteger(num); 
    String temp = in.toString(2); 

    System.out.println(new BigInteger("2").shiftLeft(temp.length() - 2)); 

Answer 11

這裏是一個遞歸位移法我寫了這個目的：

public static int nextPowDown(int x, int z) { 
    if (x == 1) 
     return z; 
    return nextPowDown(x >> 1, z << 1); 
} 

或更短的定義：

public static int nextPowTailRec(int x) { 
    return x <= 2 ? x : nextPowTailRec(x >> 1) << 1; 
} 

所以在main方法讓z參數總是相等1。可惜的是默認參數是不是可以在這裏找到：

System.out.println(nextPowDown(60, 1));    // prints 32 
System.out.println(nextPowDown(24412, 1));    // prints 16384 
System.out.println(nextPowDown(Integer.MAX_VALUE, 1)); // prints 1073741824 

Answer 12

你可以消除n中的至少顯著位，直到n爲2的冪你可以使用位運算符，並與n和n-1，其中將消除n的最低顯著位，直到N將是2的冪。如果原來N將是2的電源，然後你必須做的是1

public class MathPow{ 
    public int largestPowerOf2(int n){ 
     if((n & n-1) == 0){ //this checks if n is a power of 2 
     n--; //Since n is a power of 2 we have to subtract 1 
     } 
     while((n & n-1) != 0){ //the while will keep on going until n is a power of 2, in which case n will only have 1 bit on which is the maximum power of 2 less than n. You could eliminate the != 0 but just for clarity I left it in 
     n = n & n-1; //we will then perform the bitwise operation AND with n and n-1 to eliminate the least significant bit of n 
     } 
     return n; 
    } 
} 

說明減少N：

當你有一個數n（不是2的冪）時，小於n的2的最大冪總是n中的最高有效位。在n是2的冪的情況下，小於n的2的最大冪是在n中唯一的位之前的位。

例如，如果我們有8（其是2的第三功率），其二進制表示爲1 00 0是粗體將是2最大功率N之前。既然我們知道每個二進制數字代表2的冪，那麼如果我們有n是2的冪數，那麼2的最大冪就是2之前的冪，這將是位在n之前的唯一一點之前。

對於數n，這不是2的冪，並且不是0，我們知道在二進制表示中，n將會有不同的位，這些位將僅表示各種冪的和其中重要的是最重要的一點。那麼我們可以推斷出n只是最重要的位加上一些其他的位。由於n是以一定長度的比特來表示的，而最重要的比特是2的最大冪，所以我們可以用這個比特數來表示，但它也是我們可以用那麼多比特來表示的最小數目，那麼我們可以得出結論：最重要的比特是比n更低的2的最高冪，因爲如果我們增加另一比特來表示下一個2的冪，那麼我們將具有大於n的2的冪。

實施例：

例如，如果我們有168（其爲二進制10101000）的同時將採取168和減1，其爲167（這是在二進制10100111）。然後我們會在兩個數字上進行按位與。 例子：

10101000 
& 10100111 
------------ 
    10100000 

我們現在有二進制數10100000.如果我們減去1從它和我們使用的位與兩個數字，我們拿到千萬爲128，這是2〜7的動力。

實施例：

10100000 
& 10011111 
------------- 
    10000000 

如果n是爲原本是2的冪然後我們必須從n個減去1。例如，如果n爲16，即二進制爲10000，那麼我們將減去1，這將使我們得到15，即二進制爲1111，並且我們將它存儲在n中（這就是if）。然後，我們進入按位運算符AND與n和n-1（它將是15（二進制1111）012（二進制1110））的時間。

實施例：

1111 
& 1110 
-------- 
    1110 

現在我們留下14.然後，我們執行按位與具有n和n-1，它是14（二進制1110）& 13（二進制1101）。

例子：

1110 
& 1101 
--------- 
    1100 

現在我們有12個，我們只需要消除最後一個至少顯著位。再次，我們在n和n-1上執行按位AND，它是12（二進制1100）和11（二進制1011）。

例

1100 
& 1011 
-------- 
    1000 

我們最後剩下8這是2級不少於16

Answer 13

我看到上面的另一個解決方案BigInteger的最大功率，但實際上是相當緩慢。一個更有效的方法，如果我們要超越整數和長

BigInteger nvalue = TWO.pow(BigIntegerMath.log2(value, RoundingMode.FLOOR)); 

其中TWO簡直是BigInteger.valueOf(2L)

和BigIntegerMath從番石榴拍攝。

Answer 14

public class MathPow 
{ 
    public int largestPowerOf2(int n) 
    { 
     int res = 1;   
     while (res <= (n-1)/2) 
     { 
      res = res * 2; 
     } 

     return res; 
    } 
} 

Answer 15

我認爲這是最簡單的方法。

Integer.highestOneBit(n-1);

Answer 16

如果號碼是一個整數，你可以隨時將其更改爲二進制然後找出位數。

n = (x>>>0).toString(2).length-1 

Answer 17

簡單的位操作應該工作

public long largestPowerOf2 (long n) 
{  
//check already power of two? if yes simply left shift 
    if((num &(num-1))==0){ 
     return num>>1; 
    } 

    // assuming long can take 64 bits  
    for(int bits = 63; bits >= 0; bits--) { 
     if((num & (1<<bits)) != 0){ 
      return (1<<bits); 
     } 
    } 
    // unable to find any power of 2 
    return 0; 
    } 

Answer 18

有點晚了，但...

（假設32位的數字。）

n|=(n>>1); 
n|=(n>>2); 
n|=(n>>4); 
n|=(n>>8); 
n|=(n>>16); 
n=n^(n>>1); 

說明：

第一個|確保設置原始的最高位和最高的第二位。第二個|確保這兩個以及接下來的兩個都是，等等，直到你可能擊中所有32位。即

100010101 - > 111111111

然後我們刪除所有，但與1組成該字符串異或運算1的串的最高位移動一個向左，而我們最終只是一個最高位接着是0。