Given a number, the task is to Toggle all even bit of a number
Examples:
Input : 10 Output : 0 binary representation 1 0 1 0 after toggle 0 0 0 0 Input : 20 Output : 30 binary representation 1 0 1 0 0 after toggle 1 1 1 1 0
1. First generate a number that contains even position bits.
2. Take XOR with the original number. Note that 1 ^ 1 = 0 and 1 ^ 0 = 1.
Let’s understand this approach with below code.
C++
// CPP code to Toggle all even// bit of a number#include <iostream>using namespace std;// Returns a number which has all even// bits of n toggled.int evenbittogglenumber(int n){ // Generate number form of 101010 // ..till of same order as n int res = 0, count = 0; for (int temp = n; temp > 0; temp >>= 1) { // if bit is even then generate // number and or with res if (count % 2 == 1) res |= (1 << count); count++; } // return toggled number return n ^ res;}// Driver codeint main(){ int n = 11; cout << evenbittogglenumber(n); return 0;} |
Java
// Java code to Toggle all// even bit of a numberimport java.io.*;class GFG { // Returns a number which has // all even bits of n toggled. static int evenbittogglenumber(int n) { // Generate number form of 101010 // ..till of same order as n int res = 0, count = 0; for (int temp = n; temp > 0; temp >>= 1) { // if bit is even then generate // number and or with res if (count % 2 == 1) res |= (1 << count); count++; } // return toggled number return n ^ res; } // Driver code public static void main(String args[]) { int n = 11; System.out.println(evenbittogglenumber(n)); }}// This code is contributed by Nikita Tiwari. |
Python3
# Python code to Toggle all# even bit of a number# Returns a number which has all even# bits of n toggled.def evenbittogglenumber(n) : # Generate number form of 101010 # ..till of same order as n res = 0 count = 0 temp = n while (temp > 0) : # if bit is even then generate # number and or with res if (count % 2 == 1) : res = res | (1 << count) count = count + 1 temp >>= 1 # return toggled number return n ^ res # Driver coden = 11print(evenbittogglenumber(n))#This code is contributed by Nikita Tiwari. |
C#
// C# code to Toggle all// even bit of a numberusing System; class GFG { // Returns a number which has // all even bits of n toggled. static int evenbittogglenumber(int n) { // Generate number form of 101010 // ..till of same order as n int res = 0, count = 0; for (int temp = n; temp > 0; temp >>= 1) { // if bit is even then generate // number and or with res if (count % 2 == 1) res |= (1 << count); count++; } // return toggled number return n ^ res; } // Driver code public static void Main() { int n = 11; Console.WriteLine(evenbittogglenumber(n)); }} // This code is contributed by Anant Agarwal. |
PHP
<?php// php code to Toggle all// even bit of a number// Returns a number which has // all even bits of n toggled.function evenbittogglenumber($n){ // Generate number form of 101010 // ..till of same order as n $res = 0; $count = 0; for ($temp = $n; $temp > 0; $temp >>= 1) { // if bit is even then generate // number and or with res if ($count % 2 == 1) $res |= (1 << $count); $count++; } // return toggled number return $n ^ $res;} // Driver code $n = 11; echo evenbittogglenumber($n);// This code is contributed by mits ?> |
Javascript
<script>// JavaScript program to Toggle all// even bit of a number // Returns a number which has // all even bits of n toggled. function evenbittogglenumber(n) { // Generate number form of 101010 // ..till of same order as n let res = 0, count = 0; for (let temp = n; temp > 0; temp >>= 1) { // if bit is even then generate // number and or with res if (count % 2 == 1) res |= (1 << count); count++; } // return toggled number return n ^ res; }// Driver code let n = 11; document.write(evenbittogglenumber(n));</script> |
Output
1
Time Complexity : O(log n)
Auxiliary Space: O(1)
Another Approach:
To toggle a bit, we can take XOR of 1 and that bit (as 1 ^ 1 = 0, and 1 ^ 0 = 1). Therefore, to set all odd bits of an n bit number, we need to use a bit mask which is an n bit binary number with all odd bits set. This mask can be generated in 1 step using the formula of sum of a geometric progression, as an n bit number …1010 is equal to 21 + 23 + 25 + …. 2 (n – !(n % 1)) .
C++
//C++ implementation of the approach#include <bits/stdc++.h>using namespace std;//function to toggle all the even bitslong long int evenbittogglenumber(long long int n) { //calculating number of bits using log int numOfBits = 1 + (int)log2(n); //if there is only one bit, if (numOfBits == 1) return n; //calculating the max power of GP series int m = (numOfBits / 2); //calculating mask using GP sum //which is a(r ^ n - 1) / (r - 1) //where a = 2, r = 4, n = m int mask = 2 * (pow(4, m) - 1) / 3; //toggling all even bits using mask ^ n return mask ^ n; }// Driver codeint main(){ int n = 11; //function call cout << evenbittogglenumber(n); return 0;}//this code is contributed by phasing17 |
Java
import java.lang.Math;public class Main { // function to toggle all the even bits public static long evenBitToggleNumber(long n) { // calculating number of bits using log int numOfBits = 1 + (int) (Math.log(n) / Math.log(2)); // if there is only one bit, if (numOfBits == 1) return n; // calculating the max power of GP series int m = (numOfBits / 2); // calculating mask using GP sum // which is a(r ^ n - 1) / (r - 1) // where a = 2, r = 4, n = m long mask = 2 * ((long) Math.pow(4, m) - 1) / 3; // toggling all even bits using mask ^ n return mask ^ n; } // Main function public static void main(String[] args) { long n = 11; // function call System.out.println(evenBitToggleNumber(n)); }} |
Python3
# Python implementation of the approachimport math# function to toggle all the even bitsdef even_bit_toggle_number(n): # calculating number of bits using log num_of_bits = 1 + int(math.log2(n)) # if there is only one bit, return n if num_of_bits == 1: return n # calculating the max power of GP series m = num_of_bits // 2 # calculating mask using GP sum # which is a(r ^ n - 1) / (r - 1) # where a = 2, r = 4, n = m mask = int(2 * ((4 ** m) - 1) / 3) # toggling all even bits using mask ^ n return mask ^ n# Driver coden = 11 # function callprint(even_bit_toggle_number(n)) |
C#
// C# implementation of the approachusing System;class GFG { // function to toggle all the even bits static int evenbittogglenumber(int n) { // calculating number of bits using log int numOfBits = 1 + (int)(Math.Log(n) / Math.Log(2)); // if there is only one bit, if (numOfBits == 1) return n; // calculating the max power of GP series int m = (numOfBits / 2); // calculating mask using GP sum // which is a(r ^ n - 1) / (r - 1) // where a = 2, r = 4, n = m int mask = 2 * (int)(Math.Pow(4, m) - 1) / 3; // toggling all even bits using mask ^ n return mask ^ n; } // Driver code public static void Main(string[] args) { int n = 11; // Function call Console.WriteLine(evenbittogglenumber(n)); }}// This code is contributed by phasing17 |
Javascript
//JavaScript implementation of the approach//function to toggle all the even bitsfunction evenbittogglenumber(n) { //calculating number of bits using log let numOfBits = 1 + Math.floor(Math.log2(n)); //if there is only one bit, if (numOfBits == 1) return n; //calculating the max power of GP series let m = Math.floor(numOfBits / 2); //calculating mask using GP sum //which is a(r ^ n - 1) / (r - 1) //where a = 2, r = 4, n = m let mask = Math.floor(2 * (Math.pow(4, m) - 1) / 3); //toggling all even bits using mask ^ n return mask ^ n; }// Driver codelet n = 11; //function callconsole.log(evenbittogglenumber(n));//this code is contributed by phasing17 |
Output
1
Time Complexity : O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
