Posted on by Kalkicode
Code Bit Logic

Remove the most significant set bit of a number

The given problem is to remove the most significant set bit (i.e., the leftmost set bit) of a given number. A set bit refers to a binary digit with a value of 1. The task is to find a way to remove the leftmost set bit and return the resulting number.

Explanation with Suitable Examples

Let's understand the problem with some examples:

Example 1

Input: num = 320 (binary: 101000000)

Output: The most significant set bit is at the 8th position (from right to left). Removing it leaves us with 64 (binary: 1000000).

Example 2

Input: num = 1000 (binary: 1111101000)

Output: The most significant set bit is at the 4th position. Removing it gives us 488 (binary: 111101000).

Example 3

Input: num = 54 (binary: 110110)

Output: The most significant set bit is at the 6th position. Removing it gives us 22 (binary: 10110).

Example 4

Input: num = 5 (binary: 101)

Output: The most significant set bit is at the 3rd position. Removing it gives us 1 (binary: 01).

Standard Pseudocode

removeSignificantBit(num)
    if num is less than or equal to 0, return
    r = num >> 1
    r = r | (r >> 1)
    r = r | (r >> 2)
    r = r | (r >> 4)
    r = r | (r >> 8)
    r = r | (r >> 16)
    value = r & num
    print "Number:", num
    print "Result:", value

Algorithm Explanation

  1. Check if the input number (num) is less than or equal to 0. If it is, there is no set bit to remove, so return from the function.

  2. Initialize a variable r as num shifted right by 1 (num >> 1). This sets the second most significant bit of r to 1 if the first most significant bit of num is 1, otherwise, it sets it to 0.

  3. Perform bitwise OR operation between r and (r >> 1). This sets the third most significant bit of r to 1 if the first or second most significant bit of num is 1.

  4. Repeat step 3 for (r >> 2), (r >> 4), (r >> 8), and (r >> 16) to set the remaining higher bits to 1 if any of the lower bits are 1.

  5. Perform bitwise AND operation between r and num to get the number with the most significant bit removed.

  6. Display the original number (num) and the resulting value after removing the most significant bit.

Code Solution

Here given code implementation process.

// C Program 
// Remove the most significant set bit of a number
#include <stdio.h>

// Remove a most significant bit of given number
void removeSignificantBit(int num)
{
	if (num <= 0)
	{
		return;
	}
	int r = num >> 1;
	r = r | (r >> 1);
	r = r | (r >> 2);
	r = r | (r >> 4);
	r = r | (r >> 8);
	r = r | (r >> 16);
	// Remove most significant bit
	int value = r & num;
	// Display calculated result
	printf(" Number : %d \n", num);
	printf(" Result : %d \n", value);
}
int main()
{
	// Test A
	// 320 = (101000000)
	// Remove ↑
	// ---------------------
	//          1000000)
	// Result : 64
	removeSignificantBit(320);
	// Test B
	// (1000) = (1111101000)
	//  Remove   ↑
	//            111101000
	// ---------------------
	// Result : 488
	removeSignificantBit(1000);
	// Test C
	// (54) = (110110) 
	// Remove  ↑
	//          10110
	// ---------------------
	// Result : 22
	removeSignificantBit(54);
	// Test D
	// 5    = (101) 
	// Remove  ↑
	//          01
	// ---------------------
	// Result : 1
	removeSignificantBit(5);
	return 0;
}

Output

 Number : 320
 Result : 64
 Number : 1000
 Result : 488
 Number : 54
 Result : 22
 Number : 5
 Result : 1
