Posted on by Kalkicode
Code Bit Logic

Invert k most significant bits of number

The problem addressed here is to invert the k most significant bits of a given number. In other words, given an integer num and a positive integer k, the objective is to flip the values of the k most significant bits of num while keeping the rest of the bits unchanged.

Problem Statement and Description

Bit manipulation is a technique often used in programming to work with individual bits of integers. In this problem, the task is to modify the k most significant bits of a number num, effectively changing its value while preserving the remaining bits.


num = 321  k = 4
321 = (101000001)
       ↑↑↑↑       Change bits
---------------------
       010100001)
Result : 161

For example, consider num = 321 and k = 4. The binary representation of 321 is 101000001. Inverting the 4 most significant bits results in 010100001, which is the binary representation of 161.

Idea to Solve the Problem

The solution involves a multi-step process:

  1. Compute a number r which has all bits set to 1 except for the least significant bit. This can be done by performing bitwise right shifts and OR operations.
  2. Find the value of the most significant set bit of r. This can be done by adding 1 to r and storing it in value.
  3. Iterate through the bits of value while modifying the result based on the bit values of num.

Standard Pseudocode

procedure changeKmostBit(num: integer, k: integer)
    if num <= 0 or k < 1
        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 + 1
    result = 0
    bit = k
    while value > 0
        if bit > 0
            if (value & num) == 0
                result = result + value
            bit = bit - 1
        else if (value & num) == value
            result = result + value
        value = value >> 1
    print("Number:", num, "K:", k)
    print("Result:", result)
end procedure

Algorithm Explanation

  1. Compute r by repeatedly performing bitwise right shifts and OR operations on num. This results in a value where the most significant bit is set to 1 and all other bits are set to 0.
  2. Calculate the value of the most significant set bit by adding 1 to r and storing it in value.
  3. Iterate through the bits of value. If bit is greater than 0, check if the corresponding bit in num is 0. If it is, add the value of the current bit to the result to flip it. Decrease the value of bit by 1. If bit is 0, check if the remaining bits of num match the corresponding bits in value (to preserve them) and add the value of the current bit to the result.
  4. Shift value to the right by 1 to process the next bit.

Code Solution

// C Program 
// Invert k most significant bits of number
#include <stdio.h>

void changeKmostBit(int num, int k)
{
	if (num <= 0 || k < 1)
	{
		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);
	// Find most significant set bit
	int value = (r + 1);
	int result = 0;
	int bit = k;
	while (value > 0)
	{
		if (bit > 0)
		{
			// When need to change bits
			if ((value & num) == 0)
			{
				result = result + value;
			}
			bit--;
		}
		else if ((value & num) == value)
		{
			// Collect the value of remaining active bits
			result = result + value;
		}
		value = value >> 1;
	}
	printf("\n Number : %d K : %d \n", num, k);
	// Display calculated result
	printf(" Result : %d\n", result);
}
int main()
{
	// Test A
	// num = 321  k = 4
	// 321 = (101000001)
	//        ↑↑↑↑       Change bits
	// ---------------------
	//        010100001)
	// Result : 161
	changeKmostBit(321, 4);
	// Test B 
	// (616) = (1001101000)  k = 6
	//          ↑↑↑↑↑↑      Change bits
	//          0110011000
	// ---------------------
	// Result : 408
	changeKmostBit(616, 6);
	// Test C
	// (54) = (110110)  k = 2
	//         ↑↑      Change bits
	//         000110
	// ---------------------
	// Result : 6
	changeKmostBit(54, 2);
	// Test D
	// 9    = (1001)  k = 4
	//         ↑↑↑↑   Change bits
	//         0110
	// ---------------------
	// Result : 6
	changeKmostBit(9, 4);
	// Test E
	// 7    = (111)   k = 1
	//         ↑      Change bits
	//         011
	// ---------------------
	// Result : 3
	changeKmostBit(7, 1);
	return 0;
}

Output

 Number : 321 K : 4
 Result : 161

 Number : 616 K : 6
 Result : 408

 Number : 54 K : 2
 Result : 6

 Number : 9 K : 4
 Result : 6

 Number : 7 K : 1
 Result : 3
