Most Significant Bit Editorial

Practice Problem Link: Most Significant Bit

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

The most significant bit of a number n is the left most set bit in its binary representation. The significance of that bit is determined by its position. Given a number n, find the significance of the most significant bit, i.e., find the greatest number less than or equal to n which is the power of two.

Naive Approach

The naive approach is to keep dividing the number by 2, and keeping the track of the index of the last significant bit encountered. We keep doing this till the number is reduced to zero.

Analysis

• Time Complexity: O(log₂n)
• Space Complexity: O(1)

Implementation

C++

int msbSignificance(int n) {
    int index = 0, count = 0;
	while(n != 0) {
		count++;
		if(n % 2 == 1) {
			index = count;
		}
		n /= 2;
	}
	return (1 << (index - 1));
}

Java

class Solution {
    int msbSignificance(int n) {
		int index = 0, count = 0;
		while(n != 0) {
			count++;
			if(n % 2 == 1) {
				index = count;
			}
			n /= 2;
		}
		return (1 << (index - 1));
    }
}

Optimal Approach

The optimal approach is to use the formula that MSB = floor(log2n). 

Analysis

• Time Complexity: O(1)
• Space Complexity: O(1)

Implementation

C++

int msbSignificance(int n) {
    int index = floor(log2(n));
	return (1 << index);
}

Java

class Solution {
    int msbSignificance(int n) {
		int index = (int)(Math.log(n) / Math.log(2));
		return (1 << index);
    }
}