Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-09-26
2003-11-25
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06654774
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to arithmetic and logical shifting of numerical values by a computer microprocessor.
2. Description of Background Art
Numerical shift operations are a standard feature of modern microprocessor code. Shifting is useful for performing multiplication and division operations, as well as for various masking and other operations.
There are two kinds of shifting operations: logical shift and arithmetic shift. As is known by those skilled in the art, a logical shift right of an m-bit binary number by a shift amount n results in a new number having zeros in the n-most significant bits, followed by the (m−n)-most significant bits of the original number. For example, if the number 10011011 is shifted right by 3, the result will be 00010011. Similarly, a logical shift left results in a number consisting of the (m−n)-most significant bits, followed by n zeroes. Thus, when 10011011 is shifted left by 3, the result will be 11011000.
Unlike a logical shift right, an arithmetic shift right preserves the most significant bit of a number when doing the shift. Typically, the most significant bit represents the sign (positive or negative) of the number, and the remaining bits specify the magnitude of the number. If the most significant bit is a 1, i.e., the number is negative, then n 1s are inserted into the most significant bits of the number as it is shifted right. For example, in the example above, an arithmetic shift right by 3 of 10011011 would result in 11110011. Note that if the number is positive, an arithmetic shift right will yield exactly the same result as a logical shift right.
In the past, a commonly used microprocessor instruction was the rotate function, which would rotate a number either right or left. For example, a right rotate by 3 of 10011011 would be 01110011. At present, however, the rotate instruction is not commonly used, and is available mainly as a legacy instruction, providing backward compatibility with older microcode. However, the rotators were and are conventionally used to perform the microcode shift operations.
Because a rotator takes up a relatively large surface area, and because an m-bit rotator requires m wires running from the output back to the input, it was desirable to remove at least one of the rotators while still being able to perform both left and right shift operations. This was made possible by the realization that rotating a binary number x right by some amount r is equivalent to rotating x left by the two's complement of r. For example, rotating the number 11010010 right by 3 using a left rotator, is equivalent to rotating the number left by 5, which is the two's complement of 3. Using either method, the result is the same: 01011010. To perform a logical shift using the rotator, zeroes would have to be added either to the most significant bits or least significant bits, for a right or left shift, respectively. And for an arithmetic shift right, ones would have to be added to the most significant bits. Therefore, in addition to the rotator, a masking logic was used to complete the shift operations.
FIG. 1
illustrates a prior art example of a system
100
for performing shifting operations using a left rotator. The system
100
includes a shift amount latch
101
, a shift amount
102
, a left shift control line
104
, a right shift control line
106
, a multiplexor
110
, two's complement hardware
112
, a multiplexor control line
108
, a left rotator
114
, a masking logic
116
, a rotated data output
118
, a shift count
120
, shifted data
122
, a data latch
124
, data
125
to be shifted, and a shift amount input
126
. Latch
101
is coupled to the left shift control line
104
and right shift control line
106
. Left shift control line
104
is in turn coupled to multiplexor
110
. Right shift control line
106
is coupled to two's complement hardware
112
, which is further coupled to multiplexor
110
. Multiplexor control line
108
is additionally coupled to multiplexor
110
. Multiplexor
110
is further coupled to left rotator
114
, which is also coupled to masking logic
116
. Masking logic
116
is further coupled to the rotated data output
118
and shift count
120
.
A shift amount
102
is input via latch
101
. The shift amount
102
is passed through the left shift control line
104
for left shift operations, or through the right shift control line
106
for right shift operations. The multiplexor
110
is also connected to the multiplexor control line
108
, and the output channel of the multiplexor
110
is coupled to the input channel of the left rotator
114
, which also receives data
125
to be shifted from latch
124
. The output channel of the left rotator
114
sends data to masking logic
116
. The masking logic output is shifted data
122
.
The shift amount
102
is passed either through data line
104
to be shifted left, or data line
106
to be shifted right. The control line
108
controls which input is used by the multiplexor
110
, also known as a mux. For any right shift operation, the shift amount
102
is first converted into its two's complement by the additional two's complement hardware
112
before reaching the mux
110
.
While using two's complement eliminates the space needed by a second rotator, the operations of determining a two's complement and performing the masking function are undesirably time consuming and still require a left rotator
114
, and a masking logic
116
. Therefore, what is needed is a structure and method for performing arithmetic shift right operations that requires less overhead than two's complement structures and operations, while eliminating the need for a rotator, using a small surface area.
BRIEF SUMMARY OF THE INVENTION(S)
In accordance with the present invention, there is provided a structure and method for performing arithmetic shift right operations by n of an m-bit negative number, where n is less than or equal to m-
1
. The structure includes left and right shifters, a shift count, a logical OR gate, and conventional data pathways. The shifters are connected to a shift count, and configured to receive data to be shifted. The shifters are additionally coupled to an OR gate, which is in turn connected to an output latch. The right shifter executes a logical shift right operation on the number to be shifted. For example, if an m-bit negative number is to be arithmetically shifted right by n, the right shifter logically shifts the m-bit negative number right by n. Then, the one's complement of n is determined, and the left shifter performs a left shift on an m-bit mask of ones, left shifting the mask by the one's complement of n. An OR operation is then performed on the results of the two shifting operations, producing the desired arithmetic shift right result without the need for computing the two's complement of n.
REFERENCES:
patent: 4890251 (1989-12-01), Nitta et al.
patent: 6009451 (1999-12-01), Burns
patent: 6098087 (2000-08-01), Lemay
Dhablania Atul
Grondalski Robert S.
Maruyama Takumi
Fujitsu Limited
Malzahn David H.
LandOfFree
Generation of sign extended shifted numerical values does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Generation of sign extended shifted numerical values, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generation of sign extended shifted numerical values will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3179582