# 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`

.

- left shift 1 by i bits, and perform OR operation with
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`

.

- take the complement(~) of 1 left shifted by i bits, and perform bitwise AND(&) operation with
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`

.

1 | int[] set = {1,2,3}; |

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`

- Shift

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`

.

## Other Problems

- Bitmap indexing
- Bloom filters
- Leetcode 698