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 codeint main(){ int n = 0; cout << setBitNumber(n); n = ~(int)0; // test for possible overflow cout << "\n" << (unsigned int)setBitNumber(n); return 0;} |
C
#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;} |
Java
// 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 |
Python3
# 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 coden = 0;print(setBitNumber(n)); # This code is contributed # by mits |
C#
// 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
<?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?> |
Javascript
<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 codelet n = 0;document.write (setBitNumber(n)); // This code is contributed by Bobby</script> |
Output
0 1
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 codeint main(){ int n = 273; cout << setBitNumber(n); n = ~(int)0; // test for possible overflow cout << "\n" << (unsigned int)setBitNumber(n); return 0;} |
C
#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
// 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. |
Python3
# 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 coden = 273 print(setBitNumber(n))# This code is contributed# by Anant Agarwal. |
C#
// 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// 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?> |
Javascript
<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 codelet n = 273;document.write(setBitNumber(n));// This code is contributed by suresh07</script> |
Output
256 2147483648
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 codeint main(){ int n = 273; cout << setBitNumber(n); n = ~(int)0; // test for possible overflow cout << "\n" << (unsigned int)setBitNumber(n); return 0;} |
Java
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' |
C#
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 |
Javascript
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 codelet n = 273;console.log(setBitNumber(n)); // expected output: 256n = ~(0); // test for possible overflowconsole.log(setBitNumber(n)); // expected output: 2147483648 |
Output
256 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 codeint main(){ int n = 273; cout << setBitNumber(n); return 0;} |
C
#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
// 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)); }} |
Python3
# Python program to find# MSB number for given n.import mathdef 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 coden = 273 print(setBitNumber(n)) |
C#
// 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// 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.?> |
Javascript
<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> |
Output
256
Time Complexity: O(logn)
Auxiliary Space: O(1)
This article is contributed by Devanshu Agarwal. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
