[ad_1]

Bitmask is the idea of using the binary representation of numbers to solve otherwise difficult problems. This representation is unique for each number.

*Example*: The bits of the number 11 is “1011”, because in base 2:

11 = 8 + 2 + 1 = **1***2³ + **0***2² + **1***2¹ + **1***2⁰= “1011”

When dealing with bitmask: **It does not matter what the actual number is. **All we should care about is its binary form and the following operations:

## Common Operations for Bit Manipulation

- Left Shift: to shift
`x`

to the left by n spaces, we use`x << n`

. For example, in binary form,`"1011" << 3 = "1011000"`

, or`11 << 3 = 88`

. - Right Shift: similarly, we use
`x >> n`

. For example,`"10101" >> 3= "101"`

(note that the 1bits get vanished). - Clear the lowest set bit:
`x & (x — 1)`

(e.g.`"10100" -> "10000"`

) - AND:
`a & b = 1`

if`a = 1`

AND`b = 1`

, else 0 - OR:
`a | b = 1`

if`a = 1`

OR`b = 1`

, else 0 - XOR:
`a ^ b = 1`

if exactly one of`a`

or`b`

is 1, else 0 - For numbers greater than 1, we apply these operations iteratively to each bit position. E.g.
`"10111" AND "1100" = "00100" = "100"`

**Important Operations for Bitmasks**

- Turn the i^th bit to 1:
`mask = mask | (1 << i)`

, or`mask |= (1 << i)`

- Flip the i^th bit:
`mask = mask ^ (1 << i)`

, or`mask ^= (1 << i)`

Most of the time, you will be manipulating a number called `mask`

. This mask will be used to keep track of the “used” or “unused” elements in a list.

*Example:* Given a set of 3 elements `A = {1,2,3}`

, how do we effectively represent all the subsets of this set?

*Answer: *Use numbers from 0 to 7 and their corresponding bitmasks, where each 1bit position signals to a chosen element:

`0 = "000" = {} = the empty set`

1 = "00**1**" = {1}

2 = "0**1**0" = {2}

3 = "0**11**" = {1, 2}

4 = "**1**00" = {3}

5 = "**1**0**1**" = {1, 3}

6 = "**11**0" = {2, 3}

7 = "**111**" = {1, 2, 3}

In general, given a set of `n`

elements,** we can always represent all the subsets of this set using numbers from 0 to ****2^n — 1****.**

And this is the basic idea of bitmask. We will manipulate a `mask`

that represents a current subset of a given list.

## Count the number of 1bits in the binary representation of a number

We can keep shifting the number to the right until it becomes zero. At each step, we check if the 0^th bit is one, and add it to the total count:

[ad_2]

Source link