/*
    Java Program
    Invert k most significant bits of number
*/
public class BitManipulation
{
	public void changeKmostBit(int num, int k)
	{
		if (num <= 0 || k < 1)
		{
			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);
		// Find most significant set bit
		int value = (r + 1);
		int result = 0;
		int bit = k;
		while (value > 0)
		{
			if (bit > 0)
			{
				// When need to change bits
				if ((value & num) == 0)
				{
					result = result + value;
				}
				bit--;
			}
			else if ((value & num) == value)
			{
				// Collect the value of remaining active bits
				result = result + value;
			}
			value = value >> 1;
		}
		System.out.println("\n Number : " + num + " K : " + k);
		// Display calculated result
		System.out.println(" Result : " + result);
	}
	public static void main(String[] args)
	{
		BitManipulation task = new BitManipulation();
		// Test A
		// num = 321  k = 4
		// 321 = (101000001)
		//        ↑↑↑↑       Change bits
		// ---------------------
		//        010100001)
		// Result : 161
		task.changeKmostBit(321, 4);
		// Test B 
		// (616) = (1001101000)  k = 6
		//          ↑↑↑↑↑↑      Change bits
		//          0110011000
		// ---------------------
		// Result : 408
		task.changeKmostBit(616, 6);
		// Test C
		// (54) = (110110)  k = 2
		//         ↑↑      Change bits
		//         000110
		// ---------------------
		// Result : 6
		task.changeKmostBit(54, 2);
		// Test D
		// 9    = (1001)  k = 4
		//         ↑↑↑↑   Change bits
		//         0110
		// ---------------------
		// Result : 6
		task.changeKmostBit(9, 4);
		// Test E
		// 7    = (111)   k = 1
		//         ↑      Change bits
		//         011
		// ---------------------
		// Result : 3
		task.changeKmostBit(7, 1);
	}
}

Output

 Number : 321 K : 4
 Result : 161

 Number : 616 K : 6
 Result : 408

 Number : 54 K : 2
 Result : 6

 Number : 9 K : 4
 Result : 6

 Number : 7 K : 1
 Result : 3
// Include header file
#include <iostream>
using namespace std;
/*
    C++ Program
    Invert k most significant bits of number
*/
class BitManipulation
{
	public: void changeKmostBit(int num, int k)
	{
		if (num <= 0 || k < 1)
		{
			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);
		// Find most significant set bit
		int value = (r + 1);
		int result = 0;
		int bit = k;
		while (value > 0)
		{
			if (bit > 0)
			{
				// When need to change bits
				if ((value &num) == 0)
				{
					result = result + value;
				}
				bit--;
			}
			else if ((value &num) == value)
			{
				// Collect the value of remaining active bits
				result = result + value;
			}
			value = value >> 1;
		}
		cout << "\n Number : " 
             << num << " K : " 
             << k << endl;
		// Display calculated result
		cout << " Result : " 
             << result << endl;
	}
};
int main()
{
	BitManipulation *task = new BitManipulation();
	// Test A
	// num = 321  k = 4
	// 321 = (101000001)
	//        ↑↑↑↑       Change bits
	// ---------------------
	//        010100001)
	// Result : 161
	task->changeKmostBit(321, 4);
	// Test B 
	// (616) = (1001101000)  k = 6
	//          ↑↑↑↑↑↑      Change bits
	//          0110011000
	// ---------------------
	// Result : 408
	task->changeKmostBit(616, 6);
	// Test C
	// (54) = (110110)  k = 2
	//         ↑↑      Change bits
	//         000110
	// ---------------------
	// Result : 6
	task->changeKmostBit(54, 2);
	// Test D
	// 9    = (1001)  k = 4
	//         ↑↑↑↑   Change bits
	//         0110
	// ---------------------
	// Result : 6
	task->changeKmostBit(9, 4);
	// Test E
	// 7    = (111)   k = 1
	//         ↑      Change bits
	//         011
	// ---------------------
	// Result : 3
	task->changeKmostBit(7, 1);
	return 0;
}

