Toggle all even bits of a number

0 0 7 minutes read

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 code
int main()
{
    int n = 11;
    cout << evenbittogglenumber(n);
    return 0;
}

Java

// Java code to Toggle all
// even bit of a number
import 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 code
n = 11
print(evenbittogglenumber(n))
 
#This code is contributed by Nikita Tiwari.

C#

// C# code to Toggle all
// even bit of a number
using 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

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 2¹ + 2³ + 2⁵ + …. 2^{(n – !(n % 1))} .

C++

//C++ implementation of the approach
 
#include <bits/stdc++.h>
using namespace std;
 
//function to toggle all the even bits
long 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 code
int 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 approach
import math
# function to toggle all the even bits
def 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 code
n = 11
     
# function call
print(even_bit_toggle_number(n))

C#

// C# implementation of the approach
using 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 bits
function 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 code
let n = 11;
     
//function call
console.log(evenbittogglenumber(n));
 
 
//this code is contributed by phasing17

Output

Time Complexity : O(1)

Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!