Change all bits after most significant bit
In this article, we will discuss a problem related to manipulating bits in a binary representation of a number. The problem statement is as follows: Given an integer number, we need to change all bits in its binary representation after the most significant bit (MSB) to 0 and leave the MSB unchanged. For example, if the number is represented as 10001010 in binary, we should change it to 10000000. In other words, we want to set all bits to the right of the leftmost '1' bit to 0 while keeping the leftmost '1' bit as it is.
16 (10000) => 01111 result = 15 123 (1111011) => 0000100 result = 4
Problem Explanation with an Example
Let's take an example to illustrate the problem. Consider the number 65, which is represented as 1000001 in binary. The most significant bit is at position 7 (counting from 0) from the right, and all bits to the right of this position should be changed to 0. The resultant binary representation would be 1000000, which is equal to 64 in decimal.
The pseudocode to solve this problem can be described as follows:
// Function to change bits after the most significant bit
changeBit(num)
{
n = num
start = 1
while (n >= start)
{
n = start XOR n
start = start left shift by 1 bit
}
Display calculated result
}
Algorithm Explanation
The algorithm starts by defining a function named 'changeBit' that takes an integer 'num' as input. Inside the function, we create two variables 'n' and 'start' and set 'n' to the input number 'num' and 'start' to 1.
The while loop is the key part of the algorithm. It continues as long as 'n' is greater than or equal to 'start'. In each iteration, we perform a bitwise XOR operation between 'n' and 'start' and store the result in 'n'. This operation effectively sets all the bits to the right of the rightmost '1' bit in 'n' to 0, while keeping the leftmost '1' bit unchanged. Then, we left shift 'start' by one position to move to the next bit.
The loop continues until 'n' becomes less than 'start', at which point we exit the loop. The variable 'n' now holds the number with all bits after the most significant bit set to 0, and the original MSB remains unchanged.
Code Solution
// C Program
// Change all bits after most significant bit
#include <stdio.h>
// Change bits of given numbers
void changeBit(int num)
{
int n = num;
int start = 1;
while(n >= start)
{
// Change bits
n = start ^ n;
// shift bits to left by one bit
start = start << 1;
}
// Display calculated result
printf("\n Number : %d",num);
printf("\n After Change Bits : %d",n);
}
int main()
{
// 10000 => 01111
changeBit(16);
// 1111011 => 0000100
changeBit(123);
return 0;
}
Output
Number : 16
After Change Bits : 15
Number : 123
After Change Bits : 4
/*
Java Program for
Change all bits after most significant bit
*/
class SwitchBit
{
// Change bits of given numbers
public void changeBit(int num)
{
int n = num;
int start = 1;
while (n >= start)
{
// Change bits
n = start ^ n;
// shift bits to left by one bit
start = start << 1;
}
// Display calculated result
System.out.print("\n Number : " + num);
System.out.print("\n After Change Bits : " + n);
}
public static void main(String[] args)
{
SwitchBit task = new SwitchBit();
// 10000 => 01111
task.changeBit(16);
// 1111011 => 0000100
task.changeBit(123);
}
}
Output
Number : 16
After Change Bits : 15
Number : 123
After Change Bits : 4
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Change all bits after most significant bit
*/
class SwitchBit
{
public:
// Change bits of given numbers
void changeBit(int num)
{
int n = num;
int start = 1;
while (n >= start)
{
// Change bits
n = start ^ n;
// shift bits to left by one bit
start = start << 1;
}
// Display calculated result
cout << "\n Number : " << num;
cout << "\n After Change Bits : " << n;
}
};
int main()
{
SwitchBit task = SwitchBit();
// 10000 => 01111
task.changeBit(16);
// 1111011 => 0000100
task.changeBit(123);
return 0;
}
Output
Number : 16
After Change Bits : 15
Number : 123
After Change Bits : 4
// Include namespace system
using System;
/*
C# Program for
Change all bits after most significant bit
*/
public class SwitchBit
{
// Change bits of given numbers
public void changeBit(int num)
{
int n = num;
int start = 1;
while (n >= start)
{
// Change bits
n = start ^ n;
// shift bits to left by one bit
start = start << 1;
}
// Display calculated result
Console.Write("\n Number : " + num);
Console.Write("\n After Change Bits : " + n);
}
public static void Main(String[] args)
{
SwitchBit task = new SwitchBit();
// 10000 => 01111
task.changeBit(16);
// 1111011 => 0000100
task.changeBit(123);
}
}
Output
Number : 16
After Change Bits : 15
Number : 123
After Change Bits : 4
<?php
/*
Php Program for
Change all bits after most significant bit
*/
class SwitchBit
{
// Change bits of given numbers
public function changeBit($num)
{
$n = $num;
$start = 1;
while ($n >= $start)
{
// Change bits
$n = $start ^ $n;
// shift bits to left by one bit
$start = $start << 1;
}
// Display calculated result
echo "\n Number : ". $num;
echo "\n After Change Bits : ". $n;
}
}
function main()
{
$task = new SwitchBit();
// 10000 => 01111
$task>changeBit(16);
// 1111011 => 0000100
$task>changeBit(123);
}
main();
Output
Number : 16
After Change Bits : 15
Number : 123
After Change Bits : 4
/*
Node Js Program for
Change all bits after most significant bit
*/
class SwitchBit
{
// Change bits of given numbers
changeBit(num)
{
var n = num;
var start = 1;
while (n >= start)
{
// Change bits
n = start ^ n;
// shift bits to left by one bit
start = start << 1;
}
// Display calculated result
process.stdout.write("\n Number : " + num);
process.stdout.write("\n After Change Bits : " + n);
}
}
function main()
{
var task = new SwitchBit();
// 10000 => 01111
task.changeBit(16);
// 1111011 => 0000100
task.changeBit(123);
}
main();
Output
Number : 16
After Change Bits : 15
Number : 123
After Change Bits : 4
# Python 3 Program for
# Change all bits after most significant bit
class SwitchBit :
# Change bits of given numbers
def changeBit(self, num) :
n = num
start = 1
while (n >= start) :
# Change bits
n = start ^ n
# shift bits to left by one bit
start = start << 1
# Display calculated result
print("\n Number : ", num, end = "")
print("\n After Change Bits : ", n, end = "")
def main() :
task = SwitchBit()
# 10000 => 01111
task.changeBit(16)
# 1111011 => 0000100
task.changeBit(123)
if __name__ == "__main__": main()
Output
Number : 16
After Change Bits : 15
Number : 123
After Change Bits : 4
# Ruby Program for
# Change all bits after most significant bit
class SwitchBit
# Change bits of given numbers
def changeBit(num)
n = num
start = 1
while (n >= start)
# Change bits
n = start ^ n
# Shift bits to left by one bit
start = start << 1
end
# Display calculated result
print("\n Number : ", num)
print("\n After Change Bits : ", n)
end
end
def main()
task = SwitchBit.new()
# 10000 => 01111
task.changeBit(16)
# 1111011 => 0000100
task.changeBit(123)
end
main()
Output
Number : 16
After Change Bits : 15
Number : 123
After Change Bits : 4
/*
Scala Program for
Change all bits after most significant bit
*/
class SwitchBit
{
// Change bits of given numbers
def changeBit(num: Int): Unit = {
var n: Int = num;
var start: Int = 1;
while (n >= start)
{
// Change bits
n = start ^ n;
// Shift bits to left by one bit
start = start << 1;
}
// Display calculated result
print("\n Number : " + num);
print("\n After Change Bits : " + n);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SwitchBit = new SwitchBit();
// 10000 => 01111
task.changeBit(16);
// 1111011 => 0000100
task.changeBit(123);
}
}
Output
Number : 16
After Change Bits : 15
Number : 123
After Change Bits : 4
/*
Swift 4 Program for
Change all bits after most significant bit
*/
class SwitchBit
{
// Change bits of given numbers
func changeBit(_ num: Int)
{
var n: Int = num;
var start: Int = 1;
while (n >= start)
{
// Change bits
n = start ^ n;
// Shift bits to left by one bit
start = start << 1;
}
// Display calculated result
print("\n Number : ", num, terminator: "");
print("\n After Change Bits : ", n, terminator: "");
}
}
func main()
{
let task: SwitchBit = SwitchBit();
// 10000 => 01111
task.changeBit(16);
// 1111011 => 0000100
task.changeBit(123);
}
main();
Output
Number : 16
After Change Bits : 15
Number : 123
After Change Bits : 4
/*
Kotlin Program for
Change all bits after most significant bit
*/
class SwitchBit
{
// Change bits of given numbers
fun changeBit(num: Int): Unit
{
var n: Int = num;
var start: Int = 1;
while (n >= start)
{
// Change bits
n = start xor n;
// Shift bits to left by one bit
start = start shl 1;
}
// Display calculated result
print("\n Number : " + num);
print("\n After Change Bits : " + n);
}
}
fun main(args: Array < String > ): Unit
{
var task: SwitchBit = SwitchBit();
// 10000 => 01111
task.changeBit(16);
// 1111011 => 0000100
task.changeBit(123);
}
Output
Number : 16
After Change Bits : 15
Number : 123
After Change Bits : 4
Time Complexity
The time complexity of this algorithm is O(log N), where N is the given number. This is because the while loop iterates for the number of bits in 'num', which is proportional to the logarithm of 'num' in base 2.
Output Explanation
Let's go through the output of the provided code for the given input numbers:

Input number: 16 (10000 in binary)
After changing bits: 15 (1111 in binary)
Explanation: The most significant bit is at position 4 (counting from 0), and all bits to the right of this position are set to 0. The result is 1111, which is 15 in decimal. 
Input number: 123 (1111011 in binary)
After changing bits: 4 (100 in binary)
Explanation: The most significant bit is at position 6 (counting from 0), and all bits to the right of this position are set to 0. The result is 100, which is 4 in decimal.
Finally
In this article, we discussed a problem related to manipulating bits in a binary representation of a number. We explained how to change all bits after the most significant bit to 0 while keeping the MSB unchanged. We provided a stepbystep explanation of the algorithm to achieve this and analyzed its time complexity. Finally, we demonstrated the algorithm's output with suitable examples. Understanding bit manipulation is crucial for various computer science applications, such as embedded systems, cryptography, and lowlevel programming.
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