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. 20 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 20, 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(log2(N)). In our case, we iterated log2(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, log2 of a number gives the power of 2. Let’s look at some examples to understand this.
log2(8) = 3 and log2(16) = 4. In general, we can see that y = log2x where x = 2y.
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 log10. To compute log2(x), we can use the formula log2(x)=log10(x)/log10(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 log2(9), we do log10(9) / log10(2) = 0.95424 / 0.30103 ~= 3.
Now, the result is 23 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(Log2(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
20
1
0001
21
2
0010
22
4
0100
23
8
1000
Looking closely, we can observe that we can compute the power of 2 by left shifting the bytes for 1. ie. 22 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 264. We are using the bit shift operator *<<* to find the power of 2. For our sample input 9, after the 4th 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(log2(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 2n AND 2n -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 (24) 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.