408757: GYM103295 E Ratman's Puzzle

Ratman is attempting to save the city from one of his most dangerous nemeses, the Puzzler! Unfortunately, the Puzzler has distributed various bombs around Ratman's hometown, Gothem city, and Ratman must solve a series of math puzzles to defuse each bomb.

Specifically, each bomb is labelled with two numbers $$$n$$$ and $$$k$$$. For each bomb, Ratman must calculate the number of pairs of integers $$$a, b$$$ with $$$0 \leq a < b < 2^k$$$ such that $$$a \oplus b = n$$$, where $$$\oplus$$$ denotes the XOR operator. After doing so, he can plug the result into his bomb-defusing machine, which will neutralize the threat if the number is calculated correctly.

Write a program to help Ratman solve the Puzzler's riddles and defuse the bombs throughout Gothem city!

The input will consist of two numbers $$$n$$$ $$$(1 \leq n \leq 10^{18})$$$ and $$$k$$$ $$$(1 \leq k \leq 60)$$$.

Output the number of distinct pairs of integers $$$a, b$$$ such that $$$0 \leq a < b < 2^k$$$ and $$$a \oplus b = n$$$.

7777 1

0

3 2

2

In the first sample, the only possible pair is $$$a = 0, b = 1$$$ and $$$0 \oplus 1 = 1 \neq 7777$$$.

In the second sample, there are two pairs that satisfy the above property. Specifically $$$a = 0, b = 3$$$ and $$$a = 1, b = 2$$$ both work.