All about Bitwise Operations [Beginner-Intermediate]

22946

Prerequisites:

Knowing about the binary number system is the only prerequisite to this topic. If you want to learn about it you could refer this article by bliss14b.

Introduction:

Bitwise Operations:

AND (&):
X & Y → This keeps the bits that are set for both X and Y.

OR (|):
X | Y → This keeps all the bits that are set either in X or in Y.

NOT (~):
~X → This inverts all the bits present in the binary representation of X.

XOR (^):
X^Y → This checks if a position has a set bit in either one of X or Y, if there is then the result also has a set bit there. Eg.
X = 1011010
Y = 0101010
------------------
X^Y = 1110000

Some Properties of XOR:

1. a^0 = a
2. a^a = 0
3. x^y = y^x (Commutativity)
4. (x^y)^z = x^(y^z) (Associativity)

NOTE: Do not confuse these with logical operations like logical AND/OR.
Bitwise = Bit by bit checking, returns an integer.
Logical = Returns a boolean values, true/false

Right and left Shift (>>/<<):
Left shift multiplies a number by 2 whereas right shift divides it by 2. These are called left/right shift operations as they shift the numbers when represented in their binary format to left/right. Eg.
19 : 10011
(19>>2) : 100
This divides 19 by 4.

Some Useful Relations of Bitwise operators:

1. (a|b) = (a+b) - (a&b)     This is helpful when we want to related AND/OR operations with sum.

2. (a+b) = (a^b) + 2*(a&b)   This one is a very special relation which can be used to solve some seemingly very tough questions.

Time Complexity Analysis:
Time complexity of all bitwise operations is O(1). Infact these are faster than the arithmatic operations, this is the reason why experienced competitive coders use the shift operators instead of * or /.

Breif overview of Bitsets:
This is a very useful data structure which can replace the boolean array/vector. In a number of questions where we use a visited boolean array, we could use a bitset. The advantage with bitset is that it uses 1 bit for each position rather than 1 byte as in the case of boolean array. This reduces the space complexity by a factor of 8. The only disadvantage with bitsets is that they can only be declared by using a constant number, eg. bitset<1000>. Also note that a bitset of size 10^9 will take 128MB of space which is sometimes fine (depending on the limit), however if we were to use a boolean array, it would require 1GB of space!

Applications and common problems: :

Iterating over all 2^k possibilities: Problem: https://leetcode.com/problems/subsets/

These types of problems are generally solved using backtracking, however there is another way of solving these using bit manipulation. Here we take advantage of the fact that when we write binary numbers form 0 to (2^k)-1, these numbers will have all combinations of 1s and 0s that can be present in an array of size k (since each position has 2 choices so overall 2^k arrays). So we can iterate from all the numbers starting from 0 upto (2^k)-1 and check their binary representations. For each number, if the ith bit contains a 1, we add the element present at that location to our current vector and if its a 0, we ignore it. This is called bit masking.
Bitwise solution to Subsets problem: (C++)
```
class Solution {
public:
	vector<vector<int>> subsets(vector<int>& nums) {
		vector<vector<int>> res;   // Will contain all the vectors
		int n = nums.size();
		for(int i=0;i<(1<<n);i++){
			vector<int> cur;
			for(int j=0;j<n;j++){
				if((i>>j) & 1) cur.push_back(nums[j]);  // if the jth bit is set in i then we add it to our current vector
			}
			res.push_back(cur);
		}
		return res;
	}
};
```
XOR swap Algorithm: What is the minimum number of variables required to swap two numbers?
No its not 1, it is possible to swap the numbers using no other extra variables using the magical XOR operator:
```
a, b --> integers to be swapped
a = a^b;   // Now a contains a^b
b = a^b;   // Now b will have a
a = a^b;   // Now a will have b
```
Finding parity of a number: Parity of a number is based on the number of 1’s present in the binary equivalent of that number. When the count of present 1s is odd, it returns odd parity, for an even number of 1s it returns even parity.
One obvious way of solving this is to loop over all bits of a number and check if the number of set bits is even or odd. The time complexity of this would be O(log(n)). But is it possible to find this in O(1)?
As it turns out, it is poosible. Refer the following code (for 32 bit numbers):
```
bool findParity(int x) {
 	int y = x ^ (x >> 16);
 	y = y ^ (y >> 8);
 	y = y ^ (y >> 4);
 	y = y ^ (y >> 2);
 	y = y ^ (y >> 1);
 	if (y & 1) return 1;
 	return 0;
 }
```
The code essentially keeps splitting the number into two parts and takes the bits that are different between the two part by XORing them. Take an example, write it on a sheet of paper and you'll understand it better.

XOR queries: Problem: https://leetcode.com/problems/xor-queries-of-a-subarray/
Prerequisite: Prefix sums
Since a^a = 0, we can solve this problem in O(n) using prefix XORs array. We store the prefix XORs in an array and then for each query [l,r], res = prefix_xor[l-1]^pref_xor[r]

C++ code:

class Solution {
public:
	vector<int> xorQueries(vector<int>& a, vector<vector<int>>& queries) {
		int n = a.size();
		vector<int> pref_xors(n);
		pref_xors[0] = a[0];
		for(int i=1;i<n;i++) pref_xors[i] = pref_xors[i-1]^a[i];
		vector<int> res;
		for(auto x : queries){
			int r = x[1], l = x[0];
			int cur = pref_xors[r];
			if(l>0) cur = cur^pref_xors[l-1];   // Since we have to remove all elements that occur before l
			res.push_back(cur);
		}
		return res;
	}
};

Some Important Problems:

Missing Number: https://leetcode.com/problems/missing-number/
Bitwise ORs of Subarrays: https://leetcode.com/problems/bitwise-ors-of-subarrays/
XOR Queries of a Subarray: https://leetcode.com/problems/xor-queries-of-a-subarray/
Minimum Flips to Make a OR b Equal to c: https://leetcode.com/problems/minimum-flips-to-make-a-or-b-equal-to-c/
Count Triplets That Can Form Two Arrays of Equal XOR: https://leetcode.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/
Bitwise AND of Numbers Range: https://leetcode.com/problems/bitwise-and-of-numbers-range/
Decode XORed Permutation: https://leetcode.com/problems/decode-xored-permutation/

PS: Any suggestions are welcome, this is my first blog here. Also don't forget to upvote if you liked this post!

Comments (10)