Output

 Number : 321 K : 4
 Result : 161

 Number : 616 K : 6
 Result : 408

 Number : 54 K : 2
 Result : 6

 Number : 9 K : 4
 Result : 6

 Number : 7 K : 1
 Result : 3
// Include namespace system
using System;
/*
    Csharp Program
    Invert k most significant bits of number
*/
public class BitManipulation
{
	public void changeKmostBit(int num, int k)
	{
		if (num <= 0 || k < 1)
		{
			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);
		// Find most significant set bit
		int value = (r + 1);
		int result = 0;
		int bit = k;
		while (value > 0)
		{
			if (bit > 0)
			{
				// When need to change bits
				if ((value & num) == 0)
				{
					result = result + value;
				}
				bit--;
			}
			else if ((value & num) == value)
			{
				// Collect the value of remaining active bits
				result = result + value;
			}
			value = value >> 1;
		}
		Console.WriteLine("\n Number : " + num + " K : " + k);
		// Display calculated result
		Console.WriteLine(" Result : " + result);
	}
	public static void Main(String[] args)
	{
		BitManipulation task = new BitManipulation();
		// Test A
		// num = 321  k = 4
		// 321 = (101000001)
		//        ↑↑↑↑       Change bits
		// ---------------------
		//        010100001)
		// Result : 161
		task.changeKmostBit(321, 4);
		// Test B 
		// (616) = (1001101000)  k = 6
		//          ↑↑↑↑↑↑      Change bits
		//          0110011000
		// ---------------------
		// Result : 408
		task.changeKmostBit(616, 6);
		// Test C
		// (54) = (110110)  k = 2
		//         ↑↑      Change bits
		//         000110
		// ---------------------
		// Result : 6
		task.changeKmostBit(54, 2);
		// Test D
		// 9    = (1001)  k = 4
		//         ↑↑↑↑   Change bits
		//         0110
		// ---------------------
		// Result : 6
		task.changeKmostBit(9, 4);
		// Test E
		// 7    = (111)   k = 1
		//         ↑      Change bits
		//         011
		// ---------------------
		// Result : 3
		task.changeKmostBit(7, 1);
	}
}

Output

 Number : 321 K : 4
 Result : 161

 Number : 616 K : 6
 Result : 408

 Number : 54 K : 2
 Result : 6

 Number : 9 K : 4
 Result : 6

 Number : 7 K : 1
 Result : 3
package main
import "fmt"
/*
    Go Program
    Invert k most significant bits of number
*/
type BitManipulation struct {}
func getBitManipulation() * BitManipulation {
	var me *BitManipulation = &BitManipulation {}
	return me
}
func(this BitManipulation) changeKmostBit(num, k int) {
	if num <= 0 || k < 1 {
		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)
	// Find most significant set bit
	var value int = (r + 1)
	var result int = 0
	var bit int = k
	for (value > 0) {
		if bit > 0 {
			// When need to change bits
			if (value & num) == 0 {
				result = result + value
			}
			bit--
		} else if (value & num) == value {
			// Collect the value of remaining active bits
			result = result + value
		}
		value = value >> 1
	}
	fmt.Println("\n Number : ", num, " K : ", k)
	// Display calculated result
	fmt.Println(" Result : ", result)
}
func main() {
	var task * BitManipulation = getBitManipulation()
	// Test A
	// num = 321  k = 4
	// 321 = (101000001)
	//        ↑↑↑↑       Change bits
	// ---------------------
	//        010100001)
	// Result : 161
	task.changeKmostBit(321, 4)
	// Test B 
	// (616) = (1001101000)  k = 6
	//          ↑↑↑↑↑↑      Change bits
	//          0110011000
	// ---------------------
	// Result : 408
	task.changeKmostBit(616, 6)
	// Test C
	// (54) = (110110)  k = 2
	//         ↑↑      Change bits
	//         000110
	// ---------------------
	// Result : 6
	task.changeKmostBit(54, 2)
	// Test D
	// 9    = (1001)  k = 4
	//         ↑↑↑↑   Change bits
	//         0110
	// ---------------------
	// Result : 6
	task.changeKmostBit(9, 4)
	// Test E
	// 7    = (111)   k = 1
	//         ↑      Change bits
	//         011
	// ---------------------
	// Result : 3
	task.changeKmostBit(7, 1)
}

