Find most significant set bit of a number
Last Updated : 06 Apr, 2023
Given a number, find the greatest number less than the given a number which is the power of two or find the most significant bit number .
Examples:
Input: 10
Output: 8
Explanation:
Greatest number which is a Power of 2 less than 10 is 8
Binary representation of 10 is 1010
The most significant bit corresponds to decimal number 8.
Input: 18
Output: 16
A simple solution is to one by one divide n by 2 until it becomes 0 and increment a count while doing this. This count actually represents the position of MSB.
C++ // Simple CPP program to find MSB number // for given POSITIVE n. #include <iostream> using namespace std; int setBitNumber(int n) { if (n == 0) return 0; int msb = 0; n = n / 2; while (n != 0) { n = n / 2; msb++; } return (1 << msb); } // Driver code int main() { int n = 0; cout << setBitNumber(n); n = ~(int)0; // test for possible overflow cout << "\n" << (unsigned int)setBitNumber(n); return 0; } #include <stdio.h> int setBitNumber(int n) { if (n == 0) return 0; int msb = 0; n = n / 2; while (n != 0) { n = n / 2; msb++; } return (1 << msb); } int main() { int n = 0; printf("%d \n",setBitNumber(n)); n = ~(int)0; // test for possible overflow int ns = (unsigned int)setBitNumber(n); printf("%d",ns); return 0; } // Simple Java program to find // MSB number for given n. import java.io.*; class GFG { static int setBitNumber(int n) { if (n == 0) return 0; int msb = 0; n = n / 2; while (n != 0) { n = n / 2; msb++; } return (1 << msb); } // Driver code public static void main(String[] args) { int n = 0; System.out.println(setBitNumber(n)); } } // This code is contributed by ajit # Simple Python3 program # to find MSB number # for given n. def setBitNumber(n): if (n == 0): return 0; msb = 0; n = int(n / 2); while (n > 0): n = int(n / 2); msb += 1; return (1 << msb); # Driver code n = 0; print(setBitNumber(n)); # This code is contributed # by mits
// Simple C# program to find // MSB number for given n. using System; class GFG { static int setBitNumber(int n) { if (n == 0) return 0; int msb = 0; n = n / 2; while (n != 0) { n = n / 2; msb++; } return (1 << msb); } // Driver code static public void Main() { int n = 0; Console.WriteLine(setBitNumber(n)); } } // This code is contributed // by akt_mit <?php // Simple PhP program // to find MSB number // for given n. function setBitNumber($n) { if ($n == 0) return 0; $msb = 0; $n = $n / 2; while ($n != 0) { $n = $n / 2; $msb++; } return (1 << $msb); } // Driver code $n = 0; echo setBitNumber($n); // This code is contributed // by akt_mit ?> <script> // Javascript program // to find MSB number // for given n. function setBitNumber(n) { if (n == 0) return 0; let msb = 0; n = n / 2; while (n != 0) { n = $n / 2; msb++; } return (1 << msb); } // Driver code let n = 0; document.write (setBitNumber(n)); // This code is contributed by Bobby </script> Time Complexity: O(logn)
Auxiliary Space: O(1)
An efficient solution for a fixed size integer (say 32 bits) is to one by one set bits, then add 1 so that only the bit after MSB is set. Finally right shift by 1 and return the answer. This solution does not require any condition checking.
C++ // CPP program to find MSB number for ANY given n. #include <iostream> #include <limits.h> using namespace std; int setBitNumber(int n) { // Below steps set bits after // MSB (including MSB) // Suppose n is 273 (binary // is 100010001). It does following // 100010001 | 010001000 = 110011001 n |= n >> 1; // This makes sure 4 bits // (From MSB and including MSB) // are set. It does following // 110011001 | 001100110 = 111111111 n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // The naive approach would increment n by 1, // so only the MSB+1 bit will be set, // So now n theoretically becomes 1000000000. // All the would remain is a single bit right shift: // n = n + 1; // return (n >> 1); // // ... however, this could overflow the type. // To avoid overflow, we must retain the value // of the bit that could overflow: // n & (1 << ((sizeof(n) * CHAR_BIT)-1)) // and OR its value with the naive approach: // ((n + 1) >> 1) n = ((n + 1) >> 1) | (n & (1 << ((sizeof(n) * CHAR_BIT)-1))); return n; } // Driver code int main() { int n = 273; cout << setBitNumber(n); n = ~(int)0; // test for possible overflow cout << "\n" << (unsigned int)setBitNumber(n); return 0; } #include <stdio.h> #include <limits.h> int setBitNumber(int n) { // Below steps set bits after // MSB (including MSB) // Suppose n is 273 (binary // is 100010001). It does following // 100010001 | 010001000 = 110011001 n |= n >> 1; // This makes sure 4 bits // (From MSB and including MSB) // are set. It does following // 110011001 | 001100110 = 111111111 n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // The naive approach would increment n by 1, // so only the MSB+1 bit will be set, // So now n theoretically becomes 1000000000. // All the would remain is a single bit right shift: // n = n + 1; // return (n >> 1); // // ... however, this could overflow the type. // To avoid overflow, we must retain the value // of the bit that could overflow: // n & (1 << ((sizeof(n) * CHAR_BIT)-1)) // and OR its value with the naive approach: // ((n + 1) >> 1) n = ((n + 1) >> 1) | (n & (1 << ((sizeof(n) * CHAR_BIT)-1))); return n; } int main() { int n = 273; printf("%d\n",setBitNumber(n)); return 0; } // Java program to find MSB // number for given n. class GFG { static int setBitNumber(int n) { // Below steps set bits after // MSB (including MSB) // Suppose n is 273 (binary // is 100010001). It does following // 100010001 | 010001000 = 110011001 n |= n >> 1; // This makes sure 4 bits // (From MSB and including MSB) // are set. It does following // 110011001 | 001100110 = 111111111 n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // Increment n by 1 so that // there is only one set bit // which is just before original // MSB. n now becomes 1000000000 n = n + 1; // Return original MSB after shifting. // n now becomes 100000000 return (n >> 1); } // Driver code public static void main(String arg[]) { int n = 273; System.out.print(setBitNumber(n)); } } // This code is contributed by Anant Agarwal. # Python program to find # MSB number for given n. def setBitNumber(n): # Below steps set bits after # MSB (including MSB) # Suppose n is 273 (binary # is 100010001). It does following # 100010001 | 010001000 = 110011001 n |= n>>1 # This makes sure 4 bits # (From MSB and including MSB) # are set. It does following # 110011001 | 001100110 = 111111111 n |= n>>2 n |= n>>4 n |= n>>8 n |= n>>16 # Increment n by 1 so that # there is only one set bit # which is just before original # MSB. n now becomes 1000000000 n = n + 1 # Return original MSB after shifting. # n now becomes 100000000 return (n >> 1) # Driver code n = 273 print(setBitNumber(n)) # This code is contributed # by Anant Agarwal.
// C# program to find MSB number for given n. using System; class GFG { static int setBitNumber(int n) { // Below steps set bits after // MSB (including MSB) // Suppose n is 273 (binary // is 100010001). It does following // 100010001 | 010001000 = 110011001 n |= n >> 1; // This makes sure 4 bits // (From MSB and including MSB) // are set. It does following // 110011001 | 001100110 = 111111111 n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // Increment n by 1 so that // there is only one set bit // which is just before original // MSB. n now becomes 1000000000 n = n + 1; // Return original MSB after shifting. // n now becomes 100000000 return (n >> 1); } // Driver code public static void Main() { int n = 273; Console.WriteLine(setBitNumber(n)); } } // This code is contributed by Sam007. <?php // PHP program to find // MSB number for given n. function setBitNumber($n) { // Below steps set bits // after MSB (including MSB) // Suppose n is 273 (binary // is 100010001). It does // following 100010001 | // 010001000 = 110011001 $n |= $n >> 1; // This makes sure 4 bits // (From MSB and including // MSB) are set. It does // following 110011001 | // 001100110 = 111111111 $n |= $n >> 2; $n |= $n >> 4; $n |= $n >> 8; $n |= $n >> 16; // Increment n by 1 so // that there is only // one set bit which is // just before original // MSB. n now becomes // 1000000000 $n = $n + 1; // Return original MSB // after shifting. n // now becomes 100000000 return ($n >> 1); } // Driver code $n = 273; echo setBitNumber($n); // This code is contributed // by akt_mit ?> <script> // Javascript program to find MSB // number for given n. function setBitNumber(n) { // Below steps set bits after // MSB (including MSB) // Suppose n is 273 (binary // is 100010001). It does following // 100010001 | 010001000 = 110011001 n |= n >> 1; // This makes sure 4 bits // (From MSB and including MSB) // are set. It does following // 110011001 | 001100110 = 111111111 n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // Increment n by 1 so that // there is only one set bit // which is just before original // MSB. n now becomes 1000000000 n = n + 1; // Return original MSB after shifting. // n now becomes 100000000 return (n >> 1); } // Driver code let n = 273; document.write(setBitNumber(n)); // This code is contributed by suresh07 </script> Time Complexity: O(1)
Auxiliary Space: O(1)
Using __builtin_clz(x) (GCC builtin function)
Say for a fixed integer (32 bits), count the number of leading zeroes by using the built-in function and subtract it from 31 to get the position of MSB from left, then return the MSB using left shift operation on 1.
An efficient solution for a fixed size integer (say 32 bits) is to one by one set bits, then add 1 so that only the bit after MSB is set. Finally right shift by 1 and return the answer. This solution does not require any condition checking.
C++ // CPP program to find MSB // number for a given POSITIVE n. #include <bits/stdc++.h> using namespace std; int setBitNumber(int n) { // calculate the number // of leading zeroes int k = __builtin_clz(n); // To return the value // of the number with set // bit at (31 - k)-th position // assuming 32 bits are used return 1 << (31 - k); } // Driver code int main() { int n = 273; cout << setBitNumber(n); n = ~(int)0; // test for possible overflow cout << "\n" << (unsigned int)setBitNumber(n); return 0; } import java.lang.*; public class Main { public static int setBitNumber(int n) { // calculate the number // of leading zeroes int k = Integer.numberOfLeadingZeros(n); // To return the value // of the number with set // bit at (31 - k)-th position // assuming 32 bits are used return 1 << (31 - k); } // Driver code public static void main(String[] args) { int n = 273; System.out.println(setBitNumber(n)); n = ~(int)0; // test for possible overflow System.out.println((int)setBitNumber(n)); } } // This code is Contributed by 'Shiv1o43g' using System; public class MainClass { public static int SetBitNumber(int n) { // calculate the number // of leading zeroes int k = 32 - Convert.ToString(n, 2).Length; // To return the value // of the number with set // bit at (31 - k)-th position // assuming 32 bits are used return 1 << (31 - k); } // Driver code public static void Main() { int n = 273; Console.WriteLine(SetBitNumber(n)); n = ~(int)0; // test for possible overflow Console.WriteLine((uint)SetBitNumber(n)); } } // This code is contributed by user_dtewbxkn77n function setBitNumber(n) { // calculate the number of leading zeroes let k = 31 - Math.floor(Math.log2(n)); // To return the value of the number with set // bit at (31 - k)-th position return 1 << k; } // Driver code let n = 273; console.log(setBitNumber(n)); // expected output: 256 n = ~(0); // test for possible overflow console.log(setBitNumber(n)); // expected output: 2147483648 Time Complexity: O(1)
Auxiliary Space: O(1)
Another Approach: Given a number n. First, find the position of the most significant set bit and then compute the value of the number with a set bit at k-th position.
Thanks Rohit Narayan for suggesting this method.
C++ // CPP program to find MSB // number for given POSITIVE n. #include <bits/stdc++.h> using namespace std; int setBitNumber(int n) { //this will be the answer going to return //This will work for 64-bit if using with long long //while in-built functions overflow int ans = 1; while (n) { ans *= 2; n /= 2; } ans/=2; return ans; } // Driver code int main() { int n = 273; cout << setBitNumber(n); return 0; } #include <stdio.h> #include <math.h> int setBitNumber(int n) { if (n == 0) return 0; int msb = 0; n = n / 2; while (n != 0) { n = n / 2; msb++; } return (1 << msb); } int main() { int n = 273; printf("%d",setBitNumber(n)); return 0; } // Java program to find MSB // number for given n. class GFG { static int setBitNumber(int n) { // To find the position of the // most significant set bit int k = (int)(Math.log(n) / Math.log(2)); // To return the value of the number // with set bit at k-th position return 1 << k; } // Driver code public static void main(String arg[]) { int n = 273; System.out.print(setBitNumber(n)); } } # Python program to find # MSB number for given n. import math def setBitNumber(n): # To find the position of # the most significant # set bit k = int(math.log(n, 2)) # To return the value # of the number with set # bit at k-th position return 1 << k # Driver code n = 273 print(setBitNumber(n))
// C# program to find MSB // number for given n. using System; public class GFG { static int setBitNumber(int n) { // To find the position of the // most significant set bit int k = (int)(Math.Log(n) / Math.Log(2)); // To return the value of the number // with set bit at k-th position return 1 << k; } // Driver code static public void Main() { int n = 273; Console.WriteLine(setBitNumber(n)); } } <?php // PHP program to find MSB // number for given n. function setBitNumber($n) { // To find the position // of the most significant // set bit $k =(int)(log($n, 2)); // To return the value // of the number with set // bit at k-th position return 1 << $k; } // Driver code $n = 273; echo setBitNumber($n); // This code is contributed // by jit_t. ?> <script> // Javascript program to find // MSB number for given n. function setBitNumber(n) { // To find the position of the // most significant set bit let k = parseInt(Math.log(n) / Math.log(2), 10); // To return the value of the number // with set bit at k-th position return 1 << k; } let n = 273; document.write(setBitNumber(n)); </script> Time Complexity: O(logn)
Auxiliary Space: O(1)
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem
My Profile