Posted on by Kalkicode
Code Bit Logic

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 step-by-step 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 low-level programming.

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