Bitmap – BitArray – BitSet – Bit Vector

Besides image processing, Bitmaps are handy with real time operations and analytics. Bitmap is a useful data structure and extremely space efficient. Also, BitMaps are underlying data structure for other data structures. You can find Bitmaps being used in many places including linux kernel.

Bitmap, BitSet or BitVector is an array of zeros and ones. A cell, bit in bitmap can be set to either one or zero. Since BitMap uses array, we can work with index, offset. Bit operations such as OR, AND, XOR can be used with ease.

bitmap_population_count.

Population count can be easily calculated for Bitmaps, which is the number of bits that are set to 1. There are efficient algorithms for calculating population count, there are even special hardware instructions for this operation.

Bit related operations are of two kinds: Constant time (O(1)) e.g. operations to get/set of a particular bit and operations that are O(N) which basically operate on a group of bits. N in these cases is the length of bits that the operation will need to work on.

Common use case for bitmaps are counting stuff. Here are some examples:

  • Has user 123 been online today? This week? This month?
  • Has user 123 performed action “X”?
  • How many users have been active have this month?
  • How many unique users have performed action “X” this week?
  • How many % of users that were active last week are still active?
  • How many % of users that were active last month are still active this month?
  • And a lot of other things!

For more info checkout wiki Bit Array.

Sharing is caring Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInDigg thisEmail this to someoneShare on Reddit