Find MSB in O(1)

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 ³ = 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:

• Subarray with Sum k
• Find Maximum Subarray Sum
• Maximum Sum Circular Subarray
• Dutch National Flag Problem
• Create a mirror of an m–ary Tree
• Find a Pair with the given sum in a BST
• In-place vs out-of-place algorithms
• Hybrid QuickSort Algorithm
• Sort elements by their frequency and index
• Find dropping point of an egg