$25
CS061–Lab 7 Advanced Bit Manipulation Solved
The purpose of this lab is to give you some experience in doing some advanced bit manipulation techniques, making use of both left- and right-shifting.
1 Our Objectives for This Week
1. Exercises 01 – Review & extend assignment 4
2. Exercise 02 – Counting bits
3. Exercise 03 – Right Shift
REMEMBER: ALL your programs must now be written as subroutines!!
Call your subroutines with the JSRR instruction ( it works with subroutines located anywhere in memory)
And remember to include all four steps of subroutine construction, being especially careful to back up & restore R7 ( or your program won’t work and you won’t be able to figure out why!)
Exercise 01
Hey, remember that Programming Assignment (assn 4) you are working on? Sweet, huh? Let's reverse it:
Specs:
1. The main code block (which is basically a test harness) should just invoke subroutine 1, and then subroutine 2, using the register value created by sub 1 to set up input for sub 2.
2. Subroutine 1: This subroutine will just take a hard-coded (.FILL) value, and load it into a register of your choice.
3. (In the test harness) add 1 to the number and invoke subroutine 2:
4. Subroutine 2: Using your chosen output register from sub 1 as an input register for sub 2, print the new value out to the console as a decimal number ( i.e. the inverse of Programming Assignment 04).
Work out the algorithm for yourself by studying the algorithm we give you for assn 4, and then working "backwards" from that.
ALWAYS, ALWAYS, WRITE OUT YOUR ALGORITHM - express it in bullet points, in pseudo-code, in C++, however you like - but DO IT!
5. Just for fun, try entering the number #32767 into this program; what do you get?
Exercise 02
Write a subroutine that counts the number of binary 1’s in the value stored in a given register ( this is part of a technique known as a "parity check" - go look it up!)
Specs:
1. The main code block (test harness) should ask the user to input a single character at the keyboard.
2. The input should be “passed” as a parameter to the subroutine (i.e. the input character is copied to a register that is available to the subroutine).
3. The subroutine should “return” the number of binary 1’s in the input character in another register (i.e. it counts the number of 1’s in the original character, and stores that value in a "return" register).
4. The main code block should then print the result in a reasonably intelligent format: Example: The ASCII code for a semi-colon (‘;’) is x3B == b0000 0000 0011 1011 which contains five binary 1's, so your program will output:
The number of 1’s in ';' is: 5
Hint: We will test this exercise only with asciii characters - i.e. the maximum possible number of 1's will be 8, i.e. your output will always be a single digit numeric character.
Exercise 03
You have to read & understand this exercise, but you don't need to code it - you just need to show your TA the algorithm you would use (use the outline below).
Ok, here we go. Are you feeling advanced? You look advanced. You’re awesome! You can totally do this! Ready? Ok!
Build a subroutine that takes, as a parameter, the value of a register and right-shifts it by one bit, losing the trailing bit, and filling in the empty leading bit with 0:
Example:
(R1) ← xABCD ; (b1010 1011 1100 1101)
[call the right-shift subroutine]
[now (R1) == x55E6 == b0101 0101 1110 0110]
Note how we shifted-in a 0 when we did the right-shift, and "lost" the 1 in the lsb?
This is called a logical right shift; there are two other variations, the arithmetic right-shift (which maintains the sign bit rather than always shifting-in a 0 to the msb); and a right-rotate, which shifts in to the msb the bit shifted out of the lsb. For the moment, we will just deal with the logical right-shift.
Discussion:
Alright, let’s think about this thing. When we left-shift, we are doubling the number (aka: multiplying it by two - aka: adding it to itself - aka: ADD R1, R1, R1), right? So if left-shift is multiplication, then what might right-shift be?
Yep, you guessed it: Division. If you left-shift the number 2, you get 4. If you right-shift 4, you go back to having 2. So, division. Right. Got it.
“How in blazes are we suppose to right shift?!” the TA said rhetorically.
[Whacky Student]: If left-shifting is ADDing a number to itself, then right-shift must be subtracting it from itself, right?
[TA]: *blank stare*
[Less Whacky Student]: *whispers* “Dude, that would make it zero.”
[Whacky Student]: *facepalm*
Well, sadly, there is no super-simple way to perform a binary right-shift. Still, it's not insanely difficult. Let’s think about it:
● Left-shifting is short and sweet: add the number to itself.
● Right-shifting is not quite as simple. There is no way to directly do it.
● Hmm… how else can we mess around with the bits? We can shove them left and shift-in a 0 every time to the lsb (that’s a logical left-shift)… but what if instead we rotated the bits (i.e. take the msb being shifted out, and shift it in as the new lsb)?
Hmmm:
● Given the 4-bit (unsigned) number xC == b1100 == #12 (UNsigned magnitude)
● [Rotate left, noting that msb is 1, which gets rotated in to the lsb]
● Now we have b1001 == #9
● [Rotate left, noting that msb is 1, which gets rotated in to the lsb]
● Now we have b0011 == #3
● [Rotate left, noting that msb is 0, which gets rotated in to the lsb]
● Now we have b0110 == #6 - note that msb is now 0
Ok, this is boring. Let’s stop.
Hey wait! Oh my gosh!
We have 12/2 == 6 now! How’d that happen?!?
[This is where you, the Less Whacky Student, fill in the blanks ☺]
Note: This only works for unsigned representation. How could it be made to work for two's complement representation?
