# Find MSB in O(1)

Posted in  Vinay Khatri
Last updated on November 29, 2023

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

`10`

`8`

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 version
n |= n >> 1;

n |= n >> 2;
n |= n >> 4;

n |= n >> 8;

n |= n >> 16;

// increment by 1
n = 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 version
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;

// increasing by 1
n = 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))```

`8`