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:
- Compute a number
r
which has all bits set to1
except for the least significant bit. This can be done by performing bitwise right shifts and OR operations. - Find the value of the most significant set bit of
r
. This can be done by adding1
tor
and storing it invalue
. - Iterate through the bits of
value
while modifying the result based on the bit values ofnum
.
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
- Compute
r
by repeatedly performing bitwise right shifts and OR operations onnum
. This results in a value where the most significant bit is set to1
and all other bits are set to0
. - Calculate the value of the most significant set bit by adding
1
tor
and storing it invalue
. - Iterate through the bits of
value
. Ifbit
is greater than0
, check if the corresponding bit innum
is0
. If it is, add the value of the current bit to theresult
to flip it. Decrease the value ofbit
by1
. Ifbit
is0
, check if the remaining bits ofnum
match the corresponding bits invalue
(to preserve them) and add the value of the current bit to theresult
. - Shift
value
to the right by1
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).
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