Swap all odd and even bits

Given an unsigned integer n. The task is to swap all odd bits with adjacent even bits.

Examples: 

Input: 23
Output: 43
Explanation: 23 (0010111) should be converted to 43 (0101011).

Input: 2
Output: 1
Explanation: 2 (0010) should be converted to 1 (0001).

[Naive Approach] Time O(1) and Space O(1)

For every even index i in the binary representation of N starting from index 0 swap bits with (i+1)th index.

Follow the steps below to implement the idea:

• Find the bit at i and i+1 index.
• To swap the bits subtract and add corresponding values.
• To remove bit at i^th bit to i+1. subtract i_bit<<i and add it at i+1 index for that we need to add i_bit<<(i+1).
• Similarly subtract (i+1)^th bit and add it to i^th index.

#include <iostream>
using namespace std;

unsigned int swapBits(unsigned int n)
{
    for (int i = 0; i < 32; i += 2) {

        // Find i th bit
        int i_bit = (n >> i) & 1;

        // Find i+1 th bit
        int i_1_bit = (n >> (i + 1)) & 1;

        // Remove i_bit
        n = n  - (i_bit << i)
            // Remove i+1 th bit
            - (i_1_bit << (i + 1))
            // Put i_bit at i+1 location
            + (i_bit << (i + 1))
            // Put i+1 bit at i location
            + (i_1_bit << i);
    }
    return n;
}


int main()
{
    unsigned int n = 23;
    cout << swapBits(n);

    return 0;
}

class GFG {

    static int swapBits(int n)
    {
        for (int i = 0; i < 32; i += 2) {
            
             // find i th bit
            int i_bit = (n >> i) & 1;
            
            // find i+1 th bit
            int i_1_bit
                = (n >> (i + 1)) & 1; 
            
            // remove i_bit
            n = n - (i_bit << i) 
            
            // remove i+1 th bit
                - (i_1_bit << (i + 1)) 
                
            // put i_bit at i+1 location        
                + (i_bit   << (i + 1)) 
                
                // put i+1 bit at i location   
                + (i_1_bit << i); 
        }
        return n;
    }
    public static void main(String[] args)
    {
        int n = 23;
        System.out.print(swapBits(n));
    }
}

def swapBits(n):
    for i in range(0, 32, 2):

        # Find i th bit
        i_bit = (n >> i) & 1

        # Find i+1 th bit
        i_1_bit = (n >> (i + 1)) & 1

        # Remove i_bit
        n = n - (i_bit << i)
        
        # Remove i+1 th bit
        n = n - (i_1_bit << (i + 1))
        
        # Put i_bit at i+1 location
        n = n + (i_bit << (i + 1))
        
        # Put i+1 bit at i location
        n = n + (i_1_bit << i)

    return n

if __name__ == "__main__":
    n = 23
    print(swapBits(n))

using System;

class GFG {

    
    static int swapBits(int n)
    {
        for (int i = 0; i < 32; i += 2) {
            
            // find i th bit
            int i_bit = (n >> i) & 1; 
            
            // find i+1 th bit
            int i_1_bit
                = (n >> (i + 1)) & 1; 
                
            // remove i_bit
            n = n - (i_bit << i) 
            
            // remove i+1 th bit
                - (i_1_bit << (i + 1))
                
            // put i_bit at i+1 location
                + (i_bit
                   << (i + 1)) 
            // put i+1 bit at i location       
                + (i_1_bit
                   << i);
        }
        return n;
    }
    public static void Main()
    {
        int n = 23; 
        Console.Write(swapBits(n));
    }
}

function swapBits(n) {
    for (let i = 0; i < 32; i += 2) {

        // Find i th bit
        let i_bit = (n >> i) & 1;

        // Find i+1 th bit
        let i_1_bit = (n >> (i + 1)) & 1;

        // Remove i_bit
        n = n  - (i_bit << i)
            // Remove i+1 th bit
            - (i_1_bit << (i + 1))
            // Put i_bit at i+1 location
            + (i_bit << (i + 1))
            // Put i+1 bit at i location
            + (i_1_bit << i);
    }
    return n >>> 0; 
}

// Driver Code 
let n = 23; 
console.log(swapBits(n));

43

[Efficient Approach] Time O(1) and Space O(1)

