Posted on by Kalkicode
Code Bit Logic

# Find most significant set bit of a number without inbuilt function

The given problem aims to find the most significant set bit of a given integer without using any inbuilt functions. The most significant bit is the highest-order bit that is set to 1 in the binary representation of the number. This means finding the leftmost '1' in the binary representation of the given number.

To accomplish this task, we need to develop an algorithm that efficiently identifies the most significant set bit of a number and returns its value.

## Explanation with Suitable Example

Let's take an example to understand the problem better. Consider the number `320`, which is represented in binary as `101000000`. The most significant bit is the leftmost '1', which corresponds to the value `256` in decimal.

## Pseudocode

Before diving into the detailed algorithm, let's present the pseudocode to give an overview of the approach:

``````1. Initialize a variable 'r' to the given number 'n'.
2. Perform right-shift operations on 'r' and bitwise OR operations to get a pattern of 1s.
3. Calculate the value of the most significant bit by adding 1 to the obtained pattern.
4. Return the value of the most significant bit.
``````

## Algorithm

2. Set a temporary variable 'r' to 'n'.
3. Perform the following steps to get a pattern of 1s: a. Right-shift 'r' by 1 bit and perform a bitwise OR operation with the result. b. Repeat the right-shift and bitwise OR operation two more times with 'r'. c. Now, 'r' will have a pattern with all bits to the right of the most significant bit set to 1.
4. To get the value of the most significant bit, add 1 to the pattern obtained in step 3.
5. Return the value as the result.

## Explanation of the Algorithm

1. We start with the given number 'n', and for illustration, let's take `n = 320`.

2. Set 'r' to the given number 'n', so `r = 320`.

3. Perform right-shift and bitwise OR operations on 'r':

a. Right-shift 'r' by 1 bit: `r = r >> 1`, so `r = 160`.

b. Bitwise OR with previous 'r': `r = r | (r >> 1)`, so `r = 160 | (160 >> 1) = 160 | 80 = 240`.

c. Right-shift 'r' by 2 bits: `r = r >> 2`, so `r = 60`.

d. Bitwise OR with previous 'r': `r = r | (r >> 2)`, so `r = 60 | (60 >> 2) = 60 | 15 = 63`.

The variable 'r' now holds a pattern with all bits to the right of the most significant bit set to 1.

4. Calculate the value of the most significant bit by adding 1 to the pattern obtained in step 3:

`value = r + 1`, so `value = 63 + 1 = 64`.

5. Return the value `64` as the result.

## Code Solution

Here given code implementation process.

``````// C Program
// Find most significant set bit of a number without inbuilt function
#include <stdio.h>

#include <math.h>

// Find value of most significant bit
void mostSignificantValue(int n)
{
if (n <= 0)
{
return;
}
int r = n >> 1;
r = r | (r >> 1);
r = r | (r >> 2);
r = r | (r >> 4);
r = r | (r >> 8);
r = r | (r >> 16);
// Get value of most significant bit
int value = r + 1;
// Display calculated result
printf(" Number : %d \n", n);
printf(" Most significant bit value : %d\n", value);
}
int main()
{
// Test A
// 320 = (101000000)
//        ↑
//       256
mostSignificantValue(320);
// (1000) = (1111101000)
//           ↑
//          512
mostSignificantValue(1000);
// (54) = (110110)
//         ↑
//         32
mostSignificantValue(54);
// 5 = (101)
//      ↑
//      4
mostSignificantValue(5);
return 0;
}``````

#### Output

`````` Number : 320
Most significant bit value : 256
Number : 1000
Most significant bit value : 512
Number : 54
Most significant bit value : 32
Number : 5
Most significant bit value : 4``````
``````/*
Java Program
Find most significant set bit of a number without inbuilt function
*/
public class SignificantBit
{
// Find value of most significant bit
public void mostSignificantValue(int n)
{
if (n <= 0)
{
return;
}
int r = n >> 1;
r = r | (r >> 1);
r = r | (r >> 2);
r = r | (r >> 4);
r = r | (r >> 8);
r = r | (r >> 16);
// Get value of most significant bit
int value = r + 1;
// Display calculated result
System.out.print(" Number : " + n + " \n");
System.out.print(" Most significant bit value : " +
value + "\n");
}
public static void main(String[] args)
{
// Test A
// 320 = (101000000)
//        ↑
//       256
// (1000) = (1111101000)
//           ↑
//          512
// (54) = (110110)
//         ↑
//         32
// 5 = (101)
//      ↑
//      4
}
}``````

