Bitmaps in Algorithms

2023-03-14 22:43:42

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

# Scenario

- Bitmap indexing
- Bloom filters
- Leetcode 698