Output

 Number : 321 K : 4
 Result : 161

 Number : 616 K : 6
 Result : 408

 Number : 54 K : 2
 Result : 6

 Number : 9 K : 4
 Result : 6

 Number : 7 K : 1
 Result : 3
<?php
/*
    Php Program
    Invert k most significant bits of number
*/
class BitManipulation
{
	public	function changeKmostBit($num, $k)
	{
		if ($num <= 0 || $k < 1)
		{
			return;
		}
		$r = $num >> 1;
		$r = $r | ($r >> 1);
		$r = $r | ($r >> 2);
		$r = $r | ($r >> 4);
		$r = $r | ($r >> 8);
		$r = $r | ($r >> 16);
		// Find most significant set bit
		$value = ($r + 1);
		$result = 0;
		$bit = $k;
		while ($value > 0)
		{
			if ($bit > 0)
			{
				// When need to change bits
				if (($value & $num) == 0)
				{
					$result = $result + $value;
				}
				$bit--;
			}
			else if (($value & $num) == $value)
			{
				// Collect the value of remaining active bits
				$result = $result + $value;
			}
			$value = $value >> 1;
		}
		echo("\n Number : ".$num.
			" K : ".$k.
			"\n");
		// Display calculated result
		echo(" Result : ".$result.
			"\n");
	}
}

function main()
{
	$task = new BitManipulation();
	// Test A
	// num = 321  k = 4
	// 321 = (101000001)
	//        ↑↑↑↑       Change bits
	// ---------------------
	//        010100001)
	// Result : 161
	$task->changeKmostBit(321, 4);
	// Test B 
	// (616) = (1001101000)  k = 6
	//          ↑↑↑↑↑↑      Change bits
	//          0110011000
	// ---------------------
	// Result : 408
	$task->changeKmostBit(616, 6);
	// Test C
	// (54) = (110110)  k = 2
	//         ↑↑      Change bits
	//         000110
	// ---------------------
	// Result : 6
	$task->changeKmostBit(54, 2);
	// Test D
	// 9    = (1001)  k = 4
	//         ↑↑↑↑   Change bits
	//         0110
	// ---------------------
	// Result : 6
	$task->changeKmostBit(9, 4);
	// Test E
	// 7    = (111)   k = 1
	//         ↑      Change bits
	//         011
	// ---------------------
	// Result : 3
	$task->changeKmostBit(7, 1);
}
main();

Output

 Number : 321 K : 4
 Result : 161

 Number : 616 K : 6
 Result : 408

 Number : 54 K : 2
 Result : 6

 Number : 9 K : 4
 Result : 6

 Number : 7 K : 1
 Result : 3
/*
    Node JS Program
    Invert k most significant bits of number
*/
class BitManipulation
{
	changeKmostBit(num, k)
	{
		if (num <= 0 || k < 1)
		{
			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);
		// Find most significant set bit
		var value = (r + 1);
		var result = 0;
		var bit = k;
		while (value > 0)
		{
			if (bit > 0)
			{
				// When need to change bits
				if ((value & num) == 0)
				{
					result = result + value;
				}
				bit--;
			}
			else if ((value & num) == value)
			{
				// Collect the value of remaining active bits
				result = result + value;
			}
			value = value >> 1;
		}
		console.log("\n Number : " + num + " K : " + k);
		// Display calculated result
		console.log(" Result : " + result);
	}
}

