Toggle the last n bits
In computer science, bitwise operations are commonly used to manipulate individual bits of data efficiently. One common task is toggling or flipping the last n bits of a given number. The objective is to change the state of the last n bits of a binary number, where n is a positive integer provided by the user. In this article, we will explore this problem, its applications, and present an algorithm to achieve the desired task.
Problem Statement
Given a decimal number num
and a positive integer n
, the task is to toggle the last
n
bits of the binary representation of num
. In other words, we need to change all the
0s to 1s and vice versa in the last n
bits of the binary representation.
Example Let's take an example to understand the problem better:
Input:
num = 15
(Binary representation: 1111)n = 3
Output:
- The binary representation of 15 is 1111. We need to toggle the last 3 bits (rightmost bits).
- After toggling the last 3 bits, the binary representation becomes 1000, which is equal to decimal 8.
Pseudocode
The following pseudocode represents the algorithm to toggle the last n
bits of a given number
num
:
changeLNBits(num, n):
Set mask = (1 << n) - 1
Set result = num XOR mask
Return result
Explanation of the Algorithm
- We start by defining the function
changeLNBits
, which takes two parameters:num
(the given decimal number) andn
(the number of bits to toggle from the right). - We create a mask to toggle the last
n
bits. The mask is created by left-shifting 1 byn
bits and then subtracting 1 from the result. This operation sets the rightmostn
bits of the mask to 1 and leaves all other bits as 0. - We apply the XOR operation between
num
and the mask. The XOR operation sets the bits to 1 where there is a difference between the bits ofnum
and the mask. In other words, it toggles the bits where the mask has 1s. - The result of the XOR operation is the number with the last
n
bits toggled, which we store in the variableresult
. - Finally, we return the
result
.
Code Example
// C Program
// Toggle the last n bits
#include <stdio.h>
// Change last n bits of a given number
void changeLNBits(int num, int n)
{
// Display given number
printf("\n Number : %d", num);
// Change last n bit
int result = num ^ (1 << n) - 1;
// Display calculated result
printf("\n After change last %d bits : %d\n", n, result);
}
int main()
{
// (15) 1111 => 1000 n=3
changeLNBits(15, 3);
// (100) 1100100 => 1111011 n = 5
changeLNBits(100, 5);
// (10) 00001010 => 11110101 (1s) => 11110110 (2s)
// (-10) 11110110 => 11110001 (n = 3)
changeLNBits(-10, 3);
return 0;
}
Output
Number : 15
After change last 3 bits : 8
Number : 100
After change last 5 bits : 123
Number : -10
After change last 3 bits : -15
/*
Java Program for
Toggle the last n bits
*/
class ChangeBits
{
// Change last n bits of a given number
public void changeLNBits(int num, int n)
{
// Display given number
System.out.print("\n Number : " + num);
// Change last n bit
int result = num ^ (1 << n) - 1;
// Display calculated result
System.out.print("\n After change last " + n + " bits : " + result + "\n");
}
public static void main(String[] args)
{
ChangeBits task = new ChangeBits();
// (15) 1111 => 1000 n=3
task.changeLNBits(15, 3);
// (100) 1100100 => 1111011 n = 5
task.changeLNBits(100, 5);
// (10) 00001010 => 11110101 (1s) => 11110110 (2s)
// (-10) 11110110 => 11110001 (n = 3)
task.changeLNBits(-10, 3);
}
}
Output
Number : 15
After change last 3 bits : 8
Number : 100
After change last 5 bits : 123
Number : -10
After change last 3 bits : -15
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Toggle the last n bits
*/
class ChangeBits
{
public:
// Change last n bits of a given number
void changeLNBits(int num, int n)
{
// Display given number
cout << "\n Number : " << num;
// Change last n bit
int result = num ^ (1 << n) - 1;
// Display calculated result
cout << "\n After change last " << n << " bits : " << result << "\n";
}
};
int main()
{
ChangeBits task = ChangeBits();
// (15) 1111 => 1000 n=3
task.changeLNBits(15, 3);
// (100) 1100100 => 1111011 n = 5
task.changeLNBits(100, 5);
// (10) 00001010 => 11110101 (1s) => 11110110 (2s)
// (-10) 11110110 => 11110001 (n = 3)
task.changeLNBits(-10, 3);
return 0;
}
Output
Number : 15
After change last 3 bits : 8
Number : 100
After change last 5 bits : 123
Number : -10
After change last 3 bits : -15
// Include namespace system
using System;
/*
C# Program for
Toggle the last n bits
*/
public class ChangeBits
{
// Change last n bits of a given number
public void changeLNBits(int num, int n)
{
// Display given number
Console.Write("\n Number : " + num);
// Change last n bit
int result = num ^ (1 << n) - 1;
// Display calculated result
Console.Write("\n After change last " + n + " bits : " + result + "\n");
}
public static void Main(String[] args)
{
ChangeBits task = new ChangeBits();
// (15) 1111 => 1000 n=3
task.changeLNBits(15, 3);
// (100) 1100100 => 1111011 n = 5
task.changeLNBits(100, 5);
// (10) 00001010 => 11110101 (1s) => 11110110 (2s)
// (-10) 11110110 => 11110001 (n = 3)
task.changeLNBits(-10, 3);
}
}
Output
Number : 15
After change last 3 bits : 8
Number : 100
After change last 5 bits : 123
Number : -10
After change last 3 bits : -15
<?php
/*
Php Program for
Toggle the last n bits
*/
class ChangeBits
{
// Change last n bits of a given number
public function changeLNBits($num, $n)
{
// Display given number
echo "\n Number : ". $num;
// Change last n bit
$result = $num ^ (1 << $n) - 1;
// Display calculated result
echo "\n After change last ". $n ." bits : ". $result ."\n";
}
}
function main()
{
$task = new ChangeBits();
// (15) 1111 => 1000 n=3
$task->changeLNBits(15, 3);
// (100) 1100100 => 1111011 n = 5
$task->changeLNBits(100, 5);
// (10) 00001010 => 11110101 (1s) => 11110110 (2s)
// (-10) 11110110 => 11110001 (n = 3)
$task->changeLNBits(-10, 3);
}
main();
Output
Number : 15
After change last 3 bits : 8
Number : 100
After change last 5 bits : 123
Number : -10
After change last 3 bits : -15
/*
Node Js Program for
Toggle the last n bits
*/
class ChangeBits
{
// Change last n bits of a given number
changeLNBits(num, n)
{
// Display given number
process.stdout.write("\n Number : " + num);
// Change last n bit
var result = num ^ (1 << n) - 1;
// Display calculated result
process.stdout.write("\n After change last " + n + " bits : " + result + "\n");
}
}
function main()
{
var task = new ChangeBits();
// (15) 1111 => 1000 n=3
task.changeLNBits(15, 3);
// (100) 1100100 => 1111011 n = 5
task.changeLNBits(100, 5);
// (10) 00001010 => 11110101 (1s) => 11110110 (2s)
// (-10) 11110110 => 11110001 (n = 3)
task.changeLNBits(-10, 3);
}
main();
Output
Number : 15
After change last 3 bits : 8
Number : 100
After change last 5 bits : 123
Number : -10
After change last 3 bits : -15
# Python 3 Program for
# Toggle the last n bits
class ChangeBits :
# Change last n bits of a given number
def changeLNBits(self, num, n) :
# Display given number
print("\n Number : ", num, end = "")
# Change last n bit
result = num ^ (1 << n) - 1
# Display calculated result
print("\n After change last ", n ," bits : ", result )
def main() :
task = ChangeBits()
# (15) 1111 => 1000 n=3
task.changeLNBits(15, 3)
# (100) 1100100 => 1111011 n = 5
task.changeLNBits(100, 5)
# (10) 00001010 => 11110101 (1s) => 11110110 (2s)
# (-10) 11110110 => 11110001 (n = 3)
task.changeLNBits(-10, 3)
if __name__ == "__main__": main()
Output
Number : 15
After change last 3 bits : 8
Number : 100
After change last 5 bits : 123
Number : -10
After change last 3 bits : -15
# Ruby Program for
# Toggle the last n bits
class ChangeBits
# Change last n bits of a given number
def changeLNBits(num, n)
# Display given number
print("\n Number : ", num)
# Change last n bit
result = num ^ (1 << n) - 1
# Display calculated result
print("\n After change last ", n ," bits : ", result ,"\n")
end
end
def main()
task = ChangeBits.new()
# (15) 1111 => 1000 n=3
task.changeLNBits(15, 3)
# (100) 1100100 => 1111011 n = 5
task.changeLNBits(100, 5)
# (10) 00001010 => 11110101 (1s) => 11110110 (2s)
# (-10) 11110110 => 11110001 (n = 3)
task.changeLNBits(-10, 3)
end
main()
Output
Number : 15
After change last 3 bits : 8
Number : 100
After change last 5 bits : 123
Number : -10
After change last 3 bits : -15
/*
Scala Program for
Toggle the last n bits
*/
class ChangeBits
{
// Change last n bits of a given number
def changeLNBits(num: Int, n: Int): Unit = {
// Display given number
print("\n Number : " + num);
// Change last n bit
var result: Int = num ^ (1 << n) - 1;
// Display calculated result
print("\n After change last " + n + " bits : " + result + "\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: ChangeBits = new ChangeBits();
// (15) 1111 => 1000 n=3
task.changeLNBits(15, 3);
// (100) 1100100 => 1111011 n = 5
task.changeLNBits(100, 5);
// (10) 00001010 => 11110101 (1s) => 11110110 (2s)
// (-10) 11110110 => 11110001 (n = 3)
task.changeLNBits(-10, 3);
}
}
Output
Number : 15
After change last 3 bits : 8
Number : 100
After change last 5 bits : 123
Number : -10
After change last 3 bits : -15
/*
Swift 4 Program for
Toggle the last n bits
*/
class ChangeBits
{
// Change last n bits of a given number
func changeLNBits(_ num: Int, _ n: Int)
{
// Display given number
print("\n Number : ", num, terminator: "");
// Change last n bit
let result: Int = num ^ ((1 << n) - 1);
// Display calculated result
print("\n After change last ", n ," bits : ", result );
}
}
func main()
{
let task: ChangeBits = ChangeBits();
// (15) 1111 => 1000 n=3
task.changeLNBits(15, 3);
// (100) 1100100 => 1111011 n = 5
task.changeLNBits(100, 5);
// (10) 00001010 => 11110101 (1s) => 11110110 (2s)
// (-10) 11110110 => 11110001 (n = 3)
task.changeLNBits(-10, 3);
}
main();
Output
Number : 15
After change last 3 bits : 8
Number : 100
After change last 5 bits : 123
Number : -10
After change last 3 bits : -15
/*
Kotlin Program for
Toggle the last n bits
*/
class ChangeBits
{
// Change last n bits of a given number
fun changeLNBits(num: Int, n: Int): Unit
{
// Display given number
print("\n Number : " + num);
// Change last n bit
var result: Int = num xor (1 shl n) - 1;
// Display calculated result
print("\n After change last " + n + " bits : " + result + "\n");
}
}
fun main(args: Array < String > ): Unit
{
var task: ChangeBits = ChangeBits();
// (15) 1111 => 1000 n=3
task.changeLNBits(15, 3);
// (100) 1100100 => 1111011 n = 5
task.changeLNBits(100, 5);
// (10) 00001010 => 11110101 (1s) => 11110110 (2s)
// (-10) 11110110 => 11110001 (n = 3)
task.changeLNBits(-10, 3);
}
Output
Number : 15
After change last 3 bits : 8
Number : 100
After change last 5 bits : 123
Number : -10
After change last 3 bits : -15
Output Explanation
Let's now understand the output of the provided code:
1. Input: num = 15, n = 3
- The binary representation of 15 is 1111. The last 3 bits are
111
, which need to be toggled. - The mask for
n = 3
is111
(in binary). Performing the XOR operation withnum
, we get1111 XOR 111 = 1000
. - The decimal equivalent of
1000
is8
. - Therefore, the output is
After change last 3 bits : 8
.
2. Input: num = 100, n = 5
- The binary representation of 100 is 1100100. The last 5 bits are
100
, which need to be toggled. - The mask for
n = 5
is11111
(in binary). Performing the XOR operation withnum
, we get1100100 XOR 11111 = 1111011
. - The decimal equivalent of
1111011
is123
. - Therefore, the output is
After change last 5 bits : 123
.
3. Input: num = -10, n = 3
- The binary representation of -10 (in 8 bits) is
11110110
. The last 3 bits are110
, which need to be toggled. - The mask for
n = 3
is111
(in binary). Performing the XOR operation withnum
, we get11110110 XOR 111 = 11110001
. - The decimal equivalent of
11110001
is-15
. - Therefore, the output is
After change last 3 bits : -15
.
Time Complexity Analysis
The time complexity of the provided algorithm is constant, O(1), which means it does not depend on the size of
the input. The reason behind this is that the algorithm performs a fixed number of operations (calculating the
mask and performing the XOR operation), regardless of the input values. Therefore, it offers an efficient
solution for toggling the last n
bits of a given number.
Finally, the task of toggling the last n
bits of a given number can be efficiently achieved
using bitwise operations. By following the provided algorithm, we can quickly perform this operation in constant
time, making it a practical solution for various applications that require bit manipulation.
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