{"id":63373,"date":"2020-08-28T06:10:03","date_gmt":"2020-08-28T06:10:03","guid":{"rendered":"https:\/\/www.baeldung.com\/?p=86285"},"modified":"2020-08-28T06:10:03","modified_gmt":"2020-08-28T06:10:03","slug":"largest-power-of-2-that-is-less-than-the-given-number","status":"publish","type":"post","link":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/2020\/08\/28\/largest-power-of-2-that-is-less-than-the-given-number\/","title":{"rendered":"Largest Power of 2 That Is Less Than the Given Number"},"content":{"rendered":"

<\/p>\n

1. Overview<\/h2>\n
<\/div>\n

In this article, we’ll be seeing how to find the largest power of 2 that is less than the given number.<\/p>\n

For our examples, we’ll take the sample input 9. 20<\/sup> 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.<\/p>\n

2. Naive Approach<\/h2>\n
<\/div>\n

Let’s start with 20<\/sup>, which is 1, and we’ll keep multiplying the number by 2 until we find a number that is less than the input<\/strong>:<\/p>\n

public long findLargestPowerOf2LessThanTheGivenNumber(long input) {\r\n    Assert.isTrue(input > 1, \"Invalid input\");\r\n    long firstPowerOf2 = 1;\r\n    long nextPowerOf2 = 2;\r\n    while (nextPowerOf2 < input) {\r\n        firstPowerOf2 = nextPowerOf2;\r\n        nextPowerOf2 = nextPowerOf2 * 2;\r\n    }\r\n    return firstPowerOf2;\r\n}<\/code><\/pre>\n
Let’s understand the code for sample input<\/em> = 9.<\/p>\n
The initial value for firstPowerOf2<\/em> is 1 and nextPowerOf2<\/em> is 2. As we can see, 2 < 9 is true, and we get inside the while loop.<\/p>\n
For the first iteration, firstPowerOf2<\/em> is 2 and nextPowerOf2<\/em> is 2 * 2 = 4. Again 4 < 9 so lets continue the while loop.<\/p>\n
For the second iteration, firstPowerOf2<\/em> is 4 and nextPowerOf2<\/em> is 4 * 2 = 8. Now 8 < 9, let’s keep going.<\/p>\n
For the third iteration, firstPowerOf2<\/em> is 8 and nextPowerOf2<\/em> 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.<\/p>\n
Let’s run some tests to validate our code:<\/p>\n
assertEquals(8, findPowerOf2LessThanTheGivenNumber(9));\r\nassertEquals(16, findPowerOf2LessThanTheGivenNumber(32));\r\n<\/code><\/pre>\n
The time complexity of our solution is O(log2<\/sub>(N))<\/strong>. In our case, we iterated log2<\/sub>(9) = 3 times.<\/p>\n
3. Using Math.log<\/em><\/h2>\n
<\/div>\n
Log base 2 will give how many times we can divide a number by 2 recursively in other words, log2<\/sub> of a number gives the power of 2<\/strong>. Let’s look at some examples to understand this.<\/p>\n
log2<\/sub>(8) = 3 and log2<\/sub>(16) = 4. In general, we can see that y = log2<\/sub>x where x = 2y<\/sup>.<\/p>\n
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.<\/p>\n
Math.log<\/em><\/a> is log10<\/sub>. To compute log2<\/sub>(x), we can use the formula log2<\/sub>(x)=log10<\/sub>(x)\/log10<\/sub>(2)<\/p>\n
Let’s put that in code:<\/p>\n
public long findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(long input) {\r\n    Assert.isTrue(input > 1, \"Invalid input\");\r\n    long temp = input;\r\n    if (input % 2 == 0) {\r\n        temp = input - 1;\r\n    }\r\n    long power = (long) (Math.log(temp) \/ Math.log(2));\r\n    long result = (long) Math.pow(2, power);\r\n    return result;\r\n}<\/code><\/pre>\n
Assuming our sample input as 9, the initial value of temp<\/em> is 9.<\/p>\n
9 % 2 is 1, so our temp<\/em> variable is 9.\u00a0<\/strong>Here we are using modulo division, which will give the remainder of 9\/2.<\/p>\n
To find the log2<\/sub>(9), we do log10<\/sub>(9) \/ log10<\/sub>(2) = 0.95424 \/ 0.30103 ~= 3.<\/p>\n
Now, the result<\/em> is 23<\/sup> which is 8.<\/p>\n
Let’s verify our code:<\/p>\n
assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(9));\r\nassertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(32));<\/code><\/pre>\n
In reality, Math.pow<\/em> 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<\/sub>(N))<\/strong>.<\/p>\n
4. Bitwise Technique<\/h2>\n
<\/div>\n
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<\/p>\n\n\n\n\n\n\n
20<\/sup><\/td>\n1<\/td>\n0001<\/em><\/td>\n<\/tr>\n
21<\/sup><\/td>\n2<\/td>\n0010<\/em><\/td>\n<\/tr>\n
22<\/sup><\/td>\n4<\/td>\n0100<\/em><\/td>\n<\/tr>\n
23<\/sup><\/td>\n8<\/td>\n1000<\/em><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Looking closely, we can observe that we can compute the power of 2 by left shifting the bytes for 1<\/strong>. ie. 22<\/sup> is left shift bytes for 1 by 2 places and so on.<\/p>\n
Let’s code using bitshift technique:<\/p>\n
public long findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(long input) {\r\n    Assert.isTrue(input > 1, \"Invalid input\");\r\n    long result = 1;\r\n    long powerOf2;\r\n    for (long i = 0; i < Long.BYTES * 8; i++) {\r\n        powerOf2 = 1 << i;\r\n        if (powerOf2 >= input) {\r\n            break;\r\n        }\r\n        result = powerOf2;\r\n    }\r\n    return result;\r\n}<\/code><\/pre>\n
In the above code, we are using long <\/em>as our data type, which uses 8 bytes or 64 bits. So we’ll be computing the power of 2 up to 264<\/sup>. We are using the bit shift operator << <\/em>to find the power of 2. For our sample input 9, after the 4th<\/sup> iteration, the value of powerOf2<\/em> = 16 and result<\/em> = 8 where we break out of the loop as 16 > 9 the input<\/em>.<\/p>\n
Let’s check if our code is working as expected:<\/p>\n
assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(9));\r\nassertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(32));<\/code><\/pre>\n
The worst-case time complexity for this approach is again O(log2<\/sub>(N))<\/strong>, 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<\/strong>.<\/p>\n
5. Bitwise AND<\/h2>\n
<\/div>\n
For our next approach, we’ll be using this formula 2n<\/sup> AND 2n<\/sup> -1 = 0<\/strong>.<\/p>\n
Let’s look at some examples to understand how it works.<\/p>\n
The binary representation of 4 is 0100,<\/em> and 3 is 0011<\/em>.<\/p>\n
Let’s do a bitwise AND operation<\/a> on these two numbers. 0100<\/em> AND 0011<\/em> is 0000<\/em>. We can say the same for any power of 2 and a number less than it. Let’s take 16 (24<\/sup>) and 15 which is represented as 1000<\/em>, 0111<\/em> 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.<\/p>\n
Let’s see the code for solving this problem using bitwise AND:<\/p>\n
public long findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(long input) { \r\n    Assert.isTrue(input > 1, \"Invalid input\");\r\n    long result = 1;\r\n    for (long i = input - 1; i > 1; i--) {\r\n        if ((i & (i - 1)) == 0) {\r\n            result = i;\r\n            break;\r\n        }\r\n    }\r\n    return result;\r\n}<\/code><\/pre>\n
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<\/em> 9, we break out of the loop when i<\/em> = 8 and i<\/em> – 1 = 7.<\/p>\n
Now, let’s verify a couple of scenarios:<\/p>\n
assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(9));\r\nassertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(32));<\/code><\/pre>\n
The worst-case time complexity for this approach is O(N\/2)<\/strong> 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.<\/p>\n
6. Conclusion<\/h2>\n
<\/div>\n
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.<\/p>\n
The complete source code with unit tests for this article can be found over on GitHub<\/a>.<\/p>\n
\"\"<\/p>\n
<\/a> <\/a> <\/a> <\/a> <\/a> <\/a> <\/a> <\/a> <\/div>\n\n
\\\"IT\u96fb\u8166\u88dc\u7fd2
\u7acb\u523b\u8a3b\u518a\u53ca\u5831\u540d\u96fb\u8166\u88dc\u7fd2\u8ab2\u7a0b\u5427!<\/figcaption><\/figure>\r\n<\/br>Find A Teacher Form:\r\n<\/br>https:\/\/docs.google.com\/forms\/d\/1vREBnX5n262umf4wU5U2pyTwvk9O-JrAgblA-wH9GFQ\/viewform?edit_requested=true#responses\r\n<\/br><\/br>Email:\r\n<\/br>public1989two@gmail.com






\r\nwww.itsec.hk<\/a>
\r\nwww.itsec.vip<\/a>
\r\nwww.itseceu.uk<\/a>
<\/p>","protected":false},"excerpt":{"rendered":"
Learn how to find the largest power of 2 that is less than an input number.<\/p>\n
<\/a> <\/a> <\/a> <\/a> <\/a> <\/a> <\/a> <\/a> <\/div>\n<\/div>","protected":false},"author":214,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"slim_seo":{"title":"Largest Power of 2 That Is Less Than the Given Number - ITTeacherITFreelance.hk","description":"Learn how to find the largest power of 2 that is less than an input number.                "},"footnotes":""},"categories":[6],"tags":[4911,4912],"_links":{"self":[{"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/posts\/63373"}],"collection":[{"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/users\/214"}],"replies":[{"embeddable":true,"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/comments?post=63373"}],"version-history":[{"count":9,"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/posts\/63373\/revisions"}],"predecessor-version":[{"id":66530,"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/posts\/63373\/revisions\/66530"}],"wp:attachment":[{"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/media?parent=63373"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/categories?post=63373"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/tags?post=63373"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}