#### Output

`````` Number : 320
Most significant bit value : 256
Number : 1000
Most significant bit value : 512
Number : 54
Most significant bit value : 32
Number : 5
Most significant bit value : 4``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program
Find most significant set bit of a
number without inbuilt function
*/
class SignificantBit
{
public:
// Find value of most significant bit
void mostSignificantValue(int n)
{
if (n <= 0)
{
return;
}
int r = n >> 1;
r = r | (r >> 1);
r = r | (r >> 2);
r = r | (r >> 4);
r = r | (r >> 8);
r = r | (r >> 16);
// Get value of most significant bit
int value = r + 1;
// Display calculated result
cout << " Number : " << n << " \n";
cout << " Most significant bit value : "
<< value << "\n";
}
};
int main()
{
// Test A
// 320 = (101000000)
//        ↑
//       256
// (1000) = (1111101000)
//           ↑
//          512
// (54) = (110110)
//         ↑
//         32
// 5 = (101)
//      ↑
//      4
return 0;
}``````

#### Output

`````` Number : 320
Most significant bit value : 256
Number : 1000
Most significant bit value : 512
Number : 54
Most significant bit value : 32
Number : 5
Most significant bit value : 4``````
``````// Include namespace system
using System;
/*
Csharp Program
Find most significant set bit of a number without inbuilt function
*/
public class SignificantBit
{
// Find value of most significant bit
public void mostSignificantValue(int n)
{
if (n <= 0)
{
return;
}
int r = n >> 1;
r = r | (r >> 1);
r = r | (r >> 2);
r = r | (r >> 4);
r = r | (r >> 8);
r = r | (r >> 16);
// Get value of most significant bit
int value = r + 1;
// Display calculated result
Console.Write(" Number : " + n + " \n");
Console.Write(" Most significant bit value : " + value + "\n");
}
public static void Main(String[] args)
{
// Test A
// 320 = (101000000)
//        ↑
//       256
// (1000) = (1111101000)
//           ↑
//          512
// (54) = (110110)
//         ↑
//         32
// 5 = (101)
//      ↑
//      4
}
}``````

#### Output

`````` Number : 320
Most significant bit value : 256
Number : 1000
Most significant bit value : 512
Number : 54
Most significant bit value : 32
Number : 5
Most significant bit value : 4``````
``````package main
import "fmt"
/*
Go Program
Find most significant set bit of a number without inbuilt function
*/
type SignificantBit struct {}
func getSignificantBit() * SignificantBit {
var me *SignificantBit = &SignificantBit {}
return me
}
// Find value of most significant bit
func(this SignificantBit) mostSignificantValue(n int) {
if n <= 0 {
return
}
var r int = n >> 1
r = r | (r >> 1)
r = r | (r >> 2)
r = r | (r >> 4)
r = r | (r >> 8)
r = r | (r >> 16)
// Get value of most significant bit
var value int = r + 1
// Display calculated result
fmt.Print(" Number : ", n, " \n")
fmt.Print(" Most significant bit value : ", value, "\n")
}
func main() {
var task * SignificantBit = getSignificantBit()
// Test A
// 320 = (101000000)
//        ↑
//       256
// (1000) = (1111101000)
//           ↑
//          512
// (54) = (110110)
//         ↑
//         32
// 5 = (101)
//      ↑
//      4
}``````

#### Output