/*
    Java Program
    Remove the most significant set bit of a number
*/
public class SignificantBit
{
	// Remove a most significant bit of given number
	public void removeSignificantBit(int num)
	{
		if (num <= 0)
		{
			return;
		}
		int r = num >> 1;
		r = r | (r >> 1);
		r = r | (r >> 2);
		r = r | (r >> 4);
		r = r | (r >> 8);
		r = r | (r >> 16);
		// Remove most significant bit
		int value = r & num;
		// Display calculated result
		System.out.print(" Number : " + num + " \n");
		System.out.print(" Result : " + value + " \n");
	}
	public static void main(String[] args)
	{
		SignificantBit task = new SignificantBit();
		// Test A
		// 320 = (101000000)
		// Remove ↑
		// ---------------------
		//          1000000)
		// Result : 64
		task.removeSignificantBit(320);
		// Test B
		// (1000) = (1111101000)
		//  Remove   ↑
		//            111101000
		// ---------------------
		// Result : 488
		task.removeSignificantBit(1000);
		// Test C
		// (54) = (110110) 
		// Remove  ↑
		//          10110
		// ---------------------
		// Result : 22
		task.removeSignificantBit(54);
		// Test D
		// 5    = (101) 
		// Remove  ↑
		//          01
		// ---------------------
		// Result : 1
		task.removeSignificantBit(5);
	}
}

Output

 Number : 320
 Result : 64
 Number : 1000
 Result : 488
 Number : 54
 Result : 22
 Number : 5
 Result : 1
// Include header file
#include <iostream>

using namespace std;
/*
    C++ Program
    Remove the most significant set bit of a number
*/
class SignificantBit
{
	public:
		// Remove a most significant bit of given number
		void removeSignificantBit(int num)
		{
			if (num <= 0)
			{
				return;
			}
			int r = num >> 1;
			r = r | (r >> 1);
			r = r | (r >> 2);
			r = r | (r >> 4);
			r = r | (r >> 8);
			r = r | (r >> 16);
			// Remove most significant bit
			int value = r #
			// Display calculated result
			cout << " Number : " << num << " \n";
			cout << " Result : " << value << " \n";
		}
};
int main()
{
	SignificantBit *task = new SignificantBit();
	// Test A
	// 320 = (101000000)
	// Remove ↑
	// ---------------------
	//          1000000)
	// Result : 64
	task->removeSignificantBit(320);
	// Test B
	// (1000) = (1111101000)
	//  Remove   ↑
	//            111101000
	// ---------------------
	// Result : 488
	task->removeSignificantBit(1000);
	// Test C
	// (54) = (110110) 
	// Remove  ↑
	//          10110
	// ---------------------
	// Result : 22
	task->removeSignificantBit(54);
	// Test D
	// 5    = (101) 
	// Remove  ↑
	//          01
	// ---------------------
	// Result : 1
	task->removeSignificantBit(5);
	return 0;
}

Output

 Number : 320
 Result : 64
 Number : 1000
 Result : 488
 Number : 54
 Result : 22
 Number : 5
 Result : 1
// Include namespace system
using System;
/*
    Csharp Program
    Remove the most significant set bit of a number
*/
public class SignificantBit
{
	// Remove a most significant bit of given number
	public void removeSignificantBit(int num)
	{
		if (num <= 0)
		{
			return;
		}
		int r = num >> 1;
		r = r | (r >> 1);
		r = r | (r >> 2);
		r = r | (r >> 4);
		r = r | (r >> 8);
		r = r | (r >> 16);
		// Remove most significant bit
		int value = r & num;
		// Display calculated result
		Console.Write(" Number : " + num + " \n");
		Console.Write(" Result : " + value + " \n");
	}
	public static void Main(String[] args)
	{
		SignificantBit task = new SignificantBit();
		// Test A
		// 320 = (101000000)
		// Remove ↑
		// ---------------------
		//          1000000)
		// Result : 64
		task.removeSignificantBit(320);
		// Test B
		// (1000) = (1111101000)
		//  Remove   ↑
		//            111101000
		// ---------------------
		// Result : 488
		task.removeSignificantBit(1000);
		// Test C
		// (54) = (110110) 
		// Remove  ↑
		//          10110
		// ---------------------
		// Result : 22
		task.removeSignificantBit(54);
		// Test D
		// 5    = (101) 
		// Remove  ↑
		//          01
		// ---------------------
		// Result : 1
		task.removeSignificantBit(5);
	}
}

Output

 Number : 320
 Result : 64
 Number : 1000
 Result : 488
 Number : 54
 Result : 22
 Number : 5
 Result : 1