function main()
{
	var task = new BitManipulation();
	// Test A
	// num = 321  k = 4
	// 321 = (101000001)
	//        ↑↑↑↑       Change bits
	// ---------------------
	//        010100001)
	// Result : 161
	task.changeKmostBit(321, 4);
	// Test B 
	// (616) = (1001101000)  k = 6
	//          ↑↑↑↑↑↑      Change bits
	//          0110011000
	// ---------------------
	// Result : 408
	task.changeKmostBit(616, 6);
	// Test C
	// (54) = (110110)  k = 2
	//         ↑↑      Change bits
	//         000110
	// ---------------------
	// Result : 6
	task.changeKmostBit(54, 2);
	// Test D
	// 9    = (1001)  k = 4
	//         ↑↑↑↑   Change bits
	//         0110
	// ---------------------
	// Result : 6
	task.changeKmostBit(9, 4);
	// Test E
	// 7    = (111)   k = 1
	//         ↑      Change bits
	//         011
	// ---------------------
	// Result : 3
	task.changeKmostBit(7, 1);
}
main();

Output

 Number : 321 K : 4
 Result : 161

 Number : 616 K : 6
 Result : 408

 Number : 54 K : 2
 Result : 6

 Number : 9 K : 4
 Result : 6

 Number : 7 K : 1
 Result : 3
#    Python 3 Program
#    Invert k most significant bits of number
class BitManipulation :
	def changeKmostBit(self, num, k) :
		if (num <= 0 or k < 1) :
			return
		
		r = num >> 1
		r = r | (r >> 1)
		r = r | (r >> 2)
		r = r | (r >> 4)
		r = r | (r >> 8)
		r = r | (r >> 16)
		#  Find most significant set bit
		value = (r + 1)
		result = 0
		bit = k
		while (value > 0) :
			if (bit > 0) :
				#  When need to change bits
				if ((value & num) == 0) :
					result = result + value
				
				bit -= 1
			elif ((value & num) == value) :
				#  Collect the value of remaining active bits
				result = result + value
			
			value = value >> 1
		
		print("\n Number : ", num ," K : ", k)
		#  Display calculated result
		print(" Result : ", result)
	

def main() :
	task = BitManipulation()
	#  Test A
	#  num = 321  k = 4
	#  321 = (101000001)
	#         ↑↑↑↑       Change bits
	#  ---------------------
	#         010100001)
	#  Result : 161
	task.changeKmostBit(321, 4)
	#  Test B 
	#  (616) = (1001101000)  k = 6
	#           ↑↑↑↑↑↑      Change bits
	#           0110011000
	#  ---------------------
	#  Result : 408
	task.changeKmostBit(616, 6)
	#  Test C
	#  (54) = (110110)  k = 2
	#          ↑↑      Change bits
	#          000110
	#  ---------------------
	#  Result : 6
	task.changeKmostBit(54, 2)
	#  Test D
	#  9    = (1001)  k = 4
	#          ↑↑↑↑   Change bits
	#          0110
	#  ---------------------
	#  Result : 6
	task.changeKmostBit(9, 4)
	#  Test E
	#  7    = (111)   k = 1
	#          ↑      Change bits
	#          011
	#  ---------------------
	#  Result : 3
	task.changeKmostBit(7, 1)

if __name__ == "__main__": main()

Output

 Number :  321  K :  4
 Result :  161

 Number :  616  K :  6
 Result :  408

 Number :  54  K :  2
 Result :  6

 Number :  9  K :  4
 Result :  6

 Number :  7  K :  1
 Result :  3
#    Ruby Program
#    Invert k most significant bits of number
class BitManipulation 
	def changeKmostBit(num, k) 
		if (num <= 0 || k < 1) 
			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)
		#  Find most significant set bit
		value = (r + 1)
		result = 0
		bit = k
		while (value > 0) 
			if (bit > 0) 
				#  When need to change bits
				if ((value & num) == 0) 
					result = result + value
				end

				bit -= 1
			elsif ((value & num) == value) 
				#  Collect the value of remaining active bits
				result = result + value
			end

			value = value >> 1
		end

		print("\n Number : ", num ," K : ", k, "\n")
		#  Display calculated result
		print(" Result : ", result, "\n")
	end

end