`````` Number : 320
Most significant bit value : 256
Number : 1000
Most significant bit value : 512
Number : 54
Most significant bit value : 32
Number : 5
Most significant bit value : 4``````
``````<?php
/*
Php Program
Find most significant set bit of a number without inbuilt function
*/
class SignificantBit
{
// Find value of most significant bit
public	function mostSignificantValue(\$n)
{
if (\$n <= 0)
{
return;
}
\$r = \$n >> 1;
\$r = \$r | (\$r >> 1);
\$r = \$r | (\$r >> 2);
\$r = \$r | (\$r >> 4);
\$r = \$r | (\$r >> 8);
\$r = \$r | (\$r >> 16);
// Get value of most significant bit
\$value = \$r + 1;
// Display calculated result
echo(" Number : ".\$n." \n");
echo(" Most significant bit value : ".\$value."\n");
}
}

function main()
{
// Test A
// 320 = (101000000)
//        ↑
//       256
// (1000) = (1111101000)
//           ↑
//          512
// (54) = (110110)
//         ↑
//         32
// 5 = (101)
//      ↑
//      4
}
main();``````

#### Output

`````` Number : 320
Most significant bit value : 256
Number : 1000
Most significant bit value : 512
Number : 54
Most significant bit value : 32
Number : 5
Most significant bit value : 4``````
``````/*
Node JS Program
Find most significant set bit of a number without inbuilt function
*/
class SignificantBit
{
// Find value of most significant bit
mostSignificantValue(n)
{
if (n <= 0)
{
return;
}
var r = n >> 1;
r = r | (r >> 1);
r = r | (r >> 2);
r = r | (r >> 4);
r = r | (r >> 8);
r = r | (r >> 16);
// Get value of most significant bit
var value = r + 1;
// Display calculated result
process.stdout.write(" Number : " + n + " \n");
process.stdout.write(" Most significant bit value : " +
value + "\n");
}
}

function main()
{
// Test A
// 320 = (101000000)
//        ↑
//       256
// (1000) = (1111101000)
//           ↑
//          512
// (54) = (110110)
//         ↑
//         32
// 5 = (101)
//      ↑
//      4
}
main();``````

#### Output

`````` Number : 320
Most significant bit value : 256
Number : 1000
Most significant bit value : 512
Number : 54
Most significant bit value : 32
Number : 5
Most significant bit value : 4``````
``````#    Python 3 Program
#    Find most significant set bit of a number without inbuilt function
class SignificantBit :
#  Find value of most significant bit
def mostSignificantValue(self, n) :
if (n <= 0) :
return

r = n >> 1
r = r | (r >> 1)
r = r | (r >> 2)
r = r | (r >> 4)
r = r | (r >> 8)
r = r | (r >> 16)
#  Get value of most significant bit
value = r + 1
#  Display calculated result
print(" Number : ", n ," ")
print(" Most significant bit value : ", value )

def main() :
#  Test A
#  320 = (101000000)
#         ↑
#        256
#  (1000) = (1111101000)
#            ↑
#           512
#  (54) = (110110)
#          ↑
#          32
#  5 = (101)
#       ↑
#       4

if __name__ == "__main__": main()``````

#### Output

`````` Number :  320
Most significant bit value :  256
Number :  1000
Most significant bit value :  512
Number :  54
Most significant bit value :  32
Number :  5
Most significant bit value :  4``````
``````#    Ruby Program
#    Find most significant set bit of a number without inbuilt function
class SignificantBit
#  Find value of most significant bit
def mostSignificantValue(n)
if (n <= 0)
return
end

r = n >> 1
r = r | (r >> 1)
r = r | (r >> 2)
r = r | (r >> 4)
r = r | (r >> 8)
r = r | (r >> 16)
#  Get value of most significant bit
value = r + 1
#  Display calculated result
print(" Number : ", n ," \n")
print(" Most significant bit value : ", value ,"\n")
end

end

def main()
#  Test A
#  320 = (101000000)
#         ↑
#        256
#  (1000) = (1111101000)
#            ↑
#           512
#  (54) = (110110)
#          ↑
#          32
#  5 = (101)
#       ↑
#       4
end

main()``````

#### Output

