Thread: Bitwise Shift Operations

  1. #1
    Registered User
    Join Date
    Sep 2007
    Posts
    119

    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

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    There should be assembly language instructions for left and right shifting.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  4. #4
    Registered User
    Join Date
    Sep 2007
    Posts
    119
    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?
    Last edited by John_L; 02-22-2008 at 01:20 PM.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    What instructions are available?

    Oh, and I have moved this to the Tech board as it is not about C programming.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by John_L View Post
    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.)

  7. #7
    Registered User
    Join Date
    Sep 2007
    Posts
    119
    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.

  8. #8
    Registered User
    Join Date
    Sep 2007
    Posts
    119
    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

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by John_L View Post
    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!).

  10. #10
    Registered User
    Join Date
    Sep 2007
    Posts
    119
    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.

  11. #11
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    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.
    My Website

    "Circular logic is good because it is."

  12. #12
    Reverse Engineer maxorator's Avatar
    Join Date
    Aug 2005
    Location
    Estonia
    Posts
    2,318
    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
    "The Internet treats censorship as damage and routes around it." - John Gilmore

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by John_L View Post
    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.

  15. #15
    Reverse Engineer maxorator's Avatar
    Join Date
    Aug 2005
    Location
    Estonia
    Posts
    2,318
    Quote Originally Posted by laserlight View Post
    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.
    "The Internet treats censorship as damage and routes around it." - John Gilmore

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. still problems with ceasar shift
    By trevordunstan in forum C Programming
    Replies: 2
    Last Post: 09-14-2008, 01:49 AM
  2. bitwise operations with double
    By henry_kay in forum C Programming
    Replies: 2
    Last Post: 10-03-2007, 04:57 AM
  3. Bitwise operations
    By sh3rpa in forum C++ Programming
    Replies: 16
    Last Post: 09-25-2007, 06:32 PM
  4. bitwise operations
    By black_watch in forum C++ Programming
    Replies: 9
    Last Post: 03-24-2007, 04:48 AM
  5. bitwise operations
    By andrew_tucker in forum C Programming
    Replies: 2
    Last Post: 11-28-2002, 12:46 AM