Bitmaps in Algorithms

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)

Scenario

• Bitmap indexing
• Bloom filters
• Leetcode 698