`````` Number : 320
Most significant bit value : 256
Number : 1000
Most significant bit value : 512
Number : 54
Most significant bit value : 32
Number : 5
Most significant bit value : 4
``````
``````/*
Scala Program
Find most significant set bit of a number without inbuilt function
*/
class SignificantBit()
{
// Find value of most significant bit
def mostSignificantValue(n: Int): Unit = {
if (n <= 0)
{
return;
}
var r: Int = n >> 1;
r = r | (r >> 1);
r = r | (r >> 2);
r = r | (r >> 4);
r = r | (r >> 8);
r = r | (r >> 16);
// Get value of most significant bit
var value: Int = r + 1;
// Display calculated result
print(" Number : " + n + " \n");
print(" Most significant bit value : " + value + "\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SignificantBit = new SignificantBit();
// Test A
// 320 = (101000000)
//        ↑
//       256
// (1000) = (1111101000)
//           ↑
//          512
// (54) = (110110)
//         ↑
//         32
// 5 = (101)
//      ↑
//      4
}
}``````

#### Output

`````` Number : 320
Most significant bit value : 256
Number : 1000
Most significant bit value : 512
Number : 54
Most significant bit value : 32
Number : 5
Most significant bit value : 4``````
``````/*
Swift 4 Program
Find most significant set bit of a number without inbuilt function
*/
class SignificantBit
{
// Find value of most significant bit
func mostSignificantValue(_ n: Int)
{
if (n <= 0)
{
return;
}
var r: Int = n >> 1;
r = r | (r >> 1);
r = r | (r >> 2);
r = r | (r >> 4);
r = r | (r >> 8);
r = r | (r >> 16);
// Get value of most significant bit
let value: Int = r + 1;
// Display calculated result
print(" Number : ", n ," ");
print(" Most significant bit value : ", value );
}
}
func main()
{
// Test
// 320 = (101000000)
//        ↑
//       256
// (1000) = (1111101000)
//           ↑
//          512
// (54) = (110110)
//         ↑
//         32
// 5 = (101)
//      ↑
//      4
}
main();``````

#### Output

`````` Number :  320
Most significant bit value :  256
Number :  1000
Most significant bit value :  512
Number :  54
Most significant bit value :  32
Number :  5
Most significant bit value :  4``````
``````/*
Kotlin Program
Find most significant set bit of a number without inbuilt function
*/
class SignificantBit
{
// Find value of most significant bit
fun mostSignificantValue(n: Int): Unit
{
if (n <= 0)
{
return;
}
var r: Int = n shr 1;
r = r or(r shr 1);
r = r or(r shr 2);
r = r or(r shr 4);
r = r or(r shr 8);
r = r or(r shr 16);
// Get value of most significant bit
val value: Int = r + 1;
// Display calculated result
print(" Number : " + n + " \n");
print(" Most significant bit value : " + value + "\n");
}
}
fun main(args: Array < String > ): Unit
{
// Test A
// 320 = (101000000)
//        ↑
//       256
// (1000) = (1111101000)
//           ↑
//          512
// (54) = (110110)
//         ↑
//         32
// 5 = (101)
//      ↑
//      4
}``````

#### Output

`````` Number : 320
Most significant bit value : 256
Number : 1000
Most significant bit value : 512
Number : 54
Most significant bit value : 32
Number : 5
Most significant bit value : 4``````

Each output is showing the given number and its corresponding most significant bit value calculated using the algorithm we explained above.

## Time Complexity

The time complexity of the given algorithm mainly depends on the number of bits in the input 'n'. Since the algorithm involves several right-shift and bitwise OR operations, we can consider the time complexity as O(log n), where 'n' is the input number. This is because the number of operations required to find the most significant bit increases logarithmically with the magnitude of the number.

## Conclusion

The provided code efficiently finds the most significant set bit of a given number without using any inbuilt functions. The algorithm employs bitwise operations to obtain a pattern with all bits to the right of the most significant bit set to 1 and then calculates the value of the most significant bit by adding 1 to that pattern. The code's time complexity is O(log n), making it a suitable solution for large numbers as well.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post