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
-
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.
-
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.
-
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.
-
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.
-
Perform bitwise AND operation between r and num to get the number with the most significant bit removed.
-
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:
-
The loop runs six times, each time doing bitwise operations, which is constant time complexity O(1).
-
Therefore, the overall time complexity of the code is O(1).
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