Introduction

Bitwise operations is one of the bitmap representation methods.

Basically we have an integer num, we can use its i-th bit(counting from right to left, starting from 0) to represent the true/false value of num[i].

Set the i-th bit to 1(true), and leave other bits unchanged: num|=(1<<i)
- left shift 1 by i bits, and perform OR operation with num.
Set the i-th bit to 0(false), and leave other bits unchanged: num &= ~(1<<i) or (num ^=1<<i)
- take the complement(~) of 1 left shifted by i bits, and perform bitwise AND(&) operation with num.
Get num[i]: (num >> i) & 1
- extracts the i-th bit(counting from right to left)
(num<<n) basically produces an num * 2^n
- 1<<5 = 100000 in binary, 1<<2 = 100 in binary
- when num = 1, sometimes it can be used in algorithms to check a target position
Check if A is a subset of B:
- A & B ==A
- 010 & 011 = 010
X & 1 makes X remain the same

Scenario

Subset Enumeration

Given that we have a set {1,2,3}, let’s find out all the subsets: {},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}. Therefore, we have 8 subsets(including the empty one).

A good approach to get all these subsets is using bits. Let’s use one bit to represent a single element. Given {1,2,3}, we have 3 bits, and each bit represent an element.

For example, 000 represents {}, 001 represents {3}, because only the third bit is maked as 1(exists). So actually, we are going to have 3 positions, and each position has two options(0/1), which means we have 2^3 = 8 subsets(000,001,010,011,100,101,110,111).

Then, this can be written as 1<<3, which means to take 1 left shifted by 3 bits, resulting in 1000 in binary. We want to have an 111 , which is the last subset we would have for the set {1,2,3}. Therefore, we can have a for loop, iterate the range[0,1<<3), integers in this range represent the possible subsets.

Another for loop is used to get positions of the 1s from these subsets representations in binary, so that we can get the actual numbers like 1,2,3.

int[] set = {1,2,3};
int n = set.length;
for(int i = 0;i<(1<<n);i++){
    //this is for listing all the possible subsets in binary
    List<Integer> subset = new ArrayList<>();
    for(int j = 0;j<n;j++){
      	if(((i>>j)&1) == 1){
          subset.add(set[j]);
        }
        //if((1<<j & i) !=0){
            //that means 1<<j is 1, so the jth postion of i is 1.
            //subset.add(set[j]);
        //}
    }
    System.out.println(subset);
}

We have two options to check if n-th bit of i is 1

Explaination for ((i>>j)&1)==1
- Shift i right by j bits. Actually it is extracting the j-th bit of i, so you can directly compare with j
- If we have i = 1011, j = 2, then i>>j = 11, 11&1 = 11&01 = 01 = 1

Explaination for (1<<j & 1)!=0:

if we have 10111 & 100, this will give us 00100, because the third number in 10111 is 1.
if we have 10011 & 100, this will give us 00000, because the the third number in 10111 is 0.
So basically, if the result is not 0, we can ensure that the number at the position j is 1.

Introduction

Scenario

Subset Enumeration

Other Problems