def main() 
	task = BitManipulation.new()
	#  Test A
	#  num = 321  k = 4
	#  321 = (101000001)
	#         ↑↑↑↑       Change bits
	#  ---------------------
	#         010100001)
	#  Result : 161
	task.changeKmostBit(321, 4)
	#  Test B 
	#  (616) = (1001101000)  k = 6
	#           ↑↑↑↑↑↑      Change bits
	#           0110011000
	#  ---------------------
	#  Result : 408
	task.changeKmostBit(616, 6)
	#  Test C
	#  (54) = (110110)  k = 2
	#          ↑↑      Change bits
	#          000110
	#  ---------------------
	#  Result : 6
	task.changeKmostBit(54, 2)
	#  Test D
	#  9    = (1001)  k = 4
	#          ↑↑↑↑   Change bits
	#          0110
	#  ---------------------
	#  Result : 6
	task.changeKmostBit(9, 4)
	#  Test E
	#  7    = (111)   k = 1
	#          ↑      Change bits
	#          011
	#  ---------------------
	#  Result : 3
	task.changeKmostBit(7, 1)
end

main()

Output

 Number : 321 K : 4
 Result : 161

 Number : 616 K : 6
 Result : 408

 Number : 54 K : 2
 Result : 6

 Number : 9 K : 4
 Result : 6

 Number : 7 K : 1
 Result : 3
/*
    Scala Program
    Invert k most significant bits of number
*/
class BitManipulation()
{
	def changeKmostBit(num: Int, k: Int): Unit = {
		if (num <= 0 || k < 1)
		{
			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);
		// Find most significant set bit
		var value: Int = (r + 1);
		var result: Int = 0;
		var bit: Int = k;
		while (value > 0)
		{
			if (bit > 0)
			{
				// When need to change bits
				if ((value & num) == 0)
				{
					result = result + value;
				}
				bit -= 1;
			}
			else if ((value & num) == value)
			{
				// Collect the value of remaining active bits
				result = result + value;
			}
			value = value >> 1;
		}
		println("\n Number : " + num + " K : " + k);
		// Display calculated result
		println(" Result : " + result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: BitManipulation = new BitManipulation();
		// Test A
		// num = 321  k = 4
		// 321 = (101000001)
		//        ↑↑↑↑       Change bits
		// ---------------------
		//        010100001)
		// Result : 161
		task.changeKmostBit(321, 4);
		// Test B 
		// (616) = (1001101000)  k = 6
		//          ↑↑↑↑↑↑      Change bits
		//          0110011000
		// ---------------------
		// Result : 408
		task.changeKmostBit(616, 6);
		// Test C
		// (54) = (110110)  k = 2
		//         ↑↑      Change bits
		//         000110
		// ---------------------
		// Result : 6
		task.changeKmostBit(54, 2);
		// Test D
		// 9    = (1001)  k = 4
		//         ↑↑↑↑   Change bits
		//         0110
		// ---------------------
		// Result : 6
		task.changeKmostBit(9, 4);
		// Test E
		// 7    = (111)   k = 1
		//         ↑      Change bits
		//         011
		// ---------------------
		// Result : 3
		task.changeKmostBit(7, 1);
	}
}

Output

 Number : 321 K : 4
 Result : 161

 Number : 616 K : 6
 Result : 408

 Number : 54 K : 2
 Result : 6

 Number : 9 K : 4
 Result : 6

