I'm working on the LC3 simulator and I am not sure how to perform a bitwise shift. I would like to shift the contents of a 16 bit register four places to the left. This is simple enough in high level languages but i'm not sure about the steps involved. Any ideas?

ex) 1, 2, 3, 4, 5, 6, 7, 8 => 5, 6, 7, 8, 0, 0, 0, 0 (just a representation)

From what I know about << bitwise shift operation, it multiplies the number by 2. So if I wanted to shift it by 4 bits, it would multiply by 2^n (n=4) giving me 16. I tried writing a program with a subroutine that loops 16 times, adding the number to itself in the loop. But I just get a wrong result due to overflow perhaps.

ex) 1, 2, 3, 4, 5, 6, 7, 8 => 5, 6, 7, 8, 0, 0, 0, 0 (just a representation)

From what I know about << bitwise shift operation, it multiplies the number by 2. So if I wanted to shift it by 4 bits, it would multiply by 2^n (n=4) giving me 16. I tried writing a program with a subroutine that loops 16 times, adding the number to itself in the loop. But I just get a wrong result due to overflow perhaps.

Shifting in assembly is quite easy:

mov eax, 10d

shl eax, 1 ; 20d (10100b)

shl eax, 2 ; 40d (101000b)

shl eax, 3 ; 80d (1010000b)

shl eax, 4 ; 160d (10100000b)

If you add the content to itself - you shift the value each time by 1. So if you want to shift 4 bits you would need to add the value to itself 4 times.

mov eax, 10

add eax, eax ; 10d + 10d = 20d (10100b)

add eax, eax ; 20d + 20d = 40d (101000b)

add eax, eax ; 40d + 40d = 80d (1010000b)

add eax, eax ; 80d + 80d = 160d (10100000b)

mov eax, 10d

shl eax, 1 ; 20d (10100b)

shl eax, 2 ; 40d (101000b)

shl eax, 3 ; 80d (1010000b)

shl eax, 4 ; 160d (10100000b)

If you add the content to itself - you shift the value each time by 1. So if you want to shift 4 bits you would need to add the value to itself 4 times.

mov eax, 10

add eax, eax ; 10d + 10d = 20d (10100b)

add eax, eax ; 20d + 20d = 40d (101000b)

add eax, eax ; 40d + 40d = 80d (1010000b)

add eax, eax ; 80d + 80d = 160d (10100000b)

So don't add the value to itself 16 times then, only 4? The instruction set on the LC3 simulator is very limited, and I'm only at a beginner level. I'm gonna keep to the loop and just add the value to itself 4 times. Hopefully that works...

What about if I were to shift to the right, how would I divide it properly?

What about if I were to shift to the right, how would I divide it properly?

Number Systems 101:

Binary shifts can be thought of as a div or mul by some power of 2.

Binary operations are all about the number 2 in fact - you're working with a Base 2 number system, thus the name Binary.

for each bit position of shift to the left, its multiply by 2 (or add if you like)

for each bit position of shift to the right, its divide by two.

So to shift to the right by 4 binary places, we must /2 four times.

ie /2/2/2/2

This is the same as saying 'divide by 2 to the power of N" where N is the number of places.

2 to the power of 4 is 2*2*2*2 , which is 16.

You can simply divide by 16, and you have shifted 4 places to the right !!

I hope this helps to clarify things.

Binary shifts can be thought of as a div or mul by some power of 2.

Binary operations are all about the number 2 in fact - you're working with a Base 2 number system, thus the name Binary.

for each bit position of shift to the left, its multiply by 2 (or add if you like)

for each bit position of shift to the right, its divide by two.

So to shift to the right by 4 binary places, we must /2 four times.

ie /2/2/2/2

This is the same as saying 'divide by 2 to the power of N" where N is the number of places.

2 to the power of 4 is 2*2*2*2 , which is 16.

You can simply divide by 16, and you have shifted 4 places to the right !!

I hope this helps to clarify things.

I think what John said is that this LC3 simulator and has no MUL or DIV instructions. I don't really know how to do a divison without DIV or Shifts.

Its possible to search for the division factor through the repeated subtraction of a growing integer. This is a slow process, but will work on a machine with no div or shift.

Lets call the growing divisor X and the iteration counter Y.

In this example, I will assume that we want to divide by 2 - we want Y to be 2.

Start by repeatedly subtracting the value X=2 until we can't anymore.

How many times did we do this? We did it Y times.

Now increase the X value to 3 and repeat the process.

Do this until we find the X value that yields a Y value of 2.

X is our answer.

Lets call the growing divisor X and the iteration counter Y.

In this example, I will assume that we want to divide by 2 - we want Y to be 2.

Start by repeatedly subtracting the value X=2 until we can't anymore.

How many times did we do this? We did it Y times.

Now increase the X value to 3 and repeat the process.

Do this until we find the X value that yields a Y value of 2.

X is our answer.

Its possible to do with shifts, but you need to have a compare function and subtract.

You can go the other way to - accumulative approach to division, by repeatedly adding a value - both methods are perfectly valid, so subtraction is not required, I just mentioned the way that suits me - I see multiplications as a series of additions, and divisions as a series of subtractions.

Choose your own adventure :)

Choose your own adventure :)

I think an interesting aspect of doing shifts in assembler is the carry flag because this is something that high level languages cannot access.

If you shift a byte left once the top bit will fall off and be lost in a high level language. In assembler the bit will fall into the carry flag so you can catch it. Then when you shift the neighbouring byte left the bit can be copied into the bottom. Thus you can shift a word or a whole array of bytes left by one bit.

This is very convenient and quite simple in assembler but more complicated in a high level language where you have to explicitly remember the bit value and OR it in afterwards.

I'll leave it to someone else to provide an example in x86 assembler ;)

If you shift a byte left once the top bit will fall off and be lost in a high level language. In assembler the bit will fall into the carry flag so you can catch it. Then when you shift the neighbouring byte left the bit can be copied into the bottom. Thus you can shift a word or a whole array of bytes left by one bit.

This is very convenient and quite simple in assembler but more complicated in a high level language where you have to explicitly remember the bit value and OR it in afterwards.

I'll leave it to someone else to provide an example in x86 assembler ;)