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

  1. Start with the given number 'n'.
  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)
	{
		SignificantBit task = new SignificantBit();
		// Test A
		// 320 = (101000000)
		//        ↑
		//       256
		task.mostSignificantValue(320);
		// (1000) = (1111101000)
		//           ↑
		//          512
		task.mostSignificantValue(1000);
		// (54) = (110110) 
		//         ↑
		//         32
		task.mostSignificantValue(54);
		// 5 = (101) 
		//      ↑
		//      4
		task.mostSignificantValue(5);
	}
}

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()
{
	SignificantBit *task = new SignificantBit();
	// Test A
	// 320 = (101000000)
	//        ↑
	//       256
	task->mostSignificantValue(320);
	// (1000) = (1111101000)
	//           ↑
	//          512
	task->mostSignificantValue(1000);
	// (54) = (110110) 
	//         ↑
	//         32
	task->mostSignificantValue(54);
	// 5 = (101) 
	//      ↑
	//      4
	task->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
// 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)
	{
		SignificantBit task = new SignificantBit();
		// Test A
		// 320 = (101000000)
		//        ↑
		//       256
		task.mostSignificantValue(320);
		// (1000) = (1111101000)
		//           ↑
		//          512
		task.mostSignificantValue(1000);
		// (54) = (110110) 
		//         ↑
		//         32
		task.mostSignificantValue(54);
		// 5 = (101) 
		//      ↑
		//      4
		task.mostSignificantValue(5);
	}
}

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
	task.mostSignificantValue(320)
	// (1000) = (1111101000)
	//           ↑
	//          512
	task.mostSignificantValue(1000)
	// (54) = (110110) 
	//         ↑
	//         32
	task.mostSignificantValue(54)
	// 5 = (101) 
	//      ↑
	//      4
	task.mostSignificantValue(5)
}

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()
{
	$task = new SignificantBit();
	// Test A
	// 320 = (101000000)
	//        ↑
	//       256
	$task->mostSignificantValue(320);
	// (1000) = (1111101000)
	//           ↑
	//          512
	$task->mostSignificantValue(1000);
	// (54) = (110110) 
	//         ↑
	//         32
	$task->mostSignificantValue(54);
	// 5 = (101) 
	//      ↑
	//      4
	$task->mostSignificantValue(5);
}
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()
{
	var task = new SignificantBit();
	// Test A
	// 320 = (101000000)
	//        ↑
	//       256
	task.mostSignificantValue(320);
	// (1000) = (1111101000)
	//           ↑
	//          512
	task.mostSignificantValue(1000);
	// (54) = (110110) 
	//         ↑
	//         32
	task.mostSignificantValue(54);
	// 5 = (101) 
	//      ↑
	//      4
	task.mostSignificantValue(5);
}
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() :
	task = SignificantBit()
	#  Test A
	#  320 = (101000000)
	#         ↑
	#        256
	task.mostSignificantValue(320)
	#  (1000) = (1111101000)
	#            ↑
	#           512
	task.mostSignificantValue(1000)
	#  (54) = (110110) 
	#          ↑
	#          32
	task.mostSignificantValue(54)
	#  5 = (101) 
	#       ↑
	#       4
	task.mostSignificantValue(5)

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() 
	task = SignificantBit.new()
	#  Test A
	#  320 = (101000000)
	#         ↑
	#        256
	task.mostSignificantValue(320)
	#  (1000) = (1111101000)
	#            ↑
	#           512
	task.mostSignificantValue(1000)
	#  (54) = (110110) 
	#          ↑
	#          32
	task.mostSignificantValue(54)
	#  5 = (101) 
	#       ↑
	#       4
	task.mostSignificantValue(5)
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
		task.mostSignificantValue(320);
		// (1000) = (1111101000)
		//           ↑
		//          512
		task.mostSignificantValue(1000);
		// (54) = (110110) 
		//         ↑
		//         32
		task.mostSignificantValue(54);
		// 5 = (101) 
		//      ↑
		//      4
		task.mostSignificantValue(5);
	}
}

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()
{
	let task: SignificantBit = SignificantBit();
	// Test 
	// 320 = (101000000)
	//        ↑
	//       256
	task.mostSignificantValue(320);
	// (1000) = (1111101000)
	//           ↑
	//          512
	task.mostSignificantValue(1000);
	// (54) = (110110) 
	//         ↑
	//         32
	task.mostSignificantValue(54);
	// 5 = (101) 
	//      ↑
	//      4
	task.mostSignificantValue(5);
}
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
{
	val task: SignificantBit = SignificantBit();
	// Test A
	// 320 = (101000000)
	//        ↑
	//       256
	task.mostSignificantValue(320);
	// (1000) = (1111101000)
	//           ↑
	//          512
	task.mostSignificantValue(1000);
	// (54) = (110110) 
	//         ↑
	//         32
	task.mostSignificantValue(54);
	// 5 = (101) 
	//      ↑
	//      4
	task.mostSignificantValue(5);
}

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.

New Comment