Reputation: 18622

How to find the largest power of 2 less than the given number

I need to find the largest power of 2 less than the given number.
And I stuck and can't find any solution.

Code:

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

This doesn't work correctly.

Testing output:

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

How to solve this issue?

Upvotes: 12

Answers (20)

Abhishek Auti

Reputation: 11

if(number>=2){

    while(result < number){
        result *=2;
    }
        result = result/ 2;
     System.out.println(result);
    }

Upvotes: 0

stinepike

Reputation: 54742

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

Upvotes: 3

Juvenik

Reputation: 950

/**
 * Find the number of bits for a given number. Let it be 'k'.
 * So the answer will be 2^k.
 */
public class Problem010 {

  public static void highestPowerOf2(int n) {
    System.out.print("The highest power of 2 less than or equal to " + n + " is ");
    int k = 0;
    while(n != 0) {
      n = n / 2;
      k++;
    }

    System.out.println(Math.pow(2, k - 1) + "\n");
  }

  public static void main(String[] args) {
    highestPowerOf2(10);
    highestPowerOf2(19);
    highestPowerOf2(32);
  }

}

Upvotes: 0

John Fehr

Reputation: 121

A bit late but...

(Assuming 32 bit number.)

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

Explanation:

The first | makes sure the original top bit and the 2nd highest top bit are set. The second | makes sure those two, and the next two are, etc, until you potentially hit all 32 bits. Ie

100010101 -> 111111111

Then we remove all but the top bit by xor'ing the string of 1's with that string of 1's shifted one to the left, and we end up with just the one top bit followed by 0's.

Upvotes: 4

user5132172

Reputation:

Here is a recursive bit-shifting method I wrote for this purpose:

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

Or shorter definition:

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

So in your main method let the z argument always equal 1. It's a pity default parameters aren't available here:

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

Upvotes: 3

recursion

Reputation: 374

Simple bit operations should work

 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;   
  }

Upvotes: 0

jajaperson

Reputation: 558

If the number is an integer you can always change it to binary then find out the number of digits.

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

Upvotes: 1

Piyush

Reputation: 1162

I think this is the simplest way to do it.

Integer.highestOneBit(n-1);

Upvotes: 2

VijayaLakshmi

Reputation: 11

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

        return res;
   }
}

Upvotes: 1

demongolem

Reputation: 9718

I saw another BigInteger solution above, but that is actually quite slow. A more effective way if we are to go beyond integer and long is

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

where TWO is simply BigInteger.valueOf(2L)

and BigIntegerMath is taken from Guava.

Upvotes: 0

Vyral

Reputation: 89

You could eliminate the least significant bit in n until n is a power of 2. You could use the bitwise operator AND with n and n-1, which would eliminate the least significant bit in n until n would be a power of 2. If originally n would be a power of 2 then all you would have to do is reduce n by 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;
   }
}

EXPLANATION:

When you have a number n (that is not a power of 2), the largest power of 2 that is less than n is always the most significant bit in n. In case of a number n that is a power of 2, the largest power of 2 less than n is the bit right before the only bit that is on in n.

For example if we had 8 (which is 2 to the 3rd power), its binary representation is 1000 the 0 that is bold would be the largest power of 2 before n. Since we know that each digit in binary represents a power of 2, then if we have n as a number that's a power of 2, the greatest power of 2 less than n would be the power of 2 before it, which would be the bit before the only bit on in n.

With a number n, that is not a power of 2 and is not 0, we know that in the binary representation n would have various bits on, these bits would only represent a sum of various powers of 2, the most important of which would be the most significant bit. Then we could deduce that n is only the most significant bit plus some other bits. Since n is represented in a certain length of bits and the most significant bit is the highest power of 2 we can represent with that number of bits, but it is also the lowest number we can represent with that many bits, then we can conclude that the most significant bit is the highest power of 2 lower than n, because if we add another bit to represent the next power of 2 we will have a power of 2 greater than n.

EXAMPLES:

For example, if we had 168 (which is 10101000 in binary) the while would take 168 and subtract 1 which is 167 (which is 10100111 in binary). Then we would do the bitwise AND on both numbers. Example:

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

We now have the binary number 10100000. If we subtract 1 from it and we use the bitwise AND on both numbers we get 10000000 which is 128, which is 2 to the power of 7.

Example:

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

If n were to be originally a power of 2 then we have to subtract 1 from n. For example if n was 16, which is 10000 in binary, we would subtract 1 which would leave us with 15, which is 1111 in binary, and we store it in n (which is what the if does). We then go into the while which does the bitwise operator AND with n and n-1, which would be 15 (in binary 1111) & 14 (in binary 1110).

Example:

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

Now we are left with 14. We then perform the bitwise AND with n and n-1, which is 14 (binary 1110) & 13 (binary 1101).

Example:

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

Now we have 12 and we only need to eliminate one last least significant bit. Again, we then execute the bitwise AND on n and n-1, which is 12 (in binary 1100) and 11 (in binary 1011).

Example

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

We are finally left with 8 which is the greatest power of 2 less than 16.

Upvotes: 7

TulaGingerbread

Reputation: 465

You are squaring res each time, meaning you calculate 2^2^2^2 instead of 2^k.
Change your evaluation to following:

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

Update:

Of course, you need to check for overflow of int, in that case checking

while (res <= (n - 1) / 2)

seems much better.

Upvotes: 4

prime

Reputation: 15594

If the number is a power of two then the answer is obvious. (just bit shift) if not well then it is also can be achieved by bit shifting.

find the length of the given number in binary representation. (13 in binary = 1101 ; length is 4)

then shift 2 by (4-2) // 4 is the length of the given number in binary

the below java code will solve this for BigIntegers(so basically for all numbers).

    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));

Upvotes: 0

chinmay

Reputation: 9

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

Upvotes: 0

user555045

Reputation: 64933

There's a nice function in Integer that is helpful, numberOfLeadingZeros.

With it you can do

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

Which does weird things when n is 0 or 1, but for those inputs there is no well-defined "highest power of two less than n".

edit: this answer is even better

Upvotes: 7

Tom Hawtin - tackline

Reputation: 147164

Integer.highestOneBit(n-1);

For n <= 1 the question doesn't really make sense. What to do in that range is left to the interested reader.

The's a good collection of bit twiddling algorithms in Hacker's Delight.

Upvotes: 42

banarun

Reputation: 2321

Find the first set bit from left to right and make all other set bits 0s.

If there is only 1 set bit then shift right by one.

Upvotes: 2

luk2302

Reputation: 57214

Change res =(int)Math.pow(res, 2); to res *= 2; This will return the next power of 2 greater than res.
The final result you are looking for will therefore finally be res / 2 after the while has ended.

To prevent the code from overflowing the int value space you should/could change the type of res to double/long, anything that can hold higher values than int. In the end you would have to cast one time.

Upvotes: 12

scaryrawr

Reputation: 867

Why not use logs?

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

log(n) / log(2) tells you the number of times 2 goes into a number. By taking the floor of it, gets you the integer value rounding down.

Upvotes: 13

Sergey Kalinichenko

Reputation: 727137

You can use this bit hack:

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

Upvotes: 12

How to find the largest power of 2 less than the given number

Answers (20)

Related Questions