Find MSB in O(1)

Posted in

Find MSB in O(1)
vinaykhatri

Vinay Khatri
Last updated on March 19, 2024

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

    Output

    8

    People are also reading:

    Leave a Comment on this Post

    0 Comments