macOS Radix Bitshift - practice question

[patent10021]

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

 

[lloyddean]

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.

 

[patent10021]

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.

 

[lloyddean]

"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

 

[patent10021]

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.

 

[lloyddean]

No need to do the 2's compliment work because of the statement -

"Here, the overflow or underflow can be ignored in this multiplication."

 

[patent10021]

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.

 

[lloyddean]

Don't know but perhaps to add uncertainty, doubt and and general confusion.

 

[patent10021]

Don't know but perhaps to add uncertainty, doubt and and general confusion.

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?

 

[lloyddean]

The man is trying to stick it to us

Did you see my edit about a shortcut?

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.

 

[patent10021]

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.

 

[lloyddean]

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.

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.

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.

 

[patent10021]

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.

x    = 127
x(5) = 635

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