Bitwise operations 3 - MarisaOJ: Marisa Online Judge

Given a non-negative integer

$a = 0$ , perform a series of

$q$ queries of the following types: -

$1 x$ : Set

$a$ to

$a \text{ XOR } x$ . -

$2$ : Turn off the most significant set bit of

$a$ . If

$a$ is already

$0$ , ignore this query. -

$3$ : Count the number of set bits in

$a$ . The most significant set bit is the highest-order bit that is set to

$1$ . For example, for the number

$36$ in binary

$(100100)_2$ , the most significant set bit is the fifth bit. After turning off this bit, the value becomes

$(100)_2$ , which is

$4$ in decimal representation. ### Input - The first line contains an integer

$q$ . - The next

$q$ lines each contain a query in the specified format. ### Output - Print the answer as an integer for each query of type

$3$ . ### Constraints -

$1 \le q \le 3 \times 10^5$ . -

$0 \le x < 2 ^ {30}$ . ### Example Input:

$5 2 1 5 3 2 3$

Output:

$2 1$

**Bonus: Find a way to handle each query with a time complexity of

$\text{O}(1)$ .**

Topic

Bitmasks

Rating

1100

Solution (0)

Solution