Assignment 1: Finite State Binary Counter
Click here to access the GitHub repository for this assignment.
The idea
This assignment contains two parts: binary puzzles and a binary counter. In this assignment you will use bitwise and Boolean operators to solve basic logical operations on numbers and finitestate machines to model a binary counter. These logic puzzles will help you better understand how binary fits into the daytoday mechanics of computing. In other words, this assignment will help you think about how computers actually look at and understand data that they interact with.
Objectives
By the end of this assignment, you should know:
Part I Binary Puzzles
 how to use bitwise and Boolean operators
 when to use specific numerical Arduino data types
 how to read function signatures
 how to structure Arduino code
 how to automate the build process
Part II Binary Counter
 FSMs
 How to make them
 When to use them
 How they can help a program’s clarity and design
 What an enum is and how it is helpful to a programmer
 how to print to the Serial Monitor
 how to call functions in Arduino C
 how to count to 7 in Binary
 how to use
delay()
The background
Bitwise and Boolean operators
It’s hard to talk about numbers at all without talking about operators. You should be familiar with many of them already: +
, 
, *
, etc. They take one or two numbers and operate on them, changing them. We introduce two new groups of operators: bitwise operators and Booleans ones.
Bitwise operators are operators that act directly on the individual bits of a binary number, whereas Boolean operators operate on the “logical values” that the complete number represents: in Arduino, 0
is a logical false
, and anything else is true
(even 1
).
In a sense, these two groups of operators are very closely related: both operate only on two values (Boolean operators treat everything as either true
or false
, and bitwise operators operate on the underlying bits of numbers which can each only be 0
or 1
), and as you’ll see in a bit, they perform very similar operations on these values. Their main difference is their scope: bitwise operations work on each bit individually, whereas Boolean operations work on the numbers as a whole.
The operations proper
 Bitwise AND (
c = a & b
),c
has1
s in the places where both of the corresponding bits ina
andb
are1
.  Bitwise OR (
c = a  b
),c
has1
s wherever at least one of the corresponding bits ina
andb
is1
.  Bitwise XOR (
c = a ^ b
),c
has1
s wherever one and only one of the corresponding bits in a and b is1
.  Bitwise NOT (
c = ~a
),c
isa
with each bit inverted.  Right shift (
c = a >> b
),c
isa
, with each bit moved lowerb
places.  Left shift (
c = a << b
),c
isa
, with each bit moved higherb
places.  Boolean AND (
c = a && b
),c
is1
if botha
andb
are nonzero.  Boolean OR (
c = a  b
),c
is1
if eithera
andb
are nonzero.  Boolean NOT (
c = !a
),c
is1
only ifa
is0
.
Characters, integers, & longs
Not all numbers are the same length. Because of this it is useful to have several different data types that we can choose from for storing differently sized numbers. In this way we don’t waste space storing small numbers in large spaces. The three data types we will use in this lab are characters (char
: 1 byte), integers (int
: 2 bytes), and longs (long
: 4 bytes), each of which store whole numbers.
By default, all of these values are signed
and can store both positive and negative numbers. Their possible values range from $2^{n1}$ and $2^{n1}  1$, where n
is the number of bits in the data type. unsigned
numbers range from $0$ to $2^{n}1$. e.g. unsigned char, unsigned int and unsigned long.
Two’s complement is used here to store signed
numbers. If you still have confusions about signed
and unsigned
numbers, please read Introduction to Information Representation guide for detailed explanations.
 Characters (
char
) : Smallest addressable unit that can contain integer data. They are 1 byte (8 bits) in length. Signed characters range between128
and+127
.  Integers (
int
) : Standard unit to contain integer data. In C, they contain 2 bytes—16 bits. Signed integers range between32,768
and32,767
.  Longs (
long
) : In Arduino C, they contain 4 bytes or 32 bits. Signed longs range between2,147,483,648
and2,147,483,647
.
Note: Data types in Java or C have different lengths than in Arduino C.
The Assignment
Part I Binary Puzzles
Open the Arduino sketch (in the assign1/binaryPuzzles
folder of your repository) called binaryPuzzles
.

Bit shifting!
Complete the functions
shiftRight
andshiftLeft
.int shiftRight(int num, int n)
: Shiftnum
to the rightn
bits.int shiftLeft(int num, int n)
: Shiftnum
to the leftn
bits.