The value even_bits obtained by even bits of N and Right shifted (>>) by 1 on even_bits and similarly obtain value odd_bits of odd bits of N and perform left shift (<<) by 1 operation on odd_bits. Now (odd_bits | even_bits) will give the desired value.

Follow the below steps to implement the approach:

• Initialize variable even_bits with bitwise and of N with 0xAAAAAAAA(32 bit number with all even bits set as 1 and all odd bits as 0). 
• Initialize variable odd_bits with bitwise and of N with 0x55555555. The number 0x55555555 is a 32 bit number with all odd bits set as 1 and all even bits as 0. 
• Right shift even_bits by 1 and Left shift odd_bits by 1. 
• Return or of even_bits with odd_bits . 

#include <bits/stdc++.h>
using namespace std;
 
unsigned int swapBits(unsigned int n) 
{ 
    // Get all even bits of x 
    unsigned int even_bits = n & 0xAAAAAAAA; 

    // Get all odd bits of x 
    unsigned int odd_bits = n & 0x55555555; 
    
      // Right shift even bits 
    even_bits >>= 1;
  
      // Left shift odd bits 
    odd_bits <<= 1; 

      // Combine even and odd bits 
    return (even_bits | odd_bits); 
} 

int main() 
{ 
     
    unsigned int n = 23; 
    cout<<swapBits(n); 

    return 0; 
} 

#include <stdio.h>


unsigned int swapBits(unsigned int n)
{
    // Get all even bits of n
    unsigned int even_bits = n & 0xAAAAAAAA; 

    // Get all odd bits of n
    unsigned int odd_bits  = n & 0x55555555; 

    even_bits >>= 1;  // Right shift even bits
    odd_bits <<= 1;   // Left shift odd bits

    return (even_bits | odd_bits); 
}

int main()
{
    unsigned int n = 23; 
    printf("%u ", swapBits(n));

    return 0;
}

class GFG{
    
    static int swapBits(int n)
    {
        // Get all even bits of n
        int even_bits = n & 0xAAAAAAAA; 
    
        // Get all odd bits of n
        int odd_bits = n & 0x55555555; 
    
        // Right shift even bits
        even_bits >>= 1; 
        
        // Left shift even bits
        odd_bits <<= 1; 
        
        // Combine even and odd bits
        return (even_bits | odd_bits); 
    }
    
    // Driver program to test above function
    public static void main(String[] args)
    {
        int n = 23; 
        System.out.println(swapBits(n));
    }
}

def swapBits(n) :
    
    # Get all even bits of n
    even_bits = n & 0xAAAAAAAA

    # Get all odd bits of n
    odd_bits = n & 0x55555555
    
    # Right shift even bits
    even_bits >>= 1
    
    # Left shift odd bits
    odd_bits <<= 1 

    # Combine even and odd bits
    return (even_bits | odd_bits) 
    
    
if __name__ == "__main__":
    n = 23
    print(swapBits(n))

using System;

class GFG {
    
    static long swapBits(int n)
    {
        // Get all even bits of n
        long even_bits = n & 0xAAAAAAAA; 
    
        // Get all odd bits of n
        long odd_bits = n & 0x55555555; 
    
        // Right shift even bits
        even_bits >>= 1; 
        
        // Left shift even bits
        odd_bits <<= 1; 
        
        // Combine even and odd bits
        return (even_bits | odd_bits); 
    }
    

    public static void Main()
    {
        
        int n = 23; 
        Console.Write(swapBits(n));
    }
}

function swapBits(n) {
    // Get all even bits of n
    let even_bits = n & 0xAAAAAAAA;

    // Get all odd bits of n
    let odd_bits = n & 0x55555555;

    // Right shift even bits
    even_bits >>>= 1;

    // Left shift odd bits
    odd_bits <<= 1;

    // Combine even and odd bits
    return (even_bits | odd_bits) >>> 0; 
}

// Driver code
let n = 23;
console.log(swapBits(n));

<?php

function swapBits($n)
{
    // Get all even bits of n
    $even_bits = $n & 0xAAAAAAAA;

    // Get all odd bits of n
    $odd_bits = $n & 0x55555555;

    // Right shift even bits
    $even_bits >>= 1;

    // Left shift odd bits
    $odd_bits <<= 1;

    // Combine even and odd bits
    return ($even_bits | $odd_bits);
}

$n = 23;
echo swapBits($n);

?>

43