## 1. Overview

In this article, we'll be seeing how to find the largest power of 2 that is less than the given number.

For our examples, we'll take the sample input 9. 2^{0} is 1, the least valid input for which we can find the power of 2 less than the given input is 2. Hence we'll only consider inputs greater than 1 as valid.

## 2. Naive Approach

Let's start with 2^{0}, which is 1, and we'll **keep multiplying the number by 2 until we find a number that is less than the input**:

```
public long findLargestPowerOf2LessThanTheGivenNumber(long input) {
Assert.isTrue(input > 1, "Invalid input");
long firstPowerOf2 = 1;
long nextPowerOf2 = 2;
while (nextPowerOf2 < input) {
firstPowerOf2 = nextPowerOf2;
nextPowerOf2 = nextPowerOf2 * 2;
}
return firstPowerOf2;
}
```

Let's understand the code for sample *input* = 9.

The initial value for *firstPowerOf2* is 1 and *nextPowerOf2* is 2. As we can see, 2 < 9 is true, and we get inside the while loop.

For the first iteration, *firstPowerOf2* is 2 and *nextPowerOf2* is 2 * 2 = 4. Again 4 < 9 so lets continue the while loop.

For the second iteration, *firstPowerOf2* is 4 and *nextPowerOf2* is 4 * 2 = 8. Now 8 < 9, let's keep going.

For the third iteration, *firstPowerOf2* is 8 and *nextPowerOf2* is 8 * 2 = 16. The while condition 16 < 9 is false, so it breaks out of the while loop. 8 is the largest power of 2 which is less than 9.

Let's run some tests to validate our code:

```
assertEquals(8, findPowerOf2LessThanTheGivenNumber(9));
assertEquals(16, findPowerOf2LessThanTheGivenNumber(32));
```

**The time complexity of our solution is O(log**_{2}(N)). In our case, we iterated log_{2}(9) = 3 times.

## 3. Using *Math.log*

Log base 2 will give how many times we can divide a number by 2 recursively in other words, **log**_{2} of a number gives the power of 2. Let's look at some examples to understand this.

log_{2}(8) = 3 and log_{2}(16) = 4. In general, we can see that y = log_{2}x where x = 2^{y}.

Hence, if we find a number that is divisible by 2, we subtract 1 from it so that we avoid a scenario where the number is a perfect power of 2.

*Math.log* is log_{10}. To compute log_{2}(x), we can use the formula log_{2}(x)=log_{10}(x)/log_{10}(2)

Let's put that in code:

```
public long findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(long input) {
Assert.isTrue(input > 1, "Invalid input");
long temp = input;
if (input % 2 == 0) {
temp = input - 1;
}
long power = (long) (Math.log(temp) / Math.log(2));
long result = (long) Math.pow(2, power);
return result;
}
```

Assuming our sample input as 9, the initial value of *temp* is 9.

9 % 2 is 1, so our *temp* variable is 9.** **Here we are using modulo division, which will give the remainder of 9/2.

To find the log_{2}(9), we do log_{10}(9) / log_{10}(2) = 0.95424 / 0.30103 ~= 3.

Now, the *result* is 2^{3} which is 8.

Let's verify our code:

```
assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(32));
```

In reality, *Math.pow* will be doing the same iteration that we did in approach 1. Hence we can say that for this solution too, **the time complexity is O(Log**_{2}(N)).

## 4. Bitwise Technique

For this approach, we'll use the bitwise shift technique. First, let's look at the binary representations for the power of 2 considering we have 4 bits to represent the number

2^{0} |
1 |
*0001* |

2^{1} |
2 |
*0010* |

2^{2} |
4 |
*0100* |

2^{3} |
8 |
*1000* |

Looking closely, we can observe that we can **compute the power of 2 by left shifting the bytes for 1**. ie. 2^{2} is left shift bytes for 1 by 2 places and so on.

Let's code using the bitshift technique:

```
public long findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(long input) {
Assert.isTrue(input > 1, "Invalid input");
long result = 1;
long powerOf2;
for (long i = 0; i < Long.BYTES * 8; i++) {
powerOf2 = 1 << i;
if (powerOf2 >= input) {
break;
}
result = powerOf2;
}
return result;
}
```

In the above code, we are using *long *as our data type, which uses 8 bytes or 64 bits. So we'll be computing the power of 2 up to 2^{64}. We are using the bit shift operator *<< *to find the power of 2. For our sample input 9, after the 4^{th} iteration, the value of *powerOf2* = 16 and *result* = 8 where we break out of the loop as 16 > 9 the *input*.

Let's check if our code is working as expected:

```
assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(32));
```

The **worst-case time complexity for this approach is again O(log**_{2}(N)), similar to what we saw for the first approach. However, this approach is better as a **bit shift operation is more efficient compared to multiplication**.

## 5. Bitwise *AND*

For our next approach, we'll be using this formula **2**^{n} AND 2^{n} -1 = 0.

Let's look at some examples to understand how it works.

The binary representation of 4 is *0100,* and 3 is *0011*.

Let's do a bitwise AND operation on these two numbers. *0100* AND *0011* is *0000*. We can say the same for any power of 2 and a number less than it. Let's take 16 (2^{4}) and 15 which is represented as *1000*, *0111* respectively. Again, we see that the bitwise AND on these two results in 0. We can also say that the AND operation on any other number apart from these 2 won't result in a 0.

Let's see the code for solving this problem using bitwise AND:

```
public long findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(long input) {
Assert.isTrue(input > 1, "Invalid input");
long result = 1;
for (long i = input - 1; i > 1; i--) {
if ((i & (i - 1)) == 0) {
result = i;
break;
}
}
return result;
}
```

In the above code, we loop over numbers less than our input. Whenever we find the bitwise AND of a number and number-1 is zero, we break out of the loop, as we know that number will be a power of 2. In this case for our sample *input* 9, we break out of the loop when *i* = 8 and *i* – 1 = 7.

Now, let's verify a couple of scenarios:

```
assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(32));
```

The worst-case **time complexity for this approach is O(N/2)** when the input is an exact power 2. As we can see, this is not the most efficient solution, but it is good to know this technique as it could come handy when tackling similar problems.

## 6. Conclusion

We have seen different approaches for finding the largest power of 2 that is less than the given number. We also noticed how bitwise operations can simplify computations in some cases.

The complete source code with unit tests for this article can be found over on GitHub.

res – REST with Spring (eBook) (everywhere)