 Number : 7 K : 1
 Result : 3
/*
    Swift 4 Program
    Invert k most significant bits of number
*/
class BitManipulation
{
	func changeKmostBit(_ num: Int, _ k: Int)
	{
		if (num <= 0 || k < 1)
		{
			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);
		// Find most significant set bit
		var value: Int = (r + 1);
		var result: Int = 0;
		var bit: Int = k;
		while (value > 0)
		{
			if (bit > 0)
			{
				// When need to change bits
				if ((value & num) == 0)
				{
					result = result + value;
				}
				bit -= 1;
			}
			else if ((value & num) == value)
			{
				// Collect the value of remaining active bits
				result = result + value;
			}
			value = value >> 1;
		}
		print("\n Number : ", num ," K : ", k);
		// Display calculated result
		print(" Result : ", result);
	}
}
func main()
{
	let task: BitManipulation = BitManipulation();
	// Test A
	// num = 321  k = 4
	// 321 = (101000001)
	//        ↑↑↑↑       Change bits
	// ---------------------
	//        010100001)
	// Result : 161
	task.changeKmostBit(321, 4);
	// Test B 
	// (616) = (1001101000)  k = 6
	//          ↑↑↑↑↑↑      Change bits
	//          0110011000
	// ---------------------
	// Result : 408
	task.changeKmostBit(616, 6);
	// Test C
	// (54) = (110110)  k = 2
	//         ↑↑      Change bits
	//         000110
	// ---------------------
	// Result : 6
	task.changeKmostBit(54, 2);
	// Test D
	// 9    = (1001)  k = 4
	//         ↑↑↑↑   Change bits
	//         0110
	// ---------------------
	// Result : 6
	task.changeKmostBit(9, 4);
	// Test E
	// 7    = (111)   k = 1
	//         ↑      Change bits
	//         011
	// ---------------------
	// Result : 3
	task.changeKmostBit(7, 1);
}
main();

Output

 Number :  321  K :  4
 Result :  161

 Number :  616  K :  6
 Result :  408

 Number :  54  K :  2
 Result :  6

 Number :  9  K :  4
 Result :  6

 Number :  7  K :  1
 Result :  3
/*
    Kotlin Program
    Invert k most significant bits of number
*/
class BitManipulation
{
	fun changeKmostBit(num: Int, k: Int): Unit
	{
		if (num <= 0 || k < 1)
		{
			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);
		// Find most significant set bit
		var value: Int = (r + 1);
		var result: Int = 0;
		var bit: Int = k;
		while (value > 0)
		{
			if (bit > 0)
			{
				// When need to change bits
				if ((value and num) == 0)
				{
					result = result + value;
				}
				bit -= 1;
			}
			else if ((value and num) == value)
			{
				// Collect the value of remaining active bits
				result = result + value;
			}
			value = value shr 1;
		}
		println("\n Number : " + num + " K : " + k);
		// Display calculated result
		println(" Result : " + result);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: BitManipulation = BitManipulation();
	// Test A
	// num = 321  k = 4
	// 321 = (101000001)
	//        ↑↑↑↑       Change bits
	// ---------------------
	//        010100001)
	// Result : 161
	task.changeKmostBit(321, 4);
	// Test B 
	// (616) = (1001101000)  k = 6
	//          ↑↑↑↑↑↑      Change bits
	//          0110011000
	// ---------------------
	// Result : 408
	task.changeKmostBit(616, 6);
	// Test C
	// (54) = (110110)  k = 2
	//         ↑↑      Change bits
	//         000110
	// ---------------------
	// Result : 6
	task.changeKmostBit(54, 2);
	// Test D
	// 9    = (1001)  k = 4
	//         ↑↑↑↑   Change bits
	//         0110
	// ---------------------
	// Result : 6
	task.changeKmostBit(9, 4);
	// Test E
	// 7    = (111)   k = 1
	//         ↑      Change bits
	//         011
	// ---------------------
	// Result : 3
	task.changeKmostBit(7, 1);
}

Output

 Number : 321 K : 4
 Result : 161

 Number : 616 K : 6
 Result : 408

 Number : 54 K : 2
 Result : 6

 Number : 9 K : 4
 Result : 6

 Number : 7 K : 1
 Result : 3

Resultant Output Explanation

When the code is executed with the provided examples, the output shows the numbers, the value of k, and the resultant number after inverting the k most significant bits.

For instance, when num = 321 and k = 4, the output is:

Number: 321 K: 4
    Result: 161

This indicates that after inverting the 4 most significant bits of 321, the result is 161.

Time Complexity

The time complexity of this solution depends mainly on the number of bits in the given integer. The loop that iterates through the bits of value runs a constant number of times (equal to the number of bits in an integer, usually 32 or 64), making the overall time complexity 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