Bitwise Shift Operations

[John_L]

<< and >>, I understand how they work...sort of. I'm curious how to bring this high level command down to a low level like assembler.

I've figured out how to shift left in assembler using a loop, and adding the number to itself as many times as you'd like the bits shifted (i.e. 1, shifts 1, 2 shifts 2 etc..). Because you multiply the number by 2, which translates easing into addition arithmatic

But How do I go about shifting right, especially with no divide operator. To divide a number by 2 you need to know what (1/2)(number) is...and what if it's uneven? Can anyone help me understand this so I can translate it to low level operations. Thanks

[laserlight]

There should be assembly language instructions for left and right shifting.

[tabstop]

As mentioned, bit shifting is pretty much the definition of a low-level operation.

But if you absolutely positively have to do it via arithmetic, you'll need another register -- an accumulator, really. Start with your number over here and 0 in your accumulator. Subtract 2 from the the number and add 1 to the accumulator; keep doing so until your number goes negative. And if you need to bit shift two, you subtract four, etc.

This seems really slow, and that's because it is.

[John_L]

LaserLight:

nah, i'm using the LC3 Simulator which is a piece of junk so we learn the fundamentals I guess.

http://en.wikipedia.org/wiki/LC-3

I'm stuck trying to write a small program that shifts the bits in one register by 4, into another register after zero'ing it out. So register1 gets shifted to the left by 4 bits, then register0 recieves those bits that were "shifted out" of register1. I was going to just use a mask but the bits stored in register0 have to be at the backend, i.e. if I used a mask, I would have to shift them right until they reached the end.

Tabstop:

