Q:

Find next and previous power of two of a given number in C++

mahmoud2506
Save to bookmark
|
2022-05-05
|
  298 
0

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

Finding previous power of 2

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
C++ programming, exam questions, C++ programming exam-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-05
need an explanation for this answer? contact us directly to get an explanation for this answer

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.

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now