shifts?

[Dillinger4]

Does anyone know how i can figure out binary shifts without
having to get the bit pattern? I thought i could use (number to shift) * 2^(places to shift) for << shifts and (number to shift) / 2^(places to shift) for >> shifts and >>> shifts. But the results i have been getting are just plain inconsistent. I have to take the Java Programmer certification exam soon and Sun always throws in shift questions.

Desen't work
64 = 0100 0000
64 << 1 = -128
64 * 2^1 = 128 not -128

Works
40 = 0010 1000
40 << 1 = 80
40 * 2^1 = 80

Works
-128 = 1000 0000
-128 >> 2 = -32
-128 /2^2 = -32

Dosen't work
-128 = 1000 0000
-128 >>> 3 = 32
-128/2^2 = -32 not 32

[Alphanos]

What kind of variable types are you supposed to be assuming? A variable that ranges -128 to 127?

[Guv]

You first of all need to understand what you mean by shifting. At the machine language level there are three basic types of shifts.

• Logical shifts, which lose bits. A left shift loses bits on the left and supplies zero bits on the right. A right shift loses bits on the right and supplies zero bits on the left. Logical shifts are not always equivalent to multiplying or dividing by a power of two.
  
• Circular shifts, which preserve all bits. A left circular shift takes bits lost at the left and puts them on the right. Right circular shifts take bits lost at the right and puts them on the left. It is obvious that these shifts are often not equivalent to multiplying or dividing by a power of two.
  
• Algebraic or numeric shifts, which are equivalent to multiplying by a positive (left shift) or negative (right shift) power of two. Right numeric shifts lose bits at the right and generate bits equal to the sign bit at the left. Left numeric shifts are like left logical shifts, except that they cause overflow if the bit shifted out of the sign bit is not equal to the bit shifted into the sign bit.

I am not sure what shifts are available as machine language commands on an Intel CPU.

After understanding the above, you have to consider the maximum number of bits in the register being shifted. This is a critical consideration for most computer operations. You also must consider the notation for negative values. The following assumes complement two binary (the standard for a CPU), not signed magnitude (standard for people).

Your examples are very confusing to me. For example, I do not understand why you said that 64*2 = 32. I will ignore your examples and give some of my own. I believe that the logical and circular shifts need no further explanation or examples.

Numeric shifts in an 8-bit signed register are as follows.

0001 1010 is +26.
— Shifted left 1 it is 0011 0100, which is 52 (same as multiply by 2).
— Shifted left 2 it is 0110 1000, which is 104 ( same as multiply by 4).
— Shifted left 3 it is 1101 0000, which is overflow (same as multiply by 8). 127 is maximum.
— Shifted right 1 it is 0000 1101, which is 13 (same as divide by 2 or multiply by ½).
— Shifted right 2 it is 0000 0110, which is 6 (same as integer divide by 4 or multiply by 1/4)
— Shifted right 3 it is 0000 0011, which is 3 (same as integer divide by 8 or multiply by 1/8)

Note that in a 16-bit signed register, +26 = 0000 0000 0001 1010
— Shifted left 3, it is 0000 0000 1101 0000, which is 208 (same as multiply by 8).

1110 0110 is - 26
— Shifted left 1 it is 1100 1100, which is -52 (same as multiply by 2)
— Shifted left 2 it is 1001 1000, which is -104 (same as multiply by 4)
— Shifted left 3 it is 0011 0000, which is overflow (same as multiply by 8) -128 is maximum.
— Shifted right 1 it is 1111 0011, which is -13 (same as divide by 2 or multiply by ½)
— Shifted right 2 it is 1111 1001, which is -6 (same as integer divide by 4 or multiply by 1/4)

Note that in a 16-bit signed register, -26 is 1111 1111 1110 0110
— Shifted left 3 it is 1111 1111 0011 0000, which is -208 (same as multiply by 8)

You must always consider the word (register) length when analyzing computer operations.

BTW: I always evaluate complement two binary by assigning a negative value to the high order (sign) bit. Also, to change sign of a value, replace all zero bits by one bits and vice versa. Then add a one bit at the low order end, carrying left as required.

[Dillinger4]

Sorry i had to trash that thread Alphanos i was giving myself a headache. Yes Guv.... Thanks for replying. Your wisdom is much needed.

Logical shifts, which lose bits. A left shift loses bits on the left and supplies zero bits on the right. A right shift loses bits on the right and supplies zero bits on the left. Logical shifts are not always equivalent to multiplying or dividing by a power of two.

Yes. That would be the behavior of the << and >>> operators i am currently working with. I wouldn't say that they lose bits though. 0 bits are padded in.

Right numeric shifts lose bits at the right and generate bits equal to the sign bit at the left.

That would be the >> "singed shift" i am using also.

Your examples are very confusing to me. For example, I do not understand why you said that 64*2 = 32. I will ignore your examples and give some of my own. I believe that the logical and circular shifts need no further explanation or examples.

