# Fizz Buzz with Bitwise Operations

I first saw the computer programmer interview screening device FizzBuzz while I was a coding bootcamp student at Wyncode Academy. The Wikipedia entry for the problem is described as follows:

a trivial problem for any would-be computer programmer

After I became an instructor at Wyncode Academy, I had to repeatedly revisit grading and explaining the FizzBuzz problem at the start of each cohort of students.

To date that is talking FizzBuzz to roughly 24 cohorts times approximately 20 people for roughly 480 people times many more times!

I wondered if there weren't a way to turn it into something I like to call a "two-for-one learning experience". By that I mean that one is learning additional useful skills while working on something trivial.

I did some Google searches and found something that caught my eye: bitwise FizzBuzz

I only had some glancing experience with bitwise operators, and I decided this would be my chance to go a little deeper.

The most useful example I found was this JavaScript version that references this post: Which FizzBuzz solution is the most efficient?

### Solve FizzBuzz with a canonical solution.¶

```
x, y = 3, 5
xy = 3 * 5
WORDS = (
FIZZ,
BUZZ,
) = (
"Fizz",
"Buzz",
)
FIZZBUZZ = f"{FIZZ}{BUZZ}"
for i in range(1, 16):
if i % xy == 0:
print(FIZZBUZZ)
elif i % x == 0:
print(FIZZ)
elif i % y == 0:
print(BUZZ)
else:
print(i)
```

### Approach the problem in a different way.¶

Note that there are some patterns to help with a different approach.

The `x`

maps to `FIZZ`

, the `y`

maps to `BUZZ`

and `xy`

maps to `FIZZBUZZ`

.

And the same pattern of `[i, i, Fizz, i, Buzz, Fizz, i, i, Fizz, Buzz, i, Fizz, i, i, FizzBuzz]`

repeats infinitely in an infinite range of positive integers from 1 to infinity.

Imagine an array with the following `[i + 1, FIZZ, BUZZ, FIZZBUZZ]`

.

If we could get a pattern of `0 0 1 0 2 1 0 0 1 2 0 1 0 0 3`

to cycle, then we could do FizzBuzz infinitely with repeating the calculation of the modulo.

```
import itertools as it
from pprint import pprint
from collections import namedtuple
INDENT, WIDTH = 4, 1
x, y = 3, 5
xy = 3 * 5
(
FIZZ,
BUZZ,
) = (
"Fizz",
"Buzz",
)
FIZZBUZZ = f"{FIZZ}{BUZZ}"
WORDS = (FIZZ, BUZZ, FIZZBUZZ)
REPEATING_PATTERN = '0 0 1 0 2 1 0 0 1 2 0 1 0 0 3'.split()
keys = it.cycle(REPEATING_PATTERN)
words_lookup = dict(zip('123', WORDS))
pprint(words_lookup, indent=INDENT, width=min(len(item) for item in WORDS))
pprint(REPEATING_PATTERN, indent=INDENT, width=WIDTH)
# Define a named tuple for prettier display.
Result = namedtuple('Result', 'count key word')
CYCLES = 2
STOP = xy * CYCLES
for count, key in zip(it.count(start=1), keys):
result = words_lookup.get(key, count)
pprint(Result(count, key, result), indent=INDENT)
if count == STOP:
break
```

### Use bitwise operations to achieve `REPEATING_PATTERN = '0 0 1 0 2 1 0 0 1 2 0 1 0 0 3'`

¶

Instead of using base 10 numbers use binary numbers using 2 bits.

This code uses the Format Specification Mini-Language to convert the `int`

types to their binary string equivalents.

```
['{:02b}'.format(int(item))
for item in '0 0 1 0 2 1 0 0 1 2 0 1 0 0 3'.split()]
```

This array of string representations of binary numbers can be joined into one string.

```
''.join('{:02b}'.format(int(item)) for item in '0 0 1 0 2 1 0 0 1 2 0 1 0 0 3'.split())
```

And that string can be turned into an integer after reversing it. It has to be reversed so that the subsequent bitwise operations will work as expected.

```
RADIX = 2 # A radix is the base of a system of numeration
START_NUMBER = int(''.join(
'{:02b}'.format(int(item))
for item in reversed('0 0 1 0 2 1 0 0 1 2 0 1 0 0 3'.split())), RADIX)
START_NUMBER
```

```
x, y = 3, 5
xy = 3 * 5
BITCOUNT = 2
for i in range(xy):
print(START_NUMBER>>(i%xy*BITCOUNT))
# >> Right shift bits by 15 mod count+1 times BITCOUNT of 2
# >> Returns a number with the bits shifted to the right by a number of places.
```

```
x, y = 3, 5
xy = 3 * 5
BITCOUNT = 2
for i in range(xy):
print(START_NUMBER>>((i%xy)*BITCOUNT)&3)
# >> Right shift bits by 15 mod count+1 times BITCOUNT of 2
# >> Returns a number with the bits shifted to the right by a number of places.
# Then perform bitwise AND "bitwise multiplcation" by 3 to get 0, 1, 2, or 3
```

The above intergers can be used as an index to retrieve a value from an array:

```
x, y = 3, 5
xy = 3 * 5
(
FIZZ,
BUZZ,
) = (
"Fizz",
"Buzz",
)
FIZZBUZZ = f"{FIZZ}{BUZZ}"
BITCOUNT = 2
CYCLES = 2
for i in range(xy*CYCLES):
index = START_NUMBER>>((i%xy)*BITCOUNT)&3
choices = [i+1, FIZZ, BUZZ, FIZZBUZZ]
print(choices[index])
```

The above can be refactors like so:

```
x, y = 3, 5
xy = 3 * 5
(
FIZZ,
BUZZ,
) = (
"Fizz",
"Buzz",
)
FIZZBUZZ = f"{FIZZ}{BUZZ}"
BITCOUNT = 2
CYCLES = 2
for i in range(xy*CYCLES): print([i+1, FIZZ, BUZZ, FIZZBUZZ][START_NUMBER>>i%xy*BITCOUNT&3])
```

### Memorizing the start number.¶

810092048 is probably harder to memorize than its hexidecimal representation:

```
hex(810092048)
```

```
for i in range(xy*CYCLES): print([i+1, FIZZ, BUZZ, FIZZBUZZ][0x30490610>>i%xy*BITCOUNT&3])
```