## What is Bit Manipulation?

**Bit Manipulation** is a collection of techniques that allows us to solve various problems by leveraging the **binary representation** of a number and its bits. Here, in this article, some interesting bit manipulation techniques and algorithms are described below:

## Check if a number is a power of 2:

A nice Bit Manipulation based approach to solve this problem is to observe the fact that all powers of two have only **1 bit (MSB)** set in their binary representation. So, when we subtract 1 from any power of 2, the set bit gets unset, and all the bits coming after it, gets set. Performing the **bitwise AND** of these two numbers, we should get the result as zero, if the original number was a power of 2.

An **edge case** to consider in this approach is that this approach will not work if **n = 0**, so we need to handle this case separately.

### C++ Code

bool checkIfPowerOf2(int n) { n = abs(n); return n && (!(n & (n - 1))); }

### Java Code

public static boolean checkIfPowerOf2(int n) { n = Math.abs(n); return (n > 0) && (((n & (n - 1)) == 0)); }

### Python Code

def checkIfPowerOf2(n): n = abs(n) return n and (not (n & (n - 1)))

### Complexity Analysis

- Time Complexity: O(1)
- Space Complexity: O(1)

## Swapping 2 Numbers using Bitwise Operators:

We can swap 2 numbers without using the 3rd variable, by using the **bitwise XOR **operator. Note that the bitwise XOR of 2 numbers returns a number that has those bits set, which are **unset in one of the numbers and set in the other number.** Using this number, if XOR it with our original numbers in reverse order, we will be able to recover back our original numbers, but now in **swapped** condition.

### C++ Implementation

void swap(int &a, int &b) { cout << "Before Swapping:" << endl; cout << a << " " << b << endl; a ^= b; b ^= a; a ^= b; cout << "After Swapping:" << endl; cout << a << " " << b << endl;

### Java Implementation

public static void swap(int a, int b) { System.out.println("Before Swapping:"); System.out.println(a + " " + b); a ^= b; b ^= a; a ^= b; System.out.println("After Swapping:"); System.out.println(a + " " + b); }

### Python Implementation

def swap(a, b): print("Before Swapping:") print(a, b) a ^= b b ^= a a ^= b print("After Swapping:") print(a, b)

### Complexity Analysis

- Time Complexity: O(1)
- Space Complexity: O(1)

## XOR of numbers from [1, n]:

The XOR of all numbers in the range **[1, n]** can be efficiently calculated using the following formula:

- If
**n % 4 = 0**, the answer is**n**. - If
**n % 4 = 1**, the answer is**1**. - If
**n % 4 = 2**, the answer is**n + 1**. - If
**n % 4 = 3**, the answer is**0**.

This formula can be observed by** brute-forcing** the answers for some small **n** and then finding the pattern in the answers.

## C++ Code

int getXOR(int n) { if(n % 4 == 0) { return n; } else if(n % 4 == 1) { return 1; } else if(n % 4 == 2) { return ++n; } else { return 0; } }

### Java Code

public static int getXOR(int n) { if(n % 4 == 0) { return n; } else if(n % 4 == 1) { return 1; } else if(n % 4 == 2) { return ++n; } else { return 0; } }

### Python Code

def getXOR(n): if n % 4 == 0: return n elif n % 4 == 1: return 1 elif n % 4 == 2: return n + 1 else: return 0

### Complexity Analysis

**Time Complexity:**O(1)**Space Complexity:**O(1)

## Finding the MSB in a Fixed-Size Integer

Suppose that we are dealing with 32-bit integers. The approach here is to **set all the bits** of the number, and then add 1 to it, so that only a bit, which appears after the **MSB** is set. Then we can just **divide the number by 2**, and return the answer.

### C++ Implementation

int setBit(int n) { n |= (n >> 1); n |= (n >> 2); n |= (n >> 4); n |= (n >> 8); n |= (n >> 16); n++; n >>= 1; return n;

### Java Implementation

public static int setBit(int n) { n |= (n >> 1); n |= (n >> 2); n |= (n >> 4); n |= (n >> 8); n |= (n >> 16); n++; n >>= 1; return n; }

### Python Implementation

def setBit(n): n |= (n >> 1); n |= (n >> 2); n |= (n >> 4); n |= (n >> 8); n |= (n >> 16); n += 1; n >>= 1; return n;

### Complexity Analysis

**Time Complexity:**O(1)**Space Complexity:**O(1)

## FAQs

**Q. What is meant by a bit being set or unset?**

A. If a bit has value 1, it is said to be set, else it is said to be unset.

**Q. How many bits are present in a number’s binary representation?**

A. **floor**(**log _{2}n) + 1** bits are present in a number’s binary representation.