Bit manipulations!
For each function below, use only the bitwise and Boolean operators listed above (i.e., no
ifthen
tests orwhile
loops are allowed) to write functions that return1
if the input matches the condition given and0
otherwise. You should be able to solve each in one line.int hasAOne(int num)
: At least one bit innum
is a one (Binary Representation).
E.g. 7 is 111 in base 2. Therefore hasAOne(7) should return 1(true).int hasAZero(int num)
: At least one bit innum
is a zero.int leastSigHasAOne(int num)
: At least one bit in the least significant byte(the last byte) ofnum
is a one.int isNegativeInt(int num)
: the integernum
is negative.
Hint: We use Two’s complement to represent signed numbers.int isNegativeLong(long num)
: the longnum
is negative. Remember, in Arduino Clong
s are 4 bytes (32 bits) in length.int isNegativeChar(char num)
: the charnum
is negative. Remember, in Arduino Cchar
s are 1 byte (8 bits) in length.int negate(int num)
: Return the two’s complement negation ofnum
. This function should return a number instead of1
or0
(true or false).
Part II Binary Counter
This part has two components: drawing a FSM, and modeling said FSM on your Arduino.
Setup
 Connect your Arduino
 Open
assign1 / FSM / FSM.ino
The Model
The Studio has useful information for this lab. If you were unable to finish the studio last class we recommend you look it over before starting on the assignment.
Interpreting FSMs and FSAs
Here is the drawing of the studio 1 FSM:
 The circles represent the possible states the machine can be in, and each circle has its own set of instructions.
 The arrows represent the possible movements the machine can make.
 Notice that this FSM has no inputs. It continuously progresses from one state to the next. This is about to change!
Drawing Your Model
 Draw a FSM to model a Binary Counter that can reverse directions
 You are welcome to turn in a picture of one drawn by hand but we recommend this Finite State Machine Designer. This program allows you add, move, and delete states more freely than pen and paper.
 Save the PNG or other image format to your repository in the
assignments/assignment1
 We want to use an input to dictate when we should reverse directions. For this lab, our input will come from the keyboard. In your FSM however, you could represent the input as a binary value: 1 if a key has been pressed, and 0 if not.
 Hint – your model should have 16 states One set of states is for counting up and another set for counting down.
The Program
Transferring FSMs to Code
 Return to
FSM.ino
 Complete the function
nextState()
with a FSM to determine the next state of the machine. Using your FSM drawing as a guide, your FSM should have 16 states and a matching
enum
.
 Using your FSM drawing as a guide, your FSM should have 16 states and a matching
Here is an Example of an Enum in Arduino C:
enum Direction {
North, // North = 0
East, // East = 1
South, // South = 2
West // West = 3
} direction = North;
 Recommended – use
switch
statements to switch between your states usingcases
 Correctly designed
if
statements will also be accepted
 Correctly designed
Here is some pseudocode to demonstrate switch
:
month = 2
switch (month) {
case 1:
print 'January'
break
case 2: // switch to case 2 because month == 2
print 'February'
break // break so other cases won't run
case 3:
print 'March'
break
...
}
Adding the Reverse Button
 Complete the function
checkReverse()
, which reverses the direction of the counter if a key on the keyboard has been pressed. To check if a key on the keyboard has been pressed, you can use Serial.read(). Take a look at the documentation to see how this function works, then use it to complete this method.
 For this lab, we don’t care which key has been pressed, we only care about whether or not any key has been pressed.
 If the user has input something,
checkReverse()
should update the state to reflect this. (Be sure the serial monitor has “No line ending” selected. Other options, like “Newline” will send one or more additional characters and may cause it to reverse multiple times.)
The Final product
Your Output should look close to this:
The checkin
 Commit and push your code (and FSM), then verify in GitHub that it is all there.
 Follow the checklist below to see if you have everything done before demoing your assignment to a TA.
 Part I Binary Puzzles
 All functions work correctly (45 points)
shiftRight(int num, int n)
shiftLeft(int num, int n)
hasAOne(int num)
hasAZero(int num)
leastSigHasAOne(int num)
isNegativeInt(int num)
isNegativeLong(long num)
isNegativeChar(char num)
negate(int num)
 All functions work correctly (45 points)
 Part II Binary Counter
 Drawn FSM (20 points)
 16 states
 correctly models the counter
 FSM (30 points)
 nextState() filled out and working
 16 states
 uses enums
 switches from state to state with switch or if statements
 working counter printed out in the Serial Monitor
 Reverse Button / Lever (5 points)
 can switch the direction of the counter
 Drawn FSM (20 points)
 All of your files are committed
 Part I Binary Puzzles
 Assignment Demo
0 : 000 1 : 001 2 : 010 3 : 011 4 : 100 Reverse 3 : 011 2 : 010 1 : 001 Reverse 2 : 010 3 : 011 Reverse 2 : 010 1 : 001 0 : 000 7 : 111 6 : 110 5 : 101 Reverse 6 : 110 7 : 111 0 : 000 Reverse 7 : 111 6 : 110 5 : 101 4 : 100
 Check out with a TA.