ok, that makes sense, so your accumulator is the result, because this way it's always a non floating point number. One question though, Say your next subtraction takes you into the negative with your number, do you still increment your accumulator? So i'm at 2 and my accumulator is at 3, when i subtract (let's say 4) from 2 I go into the negative, would I increase my accumulator to 4, or leave it at 3?

[laserlight]

What instructions are available?

Oh, and I have moved this to the Tech board as it is not about C programming.

[tabstop]

LaserLight:

nah, i'm using the LC3 Simulator which is a piece of junk so we learn the fundamentals I guess.

http://en.wikipedia.org/wiki/LC-3

I'm stuck trying to write a small program that shifts the bits in one register by 4, into another register after zero'ing it out. So register1 gets shifted to the left by 4 bits, then register0 recieves those bits that were "shifted out" of register1. I was going to just use a mask but the bits stored in register0 have to be at the backend, i.e. if I used a mask, I would have to shift them right until they reached the end.

Tabstop:

ok, that makes sense, so your accumulator is the result, because this way it's always a non floating point number. One question though, Say your next subtraction takes you into the negative with your number, do you still increment your accumulator? So i'm at 2 and my accumulator is at 3, when i subtract (let's say 4) from 2 I go into the negative, would I increase my accumulator to 4, or leave it at 3?

The easy way is to say: which one gives you the right answer? Let's say I start with 1111 and I want to shift two to the right:
1111 0000 (start)
1011 0001 (-4)
0111 0010 (-4)
0011 0011 (-4)
The next shift puts me at -1, a negative number. I want the answer to be 0011, so I should stop. (Notice that if I add 1 to get 10000, I [i]do[/] need to keep going when I get 0 in my register.)

[John_L]

NOT, AND => All other Bitwise operations via these two
ADD => subtraction, multiply via this one

Than some standard ones

LD => load value into register
ST => store value in variable
JSR => jump to subroutine
LEA => load adress
etc...

There's an appendix with all the commands through the link I posted.

[John_L]

I thought:

1111 0000 => shift right 4 bits would be 0000 1111

I have a 16 bit register with the first 4 bits needing to be shifted all the way to the back,
1111 0000 0000 0000 => 0000 0000 0000 1111. Because xF000 => x000F is the proper shift i'm looking for.

So this means, I have to subtract by 24??? Which is right I guess, cause if the 1's are that high up in the 16 bit register the number is fairly large. I'm just making sure i'm on the right track. Thanks

[tabstop]

I thought:

1111 0000 => shift right 4 bits would be 0000 1111

I have a 16 bit register with the first 4 bits needing to be shifted all the way to the back,
1111 0000 0000 0000 => 0000 0000 0000 1111. Because xF000 => x000F is the proper shift i'm looking for.

So this means, I have to subtract by 24??? Which is right I guess, cause if the 1's are that high up in the 16 bit register the number is fairly large. I'm just making sure i'm on the right track. Thanks

I was just doing a 4-bit example. If you need to right-shift 12 bits, you need to subtract 2^12 = 4096. (IOW, your subtraction must not touch the 12 right-most bits that we're going to throw away; it should only look at the bits that are going to be "kept".)

Also, be careful about starting with a negative number! (1) Your test may need to wait until your number becomes positive, then check for negative, and (2) do you fill in with the sign bit or not (in C at least that's implementation defined, and since you're the implementor, you get to choose! Yay!).

[John_L]

This seems a lot harder than I initially thought. There doesn't seem to be any other way I can think of to get the first four bits from register1, into the last 4 bits of register0 by shifting register1 to the left 4 bits.

BEFORE:
a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 => register0
b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15 => register1

AFTER:

0 0 0 0 0 0 0 0 0 0 0 0 b0, b1, b2, b3                          => register0 (it's been zero'd out)
b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15 0 0 0 0 => register1

The only method I can think of, is by using a mask of xF000 and using an "AND" operation on the original register1 to get:

         register1
AND   mask
         ------------
         new value (which needs to be bit shifted right and stored in register0 )

Result:

b0, b1, b2, b3 0 0 0 0 0 0 0 0 0 0 0 0                          => register0
b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15 0 0 0 0 => register1

Now what...?

Then i'm stuck as to how to properly get the final result for register0 that I need.

[DavidP]

You are using the LC3? Wow....do you go to BYU because I do and we used the LC3 in a couple of the early programming classes.

In fact, in one of our classes we designed the complete LC3 processor in Verilog and loaded it onto an FPGA chip and simulated it running.

[maxorator]

What good is an assembly language that doesn't allow you to do most of what the processor supports!?

shl eax,4 ; unsigned<<4
shr eax,4 ; unsigned>>4
rol eax,4 ;   signed<<4
ror eax,4 ;   signed>>4

[laserlight]

What good is an assembly language that doesn't allow you to do most of what the processor supports!?

You need to read the thread. This is an assembly language for teaching purposes. The processor, if it were actually implemented, does not support left and right shifts (unless you use LC-3b). The assembly language syntax example you gave is invalid since it not LC-3.

[tabstop]

This seems a lot harder than I initially thought. There doesn't seem to be any other way I can think of to get the first four bits from register1, into the last 4 bits of register0 by shifting register1 to the left 4 bits.

BEFORE:
a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 => register0
b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15 => register1

AFTER:

0 0 0 0 0 0 0 0 0 0 0 0 b0, b1, b2, b3                          => register0 (it's been zero'd out)
b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15 0 0 0 0 => register1

The only method I can think of, is by using a mask of xF000 and using an "AND" operation on the original register1 to get:

         register1
AND   mask
         ------------
         new value (which needs to be bit shifted right and stored in register0 )

Result:

b0, b1, b2, b3 0 0 0 0 0 0 0 0 0 0 0 0                          => register0
b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15 0 0 0 0 => register1

Now what...?

Then i'm stuck as to how to properly get the final result for register0 that I need.

Well, what are you getting? If you were doing what we were talking about before, then if you started with
123456789abcdefg (not actual values, obviously, just to keep track of where everything is)
then your register should now have
000056789abcdefg
and the accumulator would have
0000000000001234

So the accumulator is done; and if for some strange reason you're supposed to keep the shifted bits "in order as they were shifted off" you'd have to shift the register over 16-n bits (where n is the number you shifted). And then you can swap register and accumulator, if they're supposed to be in the other order.

[maxorator]

You need to read the thread. This is an assembly language for teaching purposes. The processor, if it were actually implemented, does not support left and right shifts (unless you use LC-3b). The assembly language syntax example you gave is invalid since it not LC-3.

If it needs tons of operations for stuff that x86 does with one opcode, isn't it then a very bad assembly language for learning purposes? If you'd leave the float/xmm operations out then x86 itself is a very simple assembly language. Why would someone implement an assembly language without a processor anyway?

I am just curious.