Find MSB

Posted in

Find MSB

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.

    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:

    Leave a Comment on this Post

    0 Comments