package main
import "fmt"
/*
    Go Program
    Remove the most significant set bit of a number
*/
type SignificantBit struct {}
func getSignificantBit() * SignificantBit {
	var me *SignificantBit = &SignificantBit {}
	return me
}
// Remove a most significant bit of given number
func(this SignificantBit) removeSignificantBit(num int) {
	if num <= 0 {
		return
	}
	var r int = num >> 1
	r = r | (r >> 1)
	r = r | (r >> 2)
	r = r | (r >> 4)
	r = r | (r >> 8)
	r = r | (r >> 16)
	// Remove most significant bit
	var value int = r & num
	// Display calculated result
	fmt.Print(" Number : ", num, " \n")
	fmt.Print(" Result : ", value, " \n")
}
func main() {
	var task * SignificantBit = getSignificantBit()
	// Test A
	// 320 = (101000000)
	// Remove ↑
	// ---------------------
	//          1000000)
	// Result : 64
	task.removeSignificantBit(320)
	// Test B
	// (1000) = (1111101000)
	//  Remove   ↑
	//            111101000
	// ---------------------
	// Result : 488
	task.removeSignificantBit(1000)
	// Test C
	// (54) = (110110) 
	// Remove  ↑
	//          10110
	// ---------------------
	// Result : 22
	task.removeSignificantBit(54)
	// Test D
	// 5    = (101) 
	// Remove  ↑
	//          01
	// ---------------------
	// Result : 1
	task.removeSignificantBit(5)
}

Output

 Number : 320
 Result : 64
 Number : 1000
 Result : 488
 Number : 54
 Result : 22
 Number : 5
 Result : 1
<?php
/*
    Php Program
    Remove the most significant set bit of a number
*/
class SignificantBit
{
	// Remove a most significant bit of given number
	public	function removeSignificantBit($num)
	{
		if ($num <= 0)
		{
			return;
		}
		$r = $num >> 1;
		$r = $r | ($r >> 1);
		$r = $r | ($r >> 2);
		$r = $r | ($r >> 4);
		$r = $r | ($r >> 8);
		$r = $r | ($r >> 16);
		// Remove most significant bit
		$value = $r & $num;
		// Display calculated result
		echo(" Number : ".$num.
			" \n");
		echo(" Result : ".$value.
			" \n");
	}
}

function main()
{
	$task = new SignificantBit();
	// Test A
	// 320 = (101000000)
	// Remove ↑
	// ---------------------
	//          1000000)
	// Result : 64
	$task->removeSignificantBit(320);
	// Test B
	// (1000) = (1111101000)
	//  Remove   ↑
	//            111101000
	// ---------------------
	// Result : 488
	$task->removeSignificantBit(1000);
	// Test C
	// (54) = (110110) 
	// Remove  ↑
	//          10110
	// ---------------------
	// Result : 22
	$task->removeSignificantBit(54);
	// Test D
	// 5    = (101) 
	// Remove  ↑
	//          01
	// ---------------------
	// Result : 1
	$task->removeSignificantBit(5);
}
main();

Output

 Number : 320
 Result : 64
 Number : 1000
 Result : 488
 Number : 54
 Result : 22
 Number : 5
 Result : 1
/*
    Node JS Program
    Remove the most significant set bit of a number
*/
class SignificantBit
{
	// Remove a most significant bit of given number
	removeSignificantBit(num)
	{
		if (num <= 0)
		{
			return;
		}
		var r = num >> 1;
		r = r | (r >> 1);
		r = r | (r >> 2);
		r = r | (r >> 4);
		r = r | (r >> 8);
		r = r | (r >> 16);
		// Remove most significant bit
		var value = r & num;
		// Display calculated result
		process.stdout.write(" Number : " + num + " \n");
		process.stdout.write(" Result : " + value + " \n");
	}
}

function main()
{
	var task = new SignificantBit();
	// Test A
	// 320 = (101000000)
	// Remove ↑
	// ---------------------
	//          1000000)
	// Result : 64
	task.removeSignificantBit(320);
	// Test B
	// (1000) = (1111101000)
	//  Remove   ↑
	//            111101000
	// ---------------------
	// Result : 488
	task.removeSignificantBit(1000);
	// Test C
	// (54) = (110110) 
	// Remove  ↑
	//          10110
	// ---------------------
	// Result : 22
	task.removeSignificantBit(54);
	// Test D
	// 5    = (101) 
	// Remove  ↑
	//          01
	// ---------------------
	// Result : 1
	task.removeSignificantBit(5);
}
main();

