## Description

This lab will review the basics of bitwise operations.

Getting Started

Visit Piazza and download the “bare bones” file lab12.py onto your computer. Open lab12.py in PyCharm

and fill in the following information at the top:

1. your first and last name as they appear in Blackboard

2. your Net ID (e.g., jsmith)

3. your Stony Brook ID # (e.g., 111999999)

4. the course number (CSE 101)

5. the assignment name and number (Lab #12)

Submit your final lab12.py file to Blackboard by the due date and time. Late work will not be graded. Code

that crashes and cannot be graded will earn no credit.

Part I: Extracting Bits (10 points)

Write a function extract_bits_3_9(), which takes a single integer argument named num. The function

extracts bits 3 through 9, returning them as an integer. Remember that the rightmost bit is bit #0.

As an example, suppose num is 1,521,342. In binary, this value is:

101110011011010111110

Let’s highlight bits 3 through 9, inclusive:

101110011011010111110

The function needs to perform various masking and/or shifting operations as needed so that the function will

return:

1010111

The above number written in decimal is 87, which is what the function would ultimately return.

CSE 101 – Spring 2018 Lab #12 Page 1

Remember that all data in a computer is stored in binary format, so it is not necessary for you to tell the computer

to explicitly convert between base 10 and base 2. All integers are represented in binary, but will be printed in

decimal to the screen.

You might find a base conversion website helpful while completing this assignment. Many such websites can be

found with a quick Google search.

Examples:

The function arguments in the examples below are expressed in binary (denoted by the leading 0b), making it

easier to understand the returned result.

Function Call Return Value

extract bits 3 9(0b11100110001001101010010000) 0b1010010

extract bits 3 9(0b1011110001000111110111100111) 0b111100

extract bits 3 9(0b101001110111110010110011000) 0b110011

extract bits 3 9(0b110010111111100001111100) 0b1111

extract bits 3 9(0b101100101001110100011010) 0b100011

extract bits 3 9(0b10010100111101) 0b100111

extract bits 3 9(0b11011000001) 0b1011000

extract bits 3 9(0b1001100100000) 0b1100100

extract bits 3 9(0b1000011111011) 0b11111

extract bits 3 9(0b1111011111100) 0b1011111

Part II: Setting Bits (10 points)

Write a function set bits(), which takes two arguments, in this order:

1. num: a positive integer

2. bits to set: a list of non-negative integers (i.e., positive integers and possibly zero). Each integer is

guaranteed to be less than the number of bits in the binary representation of num.

The function iterates over the bits to set list, treating each value in the list as a bit position in the binary

representation of num. The function then sets a 1 at each such bit position in num.

To make this a little easier to understand, suppose that num is 1101101001101 and bits to set is [0, 2,

4, 7]. This means we want to set the bits at positions 0, 2, 4 and 7 in num to 1. Therefore,

1101101001100

* * * *

is changed to:

1101111011101

* * * *

where the asterisks indicate the four bit positions we are attempting to set.

CSE 101 – Spring 2018 Lab #12 Page 2

Hint: you will need to use both shifting and masking operations to solve this problem. Consider: suppose we

started with the number 1 in binary and shifted it to the left by 5 positions. We would then have 100000.

Presumably this mask would somehow help us to set the 5

th bit of some number to 1.

Examples:

The function arguments in the examples below are expressed in binary (denoted by the leading 0b), making it

easier to understand the returned result.

Function Call Return Value

set bits(0b111001100010100, [0, 9, 13, 5]) 0b111001100110101

set bits(0b11011000000101, [10, 4, 7]) 0b11011010010101

set bits(0b10000100101100100, [0, 3, 5, 6, 15, 16]) 0b11000100101101101

set bits(0b10011100100110011, [0, 1]) 0b10011100100110011

set bits(0b1010011110110011, [10, 13]) 0b1010011110110011

set bits(0b1001011010010, [0, 10, 11, 5]) 0b1111011110011

set bits(0b1011100010011010, [9, 6]) 0b1011101011011010

set bits(0b1111000100100, [3]) 0b1111000101100

set bits(0b101010110000000, [2]) 0b101010110000100

set bits(0b1110111001001111, [2, 7, 12, 14, 15]) 0b1111111011001111

Part III: Decode a Machine Instruction (20 points)

The Fictional KIPS Computer

For this part you will implement a function that decodes machine language instructions of a fictional computer

we will call the KIPS. You should read through the Unit 9 lecture notes before starting this part. KIPS supports

the following instructions that the CPU can execute:

• add dest, op1, op2: Performs an addition. dest is the desination register where the sum of registers op1 and op2 will be saved. (dest = op1 + op2)

• sub dest, op1, op2: Performs a subtraction. dest is the desination register where the difference of

registers op1 and op2 will be saved. (dest = op1 – op2)

• mul dest, op1, op2: Performs a multiplication. dest is the desination register where the product

of registers op1 and op2 will be saved. (dest = op1 * op2)

• div dest, op1, op2: Performs an integer division. dest is the desination register where the quotient

of registers op1 and op2 will be saved. (dest = op1 // op2)

• li dest, immediate: Stores the value immediate in register dest. (i.e.,dest = immediate)

Recall from lecture that an immediate value is simply a constant.

As with the real MIPS computer, the KIPS computer has 10 registers numbered $t0, $t1, …, $t9. In the above

list of instructions, dest, op1 and op2 are registers. immediate is a positive integer (or zero).

Instruction Formats

Every KIPS instruction is exactly 32 bits in length. An arithmetical instruction’s bits are divided up as follows.

CSE 101 – Spring 2018 Lab #12 Page 3

Note that bit #0 is the rightmost bit:

Opcode Destination Register First Operand Second Operand

Bits 24–31 Bits 16–23 Bits 8–15 Bits 0–7

Let’s look at an example instruction to understand this format a little better:

00000111000010010000010000000010

First we divide it into its constituent parts, each of which is one byte, notice:

00000011 00001001 00000100 00000010

This instruction can be expressed more concisely in hexadecimal:

03090402

The leftmost byte, corresponding with bits 24–31, equals 310; the next byte (bits 16–23) equals 910; the next byte

(bits 8–15) equals 410; and the rightmost byte (bits 0–7) equals 210.

The leftmost byte gives the opcode, which is a number in the range 0-4 that indicates which instruction we are

executing:

Opcode Instruction

0 addition

1 subtraction

2 multiplication

3 division

4 load immediate

The number 3 in our sample instruction indicates we are performing a division operation.

The rightmost three bytes, in order from left to right, tell us the destination register (where the result will be saved)

and the two registers where we can find the operands. In this example, the destination register is $t9, and the two

operands are $t4 and $t2. Thus, our instruction:

00000011 00001001 00000100 00000010

really means this:

$t9 = $t4 // $t2

An li instruction has only three parts, instead of four:

Opcode Destination Register Immediate Value

Bits 24–31 Bits 16–23 Bits 0–15

The following example instruction:

00000101 00000110 0000100010011011

CSE 101 – Spring 2018 Lab #12 Page 4

really means this:

li $t6, 2203

because 00001000100110112 = 220310.

Write a function decode instruction() that takes a single integer argument, inst, that represents a KIPS

machine instruction. The function divides the instruction into its constituent parts and returns them in a tuple. In

the case of an arithmetical operation, the tuple returned must have this format:

(opcode, dest, op1, op2)

and for an li instruction it will have this format:

(opcode, dest, immediate)

All values in the returned tuple are integers.

You will need to use bitwise operations, including shifting and masking, to extract the parts of the instruction.

As an example of bitswise operations, let’s suppose for some reason you wanted to extract bits 21–27 of an integer

stored in variable x. Keep in mind that the bits are numbered 0–31, with bit #0 on the right. One way to do this

would be as follows:

mask = 0b00000111111000000000000000000000 # 0b indicates a binary value

x = x & mask

x = x >> 21

Use this as a model to extact the three or four parts of an instruction (as appropriate) and return the required tuple.

If any of the values opcode, dest, op1 or op2 is invalid, the function should return the tuple

(-1, -1, -1, -1). Using the information above, you should be to figure out what are the valid ranges of

these values.

Examples:

The function arguments in the examples below are expressed in hexadecimal (denoted by the leading 0x), making

it easier to see the values of the instruction.

Function Call Return Value

decode instruction(0x01050000) (1, 5, 0, 0)

decode instruction(0x00040407) (0, 4, 4, 7)

decode instruction(0x01010207) (1, 1, 2, 7)

decode instruction(0x00090400) (0, 9, 4, 0)

decode instruction(0x00090005) (0, 9, 0, 5)

decode instruction(0x01050600) (1, 5, 6, 0)

decode instruction(0x04060614) (4, 6, 1556)

decode instruction(0x02000c05) (-1, -1, -1, -1)

decode instruction(0x07020403) (-1, -1, -1, -1)

decode instruction(0x04110752) (-1, -1, -1, -1)

CSE 101 – Spring 2018 Lab #12 Page 5

How to Submit Your Work for Grading

To submit your .py file for grading:

1. Login to Blackboard and locate the course account for CSE 101.

2. Click on “Assignments” in the left-hand menu and find the link for this assignment.

3. Click on the link for this assignment.

4. Click the “Browse My Computer” button and locate the .py file you wish to submit. Submit only that one

.py file.

5. Click the “Submit” button to submit your work for grading.

Oops, I messed up and I need to resubmit a file!

No worries! Just follow the above directions again. We will grade only your last submission.

CSE 101 – Spring 2018 Lab #12 Page 6