Home » C++ programs » C++ Bit manipulation programs

Here, we are going to learn **how to find the next and previous power of two of a given number using C++ program**?

Submitted by Hritik Raj, on June 24, 2018

**Problem statement:**

Find Next and previous power of two of a given number

**Next power of two**

Example(1): input: 22 output: 32 ( as 32 is 2^5) Example(2): input: 54 output: 64 (as 64 is 2^6)

**Previous power of two**

Example(1): input: 22 output: 16 Example(2): input: 54 output: 32

We can solve this problem using bit manipulation easily.

Just have a look on the binary representation of the number which is a power of 2.

power of 2 Binary Representation 1 1 2 10 4 100 8 1000 16 10000 32 100000 64 1000000 128 10000000

As we can see every number have only their left most bit set (i.e 1) and rest are unset (i.e 0).

If we somehow, can unset all bits except the left most bit in a binary representation of number we will get previous power of two of the given number.

**Example:**

Number Binary representation previous power of two 7 111 100 (i,e 4) 25 11001 10000 (i.e 16) 95 1011111 1000000 (i,e 64)

We will use Bitwise AND ( & ) operation to clear bits.

Here is Algorithm to get previous power of 2 of n,

step 1: n = n & n-1 step 2: if n is power of two , n is our desired result,go to step 3. else go to step 1. step 3: print n and stop

**Explanation:**

let n = 27 ( 11011 in binary) n-1 = 26 ( 11010 in binary) n&n-1 = 26 as 26 is not a power of 2 so we will repeat above step again new n = 26 n = 26 ( 11010 in binary) n-1 = 25 ( 11001 in binary) n&n-1 = 24 ( 11000 in binary) as 24 is not a power of 2 so we will repeat above step again new n=24 n = 24 ( 11000 in binary) n-1 = 23 ( 10111 in binary) n&n-1 = 16 ( 10000 in binary) as 16 is a power of 2 so this is our answer

To get next power of two, all we have to do is to find a binary number greater than the given number having only left most bit set.

We can use left shift operator ( << )to generate a number having only its left most bit set.

Left shift operation example:

1 << 5 This means that shift 1 left by 5 place 1 in binary is represented as 1 so after shifting 1 by 5 place left, output will be 100000 ( i.e 32 in decimal) 5 << 2 This means that shift 5 left by 2 place 5 in binary is represented as 101 so after shifting it by 2 place to left, output will be 10100 ( i.e 20 in decimal)

**Note:** In each shift right most bit will be set to 0;

**Program:**

#include<bits/stdc++.h> using namespace std; long int nextPowerOfTwo ( int n ) { // Result is intialized as 1 long int value = 1; // The following while loop will run until we // get a number greater than n while(value<=n) { // value will be left shifted by 1 place in each iteration value=value << 1; } return value ; } int previousPowerOfTwo(int n ) { // If n is already a power of two, we can simply shift it right // by 1 place and get the previous power of 2 // (n&n-1) will be 0 if n is power of two ( for n > = 2 ) // (n&&!(n&(n-1))) condition will take care of n < 2; if((n&&!(n&(n-1)))==1) { return (n>>1); } // This while loop will run until we get a number which is a power of 2 while(n&n-1) { // Each time we are performing Bit wise And ( & )operation to clear bits n=n&n-1; } return n ; } int main() { int n; cout << "Enter Number\n"; cin >> n; long int num=nextPowerOfTwo(n); cout << "Next power of two : " << num ; cout << "\n\nEnter Number\n"; cin >> n; num=previousPowerOfTwo(n); cout << "Previous power of two : " << num ; return 0; }

**Output**

Enter Number 34 Next power of two : 64 Enter Number 34 Previous power of two : 32 Process returned 0 (0x0) execution time : 7.681 s Press any key to continue.

**Quick links:**

C FAQ(s)
C Advance programs
C/C++ Tips & Tricks
Puzzles
JavaScript
CSS
Python
Linux Commands
PHP
Android
Articles
More...

Was this page helpful? Please share with your friends...

Are you a blogger? Join our Blogging forum.

Comments and Discussions

.rgtpcss { float: right; }
@media(min-width: 300px) { .rgtpcss { float: left; }
@media(min-width: 480px) { .rgtpcss { float: left; }
@media(min-width: 750px) { .rgtpcss { float: right; }
.resCodeAS1 { display: block; width: 320px; height: 50px; }
@media(min-width: 300px) { .resCodeAS1 { display: block; width: 300px; height: 250px; } }
@media(min-width: 480px) { .resCodeAS1 { display: block; width: 300px; height: 250px; } }
@media(min-width: 750px) { .resCodeAS1 { display: block; width: 300px; height: 250px; } }
(adsbygoogle = window.adsbygoogle || []).push({});

(adsbygoogle = window.adsbygoogle || []).push({});

(adsbygoogle = window.adsbygoogle || []).push({});

solved programs: » C » C++ » DS » Java » C# |

aptitude que. & ans.: » C » C++ » Java » DBMS |

interview que. & ans.: » C » Embedded C » Java » SEO » HR |