Im sorry that was a typo. But looking at some of youre examples we seem to be on the same level of thought.

Taking your first example that you presented.

0001 1010 is +26.
— Shifted left 1 it is 0011 0100, which is 52 (same as multiply by 2).

0001 1010 = 26
26 << 1 = 52 (0011 0100)
26 * 2^1

Taking your second example

— Shifted left 2 it is 0110 1000, which is 104 ( same as multiply by 4).

0001 1010 = 26
26 << 2 = 104 (0110 1000)
26 * 2^2

What i am trying to do is find some way of doing shifts without having to gett a numbers bit pattern or binary string. The formula
(number to shift) * 2^ (places to shift) or (number to shift) / 2^ (places to shift) seems to work in certian instances but not others.

For instance 64 shifted 1 left should equal -128 but applying that formula i come up with 128 which is correct but that's not the value of the binary string after the shift has taken place.

64 = 0100 0000
64 << 1 = -128
64 * 2^1 = 128 not -128

Same when i try to apply for -112
-112 = 1001 0000
-112 >>> 1 = 72
-112 / 2^1 = -56 not 72

But now when i apply a signed shift to -112 the correct value is obtained.
-112 = 1001 0000
-112 >> 1 = -56
-112 / 2^1 = -56

Is there a way that one can look at a problem and apply a formula to achieve the desired result with out having to convert the value to binary, then shift then convert back?

[Guv]

Numeric (algebraic) shifts are exactly equivalent to multipying or dividing by a power of two. Just as multiplication can cause overflow, a numberic left shift can cause overflow.

You cannot simulate logical shifts by multiplication or division.

It seems to me that you are not paying attention to word (register) length. Left numeric shift of 64 causes overflow if you are working with 8-bit signed complement two data. It results in 128 if working with items more than 8 bits long.

VB is just not the language for implementing shifts. I think C & C++ allow interspersed assembly language. C or assembly language is the way to go for shifting data.

You might be able to do what you desire by using arrays and table lookup logic.

[jim mcnamara]

FWIW
I disagree. You can implement shifts and C macros with arithmetic operations and memory moves. Here are examples. They are clunky but they work.

This is how you do it - you have to use CopyMemory in VB:

Private Declare Sub CopyMemory Lib "kernel32.dll" (Destination As Any, Source As Any,ByRef Length As SIZE_T )

----------for integers 16 bit shift
Public Function vbShiftLeftWord(ByVal Value As Long, _
                                Count As Integer) As Long
Dim i As Integer

  ' Cut on 16-bit range
  vbShiftLeftWord = LOWORD(Value)

  For i = 1 To Count
    vbShiftLeftWord = vbShiftLeftWord * 2
  Next

  ' Cut on 16-bit range
  vbShiftLeftWord = LOWORD(vbShiftLeftWord)

Public Function vbShiftRightWord(ByVal Value As Long, _
                                 Count As Integer) As Long
Dim i As Integer

  ' Cut on 16-bit range
  vbShiftRightWord = LOWORD(Value)

  For i = 1 To Count
    vbShiftRightWord = vbShiftRightWord \ 2
  Next

End Function

' C macros & casts in VB -------------------------------------
Public Function MAKELONG(wLow As Long, wHigh As Long) As Long
  MAKELONG = LOWORD(wLow) Or (&H10000 * LOWORD(wHigh))
End Function
Public Function MAKELPARAM(wLow As Long, wHigh As Long) As Long
  MAKELPARAM = MAKELONG(wLow, wHigh)
End Function

Public Function MAKEWORD(wLow As Long, wHigh As Long) As Long
  MAKEWORD = LOBYTE(wLow) Or (&H100& * LOBYTE(wHigh))
End Function
Public Function LOWORD(dwValue As Long) As Integer
  MoveMemory LOWORD, dwValue, 2
End Function
Public Function HIWORD(dwValue As Long) As Integer
  MoveMemory HIWORD, ByVal VarPtr(dwValue) + 2, 2
End Function

Public Function LOBYTE(dwValue As Long) As Byte
  MoveMemory LOBYTE, LOWORD(dwValue), 1
End Function
Public Function HIBYTE(dwValue As Long) As Byte
  MoveMemory HIBYTE, ByVal VarPtr(LOWORD(dwValue)) + 1, 1
End Function

[Dillinger4]

VB is just not the language for implementing shifts.

Right. No im using java. So basically looking at a problem in the form of say. 12 << 3 i would first have to take into account the register size of the left hand operand. Then i would have to convert the left hand operand to a binary string and go from there.

It seems to me that you are not paying attention to word (register) length. Left numeric shift of 64 causes overflow if you are working with 8-bit signed complement two data. It results in 128 if working with items more than 8 bits long.

Right again. But i am talking about shifting within the range of the type specified. To me an overflow can occcur when using any size register if shifted too many times.