Toggle bits in the given range
Given a non-negative number n and two values l and r. The problem is to toggle the bits in the range l to r in the binary representation of n, i.e., to toggle bits from the lth least significant bit bit to the rth least significant bit (the rightmost bit as counted as first bit). A toggle operation flips a bit 0 to 1 and a bit 1 to 0.
Constraint: 1 <= l <= r <= number of bits in the binary representation of n.
Examples:
Input: n = 17, l = 1, r = 3
Output: 22
Explanation: (17)10 = (10001)2
(22)10 = (10110)2
The bits in the range 1 to 3 in the binary representation of 17 are toggled.Input: n = 50, l = 2, r = 5
Output: 44Explanation: (50)10 = (110010)2
(44)10 = (101100)2
The bits in the range 2 to 5 in the binary representation of 50 are toggled.
Approach: Following are the steps:
- Calculate num as = ((1 << r) – 1) ^ ((1 << (l-1)) – 1) or as ((1 <<r)-l). This will produce a number num having r number of bits and bits in the range l to r (from rightmost end in binary representation) are the only set bits.
- Now, perform n = n ^ num. This will toggle the bits in the range l to r in n.
// C++ implementation to toggle bits in
// the given range
#include <bits/stdc++.h>
using namespace std;
// function to toggle bits in the given range
unsigned int toggleBitsFromLToR(unsigned int n,
unsigned int l,
unsigned int r)
{
// calculating a number 'num' having 'r'
// number of bits and bits in the range l
// to r are the only set bits
int num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1);
// toggle bits in the range l to r in 'n'
// and return the number
// Besides this, we can calculate num as: num=(1<<r)-l .
return (n ^ num);
}
// Driver program to test above
int main()
{
unsigned int n = 17;
unsigned int l = 1, r = 3;
cout << toggleBitsFromLToR(n, l, r);
return 0;
}
// Java implementation to toggle bits in
// the given range
import java.io.*;
class GFG {
// Function to toggle bits in the given range
static int toggleBitsFromLToR(int n, int l, int r)
{
// calculating a number 'num' having 'r'
// number of bits and bits in the range l
// to r are the only set bits
int num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1);
// toggle bits in the range l to r in 'n'
// and return the number
// Besides this, we can calculate num as:
// num=(1<<r)-l .
return (n ^ num);
}
// driver program
public static void main(String[] args)
{
int n = 50;
int l = 2, r = 5;
System.out.println(toggleBitsFromLToR(n, l, r));
}
}
// Contributed by Pramod Kumar
// C# implementation to toggle bits
// in the given range
using System;
namespace Toggle {
public class GFG {
// Function to toggle bits in the given range
static int toggleBitsFromLToR(int n, int l, int r)
{
// calculating a number 'num' having 'r'
// number of bits and bits in the range l
// to r are the only set bits
int num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1);
// toggle bits in the range l to r in 'n'
// Besides this, we can calculate num as:
// num=(1<<r)-l .
// and return the number
return (n ^ num);
}
// Driver Code
public static void Main()
{
int n = 50;
int l = 2, r = 5;
Console.Write(toggleBitsFromLToR(n, l, r));
}
}
}
// This code is contributed by Sam007.
<script>
// Javascript implementation to toggle bits in
// the given range
// function to toggle bits in the given range
function toggleBitsFromLToR(n, l, r)
{
// calculating a number 'num' having 'r'
// number of bits and bits in the range l
// to r are the only set bits
var num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1);
// toggle bits in the range l to r in 'n'
// and return the number
//Besides this, we can calculate num as: num=(1<<r)-l .
return (n ^ num);
}
// Driver program to test above
var n = 50;
var l = 2, r = 5;
document.write( toggleBitsFromLToR(n, l, r));
</script>
<?php
// PHP implementation
// to toggle bits in
// the given range
// function to toggle bits
// in the given range
function toggleBitsFromLToR($n, $l, $r)
{
// calculating a number
// 'num' having 'r'
// number of bits and
// bits in the range l
// to r are the only
// set bits
$num = ((1 << $r) - 1) ^
((1 << ($l - 1)) - 1);
// toggle bits in the
// range l to r in 'n'
//Besides this, we can calculate num as: $num=(1<<$r)-$l .
// and return the number
return ($n ^ $num);
}
// Driver Code
$n = 50;
$l = 2; $r = 5;
echo toggleBitsFromLToR($n, $l, $r);
// This code is contributed by anuj_67
?>
# Python implementation
# to toggle bits in
# the given range
# function to toggle bits
# in the given range
def toggleBitsFromLToR(n, l, r):
# calculating a number
# 'num' having 'r'
# number of bits and
# bits in the range l
# to r are the only set bits
num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1)
# toggle bits in the
# range l to r in 'n'
# Besides this, we can calculate num as: num=(1<<r)-l .
# and return the number
return (n ^ num)
# Driver code
n = 50
l = 2
r = 5
print(toggleBitsFromLToR(n, l, r))
# This code is contributed
# by Anant Agarwal.
Output
44
Time Complexity: O(1)
Auxiliary Space: O(1)
Approach 2:
Iterate over the given range from L to R and check if the ith bit is set or not. if the ith bit is set then make it unset otherwise make it set bit.
// C++ implementation to toggle bits in
// the given range
#include <bits/stdc++.h>
using namespace std;
// Function to toggle bits in the given range
int toggleBitsFromLToR(int N, int L, int R)
{
int res = N;
for (int i = L; i <= R; i++) {
// Set bit
if ((N & (1 << (i - 1))) != 0) {
// XOR will set 0 to already set
// bits(a^a=0)
res = res ^ (1 << (i - 1));
}
// unset bits
else {
// OR will set'0'bits to 1
res = res | (1 << (i - 1));
}
}
return res;
}
// Driver code
int main()
{
int n = 50;
int l = 2, r = 5;
cout << toggleBitsFromLToR(n, l, r);
return 0;
}
// This code is contributed by phasing17
// Java implementation to toggle bits in
// the given range
import java.io.*;
class GFG {
// Function to toggle bits in the given range
static int toggleBitsFromLToR(int N, int L, int R)
{
int res = N;
for (int i = L; i <= R; i++) {
// Set bit
if ((N & (1 << (i - 1))) != 0) {
// XOR will set 0 to already set
// bits(a^a=0)
res = res ^ (1 << (i - 1));
}
// unset bits
else {
// OR will set'0'bits to 1
res = res | (1 << (i - 1));
}
}
return res;
}
// Driver method
public static void main(String[] args)
{
int n = 50;
int l = 2, r = 5;
System.out.println(toggleBitsFromLToR(n, l, r));
}
}
// Contributed by Ocean Bhardwaj
// C# implementation to toggle bits in
// the given range
using System;
class GFG {
// Function to toggle bits in the given range
static int toggleBitsFromLToR(int N, int L, int R)
{
int res = N;
for (int i = L; i <= R; i++) {
// Set bit
if ((N & (1 << (i - 1))) != 0) {
// XOR will set 0 to already set
// bits(a^a=0)
res = res ^ (1 << (i - 1));
}
// unset bits
else {
// OR will set'0'bits to 1
res = res | (1 << (i - 1));
}
}
return res;
}
// Driver Code
public static void Main(string[] args)
{
int n = 50;
int l = 2, r = 5;
// Function call
Console.WriteLine(toggleBitsFromLToR(n, l, r));
}
}
// This code is Contributed by phasing17
// JavaScript implementation to toggle bits in
// the given range
// Function to toggle bits in the given range
function toggleBitsFromLToR(N, L, R)
{
let res = N;
for (let i = L; i <= R; i++) {
// Set bit
if ((N & (1 << (i - 1))) != 0) {
// XOR will set 0 to already set
// bits(a^a=0)
res = res ^ (1 << (i - 1));
}
// unset bits
else {
// OR will set'0'bits to 1
res = res | (1 << (i - 1));
}
}
return res;
}
// Driver code
let n = 50;
let l = 2, r = 5;
console.log(toggleBitsFromLToR(n, l, r));
// This code is contributed by phasing17
# Python3 implementation to toggle bits in
# the given range
# Function to toggle bits in the given range
def toggleBitsFromLToR(N, L, R):
res = N
for i in range(L, R + 1):
# Set bit
if ((N & (1 << (i - 1))) != 0):
# XOR will set 0 to already set
# bits(a^a=0)
res = res ^ (1 << (i - 1))
# unset bits
else:
# OR will set'0'bits to 1
res = res | (1 << (i - 1))
return res
# Driver code
n = 50
l = 2
r = 5
print(toggleBitsFromLToR(n, l, r))
# This code is contributed by phasing17
Output
44
Time Complexity: O(R – L + 1)
Auxiliary Space: O(1)
Contact Us