Radix Bitshift - practice question

Discussion in 'Mac Programming' started by patent10021, Aug 1, 2019.

  1. patent10021, Aug 1, 2019
    Last edited: Aug 2, 2019

    patent10021 macrumors 68030

    patent10021

    Joined:
    Apr 23, 2004
    #1
    I have a practice question here and even though I'm pretty comfortable with Radix / Bit-shifting I just don't understand this question.


    For an eight-bit integer x represented in two’s complement format, which of the following yields the value of 5x? Here, the overflow or underflow can be ignored in this multiplication.

    a) Shift x to the left by 1 bit, then add the initial value of x to it.
    b) Shift x to the left by 2 bits, then add the initial value of x to it.
    c) Shift x to the right arithmetically by 1 bit, then subtract the initial value of x from it.
    d) Shift x to the right arithmetically by 2 bits, then subtract the initial value of x from it.

    So an eight bit integer would be something like (00011100)2 -> (+28)10
    Two's complement format is negative base2 so it becomes (11100100)2 -> (-28)10
    5x would be (+140)10 or (10001100)2.

    I know how to perform <<, but I just don't understand the wording of this question.

    Thanks
     
  2. lloyddean macrumors 65816

    Joined:
    May 10, 2009
    Location:
    Des Moines, WA
    #2
    With what is given I'd say the answer is likely "b", but given the amount of sleep I get a night my understanding of the question may be wrong.
     
  3. patent10021, Aug 2, 2019
    Last edited: Aug 3, 2019

    patent10021 thread starter macrumors 68030

    patent10021

    Joined:
    Apr 23, 2004
    #3
    Well your answer is correct :) Congrats.

    EDIT: I got it!!!


    If x is (+28)10 we need to get a result of (+140)10

    (+28)10 -> (00011100)2
    Two's complement [invert and add +1] gives us (11100100)2 -> (-28)10
    The result we want is 5x which is (+140)10 or (10001100)2.

    We take (11100100)2 -> (-28)10
    and << 2 times which gives us (10010000)2
    XOR (00011100)2 [do not XOR the 2's complement! XOR the original positive!]

    result = (10001100)2 = (+140)10

    Answer is:
    b) Shift x to the left by 2 bits, then add the initial value of x to it.


    Also, we know << is multiply and >> is divide so it cannot be (c) or (d). So that saves us tons of time.
     
  4. lloyddean macrumors 65816

    Joined:
    May 10, 2009
    Location:
    Des Moines, WA
    #4
    "Here, the overflow or underflow can be ignored in this multiplication."
    X = UNSIGNED 8 BIT
    X = ((X << 2) + X)
    X = ((X * 4) + X)
    X = X * 5
     
  5. patent10021 thread starter macrumors 68030

    patent10021

    Joined:
    Apr 23, 2004
    #5
    Hi

    I'm not sure what you are trying to say? Is the way I calculated it incorrect? I got the correct answer (b) as well.
     
  6. lloyddean macrumors 65816

    Joined:
    May 10, 2009
    Location:
    Des Moines, WA
    #6
    No need to do the 2's compliment work because of the statement -

    "Here, the overflow or underflow can be ignored in this multiplication."
     
  7. patent10021, Aug 2, 2019
    Last edited: Aug 2, 2019

    patent10021 thread starter macrumors 68030

    patent10021

    Joined:
    Apr 23, 2004
    #7
    Ah, got it. Oh well. Same thing right. But yes that can save us time.

    So why then did they even bother mentioning the two's?

    Also is there some kind of shortcut that can give you a clue without performing all the arithmetic? I mean some kind of visual clue that advanced users can spot? I guess if you have binaries up to 256 memorized that is one way.
     
  8. lloyddean macrumors 65816

    Joined:
    May 10, 2009
    Location:
    Des Moines, WA
    #8
    Don't know but perhaps to add uncertainty, doubt and and general confusion.
     
  9. patent10021 thread starter macrumors 68030

    patent10021

    Joined:
    Apr 23, 2004
    #9
    The man is trying to stick it to us ;)

    Notice in my answer I wrote "[do not XOR the 2's complement! XOR the original positive!]".
    I guess that's where I also realized that we didn't need the two's compliment lol

    Did you see my edit about a shortcut?
     
  10. lloyddean, Aug 2, 2019
    Last edited: Aug 2, 2019

    lloyddean macrumors 65816

    Joined:
    May 10, 2009
    Location:
    Des Moines, WA
    #10

    Yes, but given the original question I'm uncertain as to what sort of short cut you're looking for.

    The logic work is pretty straight forward.

    X = UNSIGNED 8 BIT
    X = ((X << 2) + X)
    X = ((X * 4) + X)
    X = X * 5

    Write down the binary pattern of the number being multiplied (or visualize it in your head).
    5 is binary multiple of 2^2, or 4, with 1 left over.
    Move the decimal to the right 2 position filling the empty 2 spaces space with 0 and then add to original value.
    Keep the right 8 bits.
     
  11. patent10021 thread starter macrumors 68030

    patent10021

    Joined:
    Apr 23, 2004
    #11
    Sorry you lost me.

    I was dealing with base2 left-shift, but now you're talking about moving a (decimal) to the right 2 positions?

    Also, are you saying because it's 2² that is the reason you're moving two decimals over?

    Can you please write out the steps you're talking about? I'm pretty new to Radix/Bit-shifting and the only logic I understand is by doing it manually.

    I'd like to see how you are doing it.

    Thank you.
     
  12. lloyddean, Aug 2, 2019
    Last edited: Aug 2, 2019

    lloyddean macrumors 65816

    Joined:
    May 10, 2009
    Location:
    Des Moines, WA
    #12
    Sorry, I knew the moment I'd left the room I said that wrong and as I can't see your face I don't always get where something is not understood.

    Code:
    127 X 5
    
    01111111        = 127
    0111111100      x   4 (THINK OF AS x 4)
    0001111111      + 127
    1001111011      = 635
      01111011      THE TOP 2 BITS ARE DISCARDED
                    AS WE ARE WORKING WITH AN 8 BIT RESULT
    
    
    Apologies,

    Probably better off looking up 8 bit multiplication as I been having trouble explaining things since the last time I was rear-ended - hoping it's just due to pain.
     
  13. patent10021, Aug 2, 2019
    Last edited: Aug 3, 2019

    patent10021 thread starter macrumors 68030

    patent10021

    Joined:
    Apr 23, 2004
    #13
    No worries. I actually know all of the binary operations and notation, but since I'm sorta fresh, sometimes the more elaborate notation is confusing for me. I didn't study CS.

    I wrote your explanation again on paper and I get it now. However I'm not sure where you learned the theory to take that 5 and use its binary multiple of 2² and multiply it by 127. Obviously the math is easy but how did you know how to use the binary multiple of 5? I can do all of this manually using Bitwise/Binary notation, but I did not know this shortcut of using the binary multiple of 5. What would I search for on Youtube to understand the theory behind that?

    Lastly, how can I infer the answer is (b) since no left-shifting was performed in your work? I'm thinking they actually want use to work through it manually because otherwise there is no way to know how many left-shifts are required right? Or does the binary multiple of 5 (2) tell us that there will be two left-shifts?
    b) Shift x to the left by 2 bits, then add the initial value of x to it.


    p.s. I hope you get better.


    Code:
    x    = 127
    x(5) = 635
    
    01111111     = 127
    0111111100   x 508 (127 x 2²)
    0001111111   + 127 *leading padding
    1001111011   = 635 (127 x 5)
    
     

Share This Page

12 August 1, 2019