Output

 Number : 320
 Result : 64
 Number : 1000
 Result : 488
 Number : 54
 Result : 22
 Number : 5
 Result : 1
#    Python 3 Program
#    Remove the most significant set bit of a number
class SignificantBit :
	#  Remove a most significant bit of given number
	def removeSignificantBit(self, num) :
		if (num <= 0) :
			return
		
		r = num >> 1
		r = r | (r >> 1)
		r = r | (r >> 2)
		r = r | (r >> 4)
		r = r | (r >> 8)
		r = r | (r >> 16)
		#  Remove most significant bit
		value = r & num
		#  Display calculated result
		print(" Number : ", num ," ")
		print(" Result : ", value ," ")
	

def main() :
	task = SignificantBit()
	#  Test A
	#  320 = (101000000)
	#  Remove ↑
	#  ---------------------
	#           1000000)
	#  Result : 64
	task.removeSignificantBit(320)
	#  Test B
	#  (1000) = (1111101000)
	#   Remove   ↑
	#             111101000
	#  ---------------------
	#  Result : 488
	task.removeSignificantBit(1000)
	#  Test C
	#  (54) = (110110) 
	#  Remove  ↑
	#           10110
	#  ---------------------
	#  Result : 22
	task.removeSignificantBit(54)
	#  Test D
	#  5    = (101) 
	#  Remove  ↑
	#           01
	#  ---------------------
	#  Result : 1
	task.removeSignificantBit(5)

if __name__ == "__main__": main()

Output

 Number :  320
 Result :  64
 Number :  1000
 Result :  488
 Number :  54
 Result :  22
 Number :  5
 Result :  1
#    Ruby Program
#    Remove the most significant set bit of a number
class SignificantBit 
	#  Remove a most significant bit of given number
	def removeSignificantBit(num) 
		if (num <= 0) 
			return
		end

		r = num >> 1
		r = r | (r >> 1)
		r = r | (r >> 2)
		r = r | (r >> 4)
		r = r | (r >> 8)
		r = r | (r >> 16)
		#  Remove most significant bit
		value = r & num
		#  Display calculated result
		print(" Number : ", num ," \n")
		print(" Result : ", value ," \n")
	end

end

def main() 
	task = SignificantBit.new()
	#  Test A
	#  320 = (101000000)
	#  Remove ↑
	#  ---------------------
	#           1000000)
	#  Result : 64
	task.removeSignificantBit(320)
	#  Test B
	#  (1000) = (1111101000)
	#   Remove   ↑
	#             111101000
	#  ---------------------
	#  Result : 488
	task.removeSignificantBit(1000)
	#  Test C
	#  (54) = (110110) 
	#  Remove  ↑
	#           10110
	#  ---------------------
	#  Result : 22
	task.removeSignificantBit(54)
	#  Test D
	#  5    = (101) 
	#  Remove  ↑
	#           01
	#  ---------------------
	#  Result : 1
	task.removeSignificantBit(5)
end

main()

Output

 Number : 320 
 Result : 64 
 Number : 1000 
 Result : 488 
 Number : 54 
 Result : 22 
 Number : 5 
 Result : 1 

/*
    Scala Program
    Remove the most significant set bit of a number
*/
class SignificantBit()
{
	// Remove a most significant bit of given number
	def removeSignificantBit(num: Int): Unit = {
		if (num <= 0)
		{
			return;
		}
		var r: Int = num >> 1;
		r = r | (r >> 1);
		r = r | (r >> 2);
		r = r | (r >> 4);
		r = r | (r >> 8);
		r = r | (r >> 16);
		// Remove most significant bit
		var value: Int = r & num;
		// Display calculated result
		print(" Number : " + num + " \n");
		print(" Result : " + value + " \n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: SignificantBit = new SignificantBit();
		// Test A
		// 320 = (101000000)
		// Remove ↑
		// ---------------------
		//          1000000)
		// Result : 64
		task.removeSignificantBit(320);
		// Test B
		// (1000) = (1111101000)
		//  Remove   ↑
		//            111101000
		// ---------------------
		// Result : 488
		task.removeSignificantBit(1000);
		// Test C
		// (54) = (110110) 
		// Remove  ↑
		//          10110
		// ---------------------
		// Result : 22
		task.removeSignificantBit(54);
		// Test D
		// 5    = (101) 
		// Remove  ↑
		//          01
		// ---------------------
		// Result : 1
		task.removeSignificantBit(5);
	}
}

Output

