Bitwise Shift Operations

Printable View

02-22-2008
John_L

Bitwise Shift Operations

<< 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
02-22-2008
laserlight

There should be assembly language instructions for left and right shifting.
02-22-2008
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.
02-22-2008
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?
02-22-2008
laserlight

What instructions are available?

Oh, and I have moved this to the Tech board as it is not about C programming.
02-22-2008
tabstop

Quote:

Originally Posted by 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?

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.)
02-22-2008
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.
02-22-2008
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
02-22-2008
tabstop

Quote:

Originally Posted by 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

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!).
02-22-2008
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.

Code:

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.
02-23-2008
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.
02-23-2008
maxorator

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

Code:

shl eax,4 ; unsigned<<4 shr eax,4 ; unsigned>>4 rol eax,4 ; signed<<4 ror eax,4 ; signed>>4
02-23-2008
laserlight

Quote:

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.
02-24-2008
tabstop

Quote:

Originally Posted by 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.

Code:

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.
02-25-2008
maxorator

Quote:

Originally Posted by laserlight

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. :)
02-25-2008
matsp

Quote:

Originally Posted by maxorator

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. :)

No, because a small set of instructions teach you more about how you do things in assembler, rather than becoming a "single operation".

Yes, all modern processors can do multiply, all manners of shifts, and most do divide in one instruction too. But that's not necessarily going to teach you a great deal.

--
Mats
02-25-2008
maxorator

If you need to finish an application in x86 assembly, then you won't be feeling you have too many different instructions, trust me. ;)
02-25-2008
matsp

Quote:

Originally Posted by maxorator

If you need to finish an application in x86 assembly, then you won't be feeling you have too many different instructions, trust me. ;)

That's certainly not what I said.

But if you have to FIRST teach a bunch of students 46 different basic instructions [each with 6-10 different addressing modes], you may spend most of the first two weeks just going through what each instruction does.

But don't you think there really is a few too many ways of doing the same thing in x86:
For most things, you can left-shift a number 4 bits by:

Code:

rol eax, 4 lsl eax, 4 lea eax, [eax*4] lea eax, [eax*4] imul eax, 16

And those are only the most obvious different variants (and not covering MMX/SSE alternatives). The rotate/shift operations are obviously the fastest, and most obvious.

And to the original poster: adding a number to itself should have the same result as a shift - it's a more complex operation in hardware, but aside from that, it's equivalent.

--
Mats
02-25-2008
laserlight

Quote:

And to the original poster: adding a number to itself should have the same result as a shift - it's a more complex operation in hardware, but aside from that, it's equivalent.

The original poster already understood that and stated as such in the original post. The real question is about right shifting.
02-25-2008
maxorator

Quote:

Originally Posted by matsp

But don't you think there really is a few too many ways of doing the same thing in x86:
For most things, you can left-shift a number 4 bits by:

Code:

rol eax, 4 lsl eax, 4 lea eax, [eax*4] lea eax, [eax*4] imul eax, 16

Well there's an optimal way to do everything. rol is the best for normal shifting, imul is good for normal multiplication (yeah, you can multiplicate with other numbers than 1,2,4,8,16... too), lea is good for putting simple calculations to few operations and so on. Every opcode is very useful when used in the right place.