Skip to main content

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

  1. We start by defining the function changeLNBits, which takes two parameters: num (the given decimal number) and n (the number of bits to toggle from the right).
  2. We create a mask to toggle the last n bits. The mask is created by left-shifting 1 by n bits and then subtracting 1 from the result. This operation sets the rightmost n bits of the mask to 1 and leaves all other bits as 0.
  3. 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 of num and the mask. In other words, it toggles the bits where the mask has 1s.
  4. The result of the XOR operation is the number with the last n bits toggled, which we store in the variable result.
  5. 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 is 111 (in binary). Performing the XOR operation with num, we get 1111 XOR 111 = 1000.
  • The decimal equivalent of 1000 is 8.
  • 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 is 11111 (in binary). Performing the XOR operation with num, we get 1100100 XOR 11111 = 1111011.
  • The decimal equivalent of 1111011 is 123.
  • 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 are 110, which need to be toggled.
  • The mask for n = 3 is 111 (in binary). Performing the XOR operation with num, we get 11110110 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.

Last updated on by Kalkicode




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