 Number : 320
 Result : 64
 Number : 1000
 Result : 488
 Number : 54
 Result : 22
 Number : 5
 Result : 1
/*
    Swift 4 Program
    Remove the most significant set bit of a number
*/
class SignificantBit
{
	// Remove a most significant bit of given number
	func removeSignificantBit(_ num: Int)
	{
		if (num <= 0)
		{
			return;
		}
		var r: Int = num >> 1;
		r = r | (r >> 1);
		r = r | (r >> 2);
		r = r | (r >> 4);
		r = r | (r >> 8);
		r = r | (r >> 16);
		// Remove most significant bit
		let value: Int = r & num;
		// Display calculated result
		print(" Number : ", num );
		print(" Result : ", value );
	}
}
func main()
{
	let task: SignificantBit = SignificantBit();
	// Test A
	// 320 = (101000000)
	// Remove ↑
	// ---------------------
	//          1000000)
	// Result : 64
	task.removeSignificantBit(320);
	// Test B
	// (1000) = (1111101000)
	//  Remove   ↑
	//            111101000
	// ---------------------
	// Result : 488
	task.removeSignificantBit(1000);
	// Test C
	// (54) = (110110) 
	// Remove  ↑
	//          10110
	// ---------------------
	// Result : 22
	task.removeSignificantBit(54);
	// Test D
	// 5    = (101) 
	// Remove  ↑
	//          01
	// ---------------------
	// Result : 1
	task.removeSignificantBit(5);
}
main();

Output

 Number :  320
 Result :  64
 Number :  1000
 Result :  488
 Number :  54
 Result :  22
 Number :  5
 Result :  1
/*
    Kotlin Program
    Remove the most significant set bit of a number
*/
class SignificantBit
{
	// Remove a most significant bit of given number
	fun removeSignificantBit(num: Int): Unit
	{
		if (num <= 0)
		{
			return;
		}
		var r: Int = num 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);
		// Remove most significant bit
		val value: Int = r and num;
		// Display calculated result
		print(" Number : " + num + " \n");
		print(" Result : " + value + " \n");
	}
}
fun main(args: Array < String > ): Unit
{
	val task: SignificantBit = SignificantBit();
	// Test A
	// 320 = (101000000)
	// Remove ↑
	// ---------------------
	//          1000000)
	// Result : 64
	task.removeSignificantBit(320);
	// Test B
	// (1000) = (1111101000)
	//  Remove   ↑
	//            111101000
	// ---------------------
	// Result : 488
	task.removeSignificantBit(1000);
	// Test C
	// (54) = (110110) 
	// Remove  ↑
	//          10110
	// ---------------------
	// Result : 22
	task.removeSignificantBit(54);
	// Test D
	// 5    = (101) 
	// Remove  ↑
	//          01
	// ---------------------
	// Result : 1
	task.removeSignificantBit(5);
}

Output

 Number : 320
 Result : 64
 Number : 1000
 Result : 488
 Number : 54
 Result : 22
 Number : 5
 Result : 1

Resultant Output Explanation

The code provided in the main function calls the removeSignificantBit function for four different test cases and prints the original number and the result after removing the most significant bit for each case.

For example, for the input num = 320, the code correctly identifies the most significant set bit at the 8th position and removes it to get the result 64. Similarly, it works for other test cases as well.

Time Complexity

The time complexity of the given code can be analyzed as follows:

  1. The loop runs six times, each time doing bitwise operations, which is constant time complexity O(1).

  2. Therefore, the overall time complexity of the code is O(1).

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





Categories
Relative Post