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.

In [1]:
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)
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz

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.

In [2]:
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
{   '1': 'Fizz',
    '2': 'Buzz',
    '3': 'FizzBuzz'}
[   '0',
    '0',
    '1',
    '0',
    '2',
    '1',
    '0',
    '0',
    '1',
    '2',
    '0',
    '1',
    '0',
    '0',
    '3']
Result(count=1, key='0', word=1)
Result(count=2, key='0', word=2)
Result(count=3, key='1', word='Fizz')
Result(count=4, key='0', word=4)
Result(count=5, key='2', word='Buzz')
Result(count=6, key='1', word='Fizz')
Result(count=7, key='0', word=7)
Result(count=8, key='0', word=8)
Result(count=9, key='1', word='Fizz')
Result(count=10, key='2', word='Buzz')
Result(count=11, key='0', word=11)
Result(count=12, key='1', word='Fizz')
Result(count=13, key='0', word=13)
Result(count=14, key='0', word=14)
Result(count=15, key='3', word='FizzBuzz')
Result(count=16, key='0', word=16)
Result(count=17, key='0', word=17)
Result(count=18, key='1', word='Fizz')
Result(count=19, key='0', word=19)
Result(count=20, key='2', word='Buzz')
Result(count=21, key='1', word='Fizz')
Result(count=22, key='0', word=22)
Result(count=23, key='0', word=23)
Result(count=24, key='1', word='Fizz')
Result(count=25, key='2', word='Buzz')
Result(count=26, key='0', word=26)
Result(count=27, key='1', word='Fizz')
Result(count=28, key='0', word=28)
Result(count=29, key='0', word=29)
Result(count=30, key='3', word='FizzBuzz')

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.

In [3]:
['{:02b}'.format(int(item)) 
 for item in '0 0 1 0 2 1 0 0 1 2 0 1 0 0 3'.split()]
Out[3]:
['00',
 '00',
 '01',
 '00',
 '10',
 '01',
 '00',
 '00',
 '01',
 '10',
 '00',
 '01',
 '00',
 '00',
 '11']

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

In [4]:
''.join('{:02b}'.format(int(item)) for item in '0 0 1 0 2 1 0 0 1 2 0 1 0 0 3'.split())
Out[4]:
'000001001001000001100001000011'

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.

In [5]:
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
Out[5]:
810092048
In [6]:
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. 
810092048
202523012
50630753
12657688
3164422
791105
197776
49444
12361
3090
772
193
48
12
3
In [7]:
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
0
0
1
0
2
1
0
0
1
2
0
1
0
0
3

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

In [8]:
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])
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
22
23
Fizz
Buzz
26
Fizz
28
29
FizzBuzz

The above can be refactors like so:

In [9]:
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])
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
22
23
Fizz
Buzz
26
Fizz
28
29
FizzBuzz

Memorizing the start number.

810092048 is probably harder to memorize than its hexidecimal representation:

In [10]:
hex(810092048)
Out[10]:
'0x30490610'
In [11]:
for i in range(xy*CYCLES): print([i+1, FIZZ, BUZZ, FIZZBUZZ][0x30490610>>i%xy*BITCOUNT&3])
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
22
23
Fizz
Buzz
26
Fizz
28
29
FizzBuzz