##
**
Problem
**

Given an integer
*
N
*
, find the maximum integer smaller than or equal to
*
N
*
, which is a power of 2, with a constant time complexity O(1).

####
**
Sample Input
**

10

####
**
Sample Output
**

8

####
**
Explanation
**

2
^{
3
}
= 8

##
**
Approach
**

This will work for integers with a fixed number of bits (such as 32 bits). We'll set bits one by one, then add 1 to ensure that only the bit after the MSB is set. Finally, perform a right shift by one and return the result.

###
**
Complexity Analysis
**

The time complexity is constant since the number of bits is fixed, and no extra space is required.

####
**
C++ Programming
**

#include <iostream> using namespace std; int solve(int n) {// keep taking bitwise OR of shifted versionn |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16;// increment by 1n = n + 1; return (n >> 1); } int main() { int n = 10; cout << solve(n); return 0; }

####
**
Output
**

8

**
Java Programming
**

class Solution { static int solve(int n) {// Or-ing the right shifted versionn |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16;// increasing by 1n = n + 1; return (n >> 1); } public static void main(String arg[]) { int n = 10; System.out.print(solve(n)); } }

####
**
Output
**

8

**
Python Programming
**

def solve(n): # right shifting n |= n>>1 n |= n>>2 n |= n>>4 n |= n>>8 n |= n>>16 # increment by 1 n = n + 1 return (n >> 1) n = 10 print(solve(n))

####
**
Output
**

8

**
People are also reading:
**

- Subarray with Sum k
- Find Maximum Subarray Sum
- Maximum Sum Circular Subarray
- Dutch National Flag Problem
- Create a mirror of an m–ary Tree
- Find a Pair with the given sum in a BST
- In-place vs out-of-place algorithms
- Hybrid QuickSort Algorithm
- Sort elements by their frequency and index
- Find dropping point of an egg

## Leave a Comment on this Post