# Find MSB

Posted in  Vinay Khatri
Last updated on June 12, 2022

## Problem

Given an integer N . Find a maximum integer smaller than or equal to N that is the power of 2.

`10`

`8`

#### Explanation

`23 = 8`

## Approach

We first find the position (let’s say k ) of the most significant set bit and then compute the value of the number with a set bit at k -th position. This will give us the required number. This works as every number that is a power of 2 is represented as 1, 10, 100.. and so on.

### Complexity Analysis

The time complexity is O(log(N)) with no extra space required.

#### C++ Programming

```#include <bits/stdc++.h>
using namespace std;

int solve(int n)
{
// find the position of the most significant set bit
int k = (int)(log2(n));
// left shift 1 by k
return 1 << k;
}
int main()
{
int n = 10;
cout << solve(n);
return 0;
}```

`8`

#### Java Programming

```class Solution {
static int solve(int n)
{
// find the position of the most significant set bit
int k = (int)(Math.log(n) / Math.log(2));
// left shift 1 by k
return 1 << k;
}
public static void main(String arg[])
{
int n = 10;
System.out.print(solve(n));
}
}```

`8`

#### Python Programming

```import math

def solve(n):
# find the position of the most significant set bit
k = int(math.log(n, 2))

# left shift 1 by k
return 1 << k

n = 10

print(solve(n))```

`8`