Find MSB

Problem

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

Sample Input

10

Sample Output

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;
}

Output

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));
    }
}

Output

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

Output

8

People are also reading:

• Find MSB in O(1)
• Longest Substring without repeating characters
• Count subarrays with given XOR
• Python Take list as an input from a user
• Delete Nodes And Return Forest
• Longest Consecutive Sequence in Linear time
• Modular Exponentiation in Logarithmic Time
• Rearrange an array such that arr[i] = i
• Minimum Edit Distance
• The Stock Span Problem