Tanner and Josh1 are in the Logic Design lab helping Siddharth debug some finicky FPGAs. To track down one of the errors in their circuit, they have to analyze a series of bitstreams (ie. 32-bit integers) and count how many times a particular mask appears in each bitstream.

For instance, given a mask of `1001` (ie. `9` in hexadecimal) and a bitstream of `10010010` (ie. `146` in decimal), then the mask occurs `2` times in the sequence of bits.

Likewise, given a mask of `1111` (ie. `F` in hexadecimal) and a bitstream of `1111111` (ie. `127` in decimal), then the mask occurs `4` times in the sequence of bits.

Both of these examples are demonstrated below.

Unfortunately, since Tanner and Josh are CPEGs, software is not really their strong suit2. Therefore, they want you to help them write a program that analyzes bitstreams and counts the number of times a mask appears in the sequence of bits.

## Input¶

You will be given a series of masks and bitstreams in the form of a hexadecimal `mask` and integer `bitstream`:

### Example Input¶

``````9 146
F 127
``````

Note: Each mask is 4 bits, while integer `bitstream` is a 32-bit integer.

## Output¶

For each pair of `mask` and `bitstream`, computer the number of times the `mask` appears in the `bitstream` and then output a message in the following format:

### Example Output¶

``````1. 146 contains 0x9 2 times
2. 127 contains 0xF 4 times
``````

#### Algorithmic Complexity¶

For each input test case, your solution should have the following targets:

 Time Complexity `O(N)`, where `N` is the number of bits in each input bitstream. Space Complexity `O(1)`

Your solution may be below the targets, but it should not exceed them.

## Submission¶

``````\$ cd path/to/cse-30872-su24-assignments     # Go to assignments repository
\$ git checkout master                       # Make sure we are on master
\$ git pull --rebase                         # Pull any changes from GitHub

\$ git checkout -b challenge08               # Create and checkout challenge08 branch

\$ \$EDITOR challenge08/program.cpp           # Edit your code

\$ git commit -m "challenge08: done"         # Commit your changes

\$ git push -u origin challenge08            # Send changes to GitHub
``````

To check your code, you can use the `.scripts/check.py` script or curl:

``````\$ .scripts/check.py
Checking challenge08 program.c ...
Result Success
Time 0.41
Score 6.00 / 6.00

\$ curl -F source=@challenge08/program.c https://dredd.h4x0r.space/code/cse-30872-su24/challenge08
{"result": "Success", "score": 6, "time": 0.416405344009399414, "value": 6, "status": 0}
``````

#### Pull Request¶

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the instructor.

1. Winners of the CSE 34872 Programming Challenges (Summer 2020) Programming Contest.

2. Not really true. Some of the best programmers in the department are CPEGs