US4748575A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Circuit for detecting trailing zeros in numbers
Assignee: Zilog Inc
•
Filing: 1984-12-21
•
Granted: 1988-05-31
•
Expires: 2004-12-21
Abstract
Abstract A system for detecting the presence of trailing zeros in a number. The number is divided into a plurality of consecutive groups, each group having an address. The system also determines the address location of the lowest order group which contains at least one non-zero bit and which precedes any trailing zeros of the number. Such group defines a target group. The system includes a first circuit for dividing the number into a plurality of consecutive words where each word contains more bits than any group. The first circuit also determines the lowest order word which contains one or more non-zero bits and which precedes any trailing zeros of the number. The system includes a second dividing circuit for dividing each word into a plurality of segments each having a number of bits equal to or greater than the number of bits in the target group. The second dividing circuit determines, for each word, the lowest order segment which contains one or more non-zero bits and which precedes any trailing zeros of such word. The first and second dividing circuits perform the determination substantially simultaneously to reduce the amount of time for determining the address of the target. The system further includes circuit for determining, from the lowest order word and segment determined by the first and second dividing circuits, the address of the target group.
Inventors
- 👤 Peter B. Ashkin
- 👤 Andrew G. Heninger
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 04:35
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/74
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
327 words
A system for detecting the presence of trailing zeros in a number, said number being divisible into a plurality of consecutive groups, each group having an address, and said system also for determining the address location of the lowest order group which contains at least one non-zero bit and which precedes any trailing zeros of the number, defining a target group, said system comprising: means for dividing the number into a plurality of consecutive words and for determining the lowest order word which contains one or more non-zero bits and which precedes any trailing zeros of the number, said words each containing more bits than any group; means for dividing each word into a plurality of consecutive segments each having a number of bits greater than or equal to the number of bits in the target group, and for determining, for each word, the lowest order segment which contains one or more non-zero bits and which precedes any trailing zeros of such word, and wherein the determination of said lowest order segment is substantially concurrent with the determination of said lowest order word to reduce the amount of time for determining the address of said target group; means for determining, from said lowest order word and segments, the address of said target group, wherein each segment contains more bits than the target group and contains a plurality of groups of bits; and means for dividing each segment into a plurality of consecutive subsegments each containing a plurality of consecutive groups and for determining (a) for each segment, the lowest order subsegment which contains at least one non-zero bit and which precedes any trailing zeros of such segment, and (b) for each subsegment, the lowest order group which contains at least one non-zero bit and which precedes any trailing zeros of such subsegment, and wherein the determination of said lowest order word, segments, subsegments and groups are performed substantially concurrently to determine the address of said target group.
Claim 2
Independent Claim
327 words
A system for detecting the presence of trailing zeros in a number, said number being divisible into a plurality of consecutive groups, each group having an address, and said system also for determining the address location of the lowest order group which contains at least one non-zero bit and which precedes any trailing zeros of the number, defining a target group, said system comprising: means for dividing the number into a plurality of consecutive words and for determining the lowest order word which contains one or more non-zero bits and which precedes any trailing zeros of the number, said words each containing more bits than any group; means for dividing each word into a plurality of consecutive segments each having a number of bits greater than or equal to the number of bits in the target group, and for determining, for each word, the lowest order segment which contains one or more non-zero bits and which precedes any trailing zeros of such word, and wherein the determination of said lowest order segment is substantially concurrent with the determination of said lowest order word to reduce the amount of time for determining the address of said target group; means for determining, from said lowest order word and segments, the address of said target group, wherein each segment contains more bits than the target group and contains a plurality of groups of bits; and means for dividing each segment into a plurality of consecutive subsegments each containing a plurality of consecutive groups and for determining (a) for each segment, the lowest order subsegment which contains at least one non-zero bit and which precedes any trailing zeros of such segment, and (b) for each subsegment, the lowest order group which contains at least one non-zero bit and which precedes any trailing zeros of such subsegment, and wherein the determination of said lowest order word, segments, subsegments and groups are performed substantially concurrently to determine the address of said target group.
Claim 3
Dependent Claim
89 words
The system of claim 1, wherein each segment is divisible into a plurality of subsegments, said system further comprising means for dividing each word into a plurality of consecutive subsegments each containing a plurality of consecutive groups and for determining (a) for each word, the lowest order subsegment which contains at least one non-zero bit and which precedes any trailing zeros of such word, and (b) for each word, the lowest order group which contains at least one non-zero bit and which precedes any trailing zeros of such word.
Claim 4
Dependent Claim
34 words
The system of claim 2, wherein said number has 16n bits, each word 4n bits, each segment 2n bits, each subsegment n bits and each group n bits, where n is a positive integer.
Claim 5
Dependent Claim
9 words
The system of claim 3, wherein n is 4.
Claim 6
Dependent Claim
35 words
The system of claim 1, wherein the number is a 4n bit number, where n is a positive integer, each word containing 2n bits, each group containing n bits and each segment containing n bits.
Claim 7
Dependent Claim
9 words
The system of claim 5, wherein n is 16.
Claim 8
Dependent Claim
11 words
The system of claim 5, wherein each word contains two segments.
Claim 9
Independent Claim
91 words
A system for use with a multiplier system for detecting the presence of trailing zeros in the two operands to be multiplied by the multiplier and for determining which of the two operands has the more trailing zeros, said system comprising: means for determining the location of the lowest order non-zero bit preceding trailing zeros of each of the two operands, if any; and means for comparing the locations of said lowest order non-zero bits of the two operands to determine which of the two operands contains the more trailing zeros.
Claim 10
Independent Claim
91 words
A system for use with a multiplier system for detecting the presence of trailing zeros in the two operands to be multiplied by the multiplier and for determining which of the two operands has the more trailing zeros, said system comprising: means for determining the location of the lowest order non-zero bit preceding trailing zeros of each of the two operands, if any; and means for comparing the locations of said lowest order non-zero bits of the two operands to determine which of the two operands contains the more trailing zeros.
Claim 11
Dependent Claim
167 words
The system of claim 8, wherein the system employs a predetermined number as its radix, wherein each of the two operands is divisible into a plurality of consecutive groups of equal number of bits, each group of one operand containing the same number of bits as each of those of the other operand, said number of bits being commensurate with the radix, each group of each operand having an address, wherein said determining means determines the location of the lowest order non-zero bit preceding trailing zeros of each operand by determining the address of the lowest order group in such operand which contains at least one non-zero bit and which precedes any trailing zeros of such operand defining the target group of such operand, and wherein said comparing means compares the locations of said lowest order non-zero bits by comparing the addresses of the target groups of the two operands, the operand whose target group having a higher address being the operand with the more trailing zeros.
Claim 12
Dependent Claim
22 words
The system of claim 9, wherein the determining means determines the addresses of the target groups of the two operands substantially concurrently.
Claim 13
Dependent Claim
166 words
The system of claim 10, wherein the determining means comprises: means for dividing each operand into a plurality of consecutive words and for determining the lowest order word which contains one or more non-zero bits and which precedes any trailing zeros of such operand, said words each containing more bits than each group; means for dividing each word into a plurality of consecutive segments each having a number of bits greater than or equal to the number of bits in the target group, and for determining, for each word, the lowest order segment which contains one or more non-zero bits and which precedes any trailing zeros of such word, and wherein the determination of said lowest order segment is substantially concurrent with the determination of said lowest order word to reduce the amount of time for determining the location of the target group of such operand; and means for determining, from said lowest order word and segments, the address of said target group of such operand.
Claim 14
Dependent Claim
129 words
The system of claim 11, wherein each segment of each operand is divisible into a plurality of subsegments, said system further comprising means for dividing each word of each operand into a plurality of consecutive subsegments each containing a plurality of consecutive groups and for determining (a) for each word of each operand, the lowest order subsegment which contains at least one non-zero bit and which precedes any trailing zeros of such word, and (b) for each word of each operand, the lowest order group which contains at least one non-zero bit and which precedes any trailing zeros of such word and wherein the determination of said lowest order word, segments, subsegments and groups are performed substantially concurrently to determine the address of said target group of each operand.
Claim 15
Dependent Claim
34 words
The system of claim 12, wherein each operand has 16n bits, each word 8n bits, each segment 4n bits, each subsegment 2n bits and each group n bits, where n is a positive integer.
Claim 16
Dependent Claim
9 words
The system of claim 13, wherein n is 4.
Claim 17
Dependent Claim
103 words
The system of claim 10, wherein the determining means provides to the comparing means the addresses of the target groups of the two operands for comparison, and wherein the comparing means is a subtracter for subtracting the address of the target group of the first operand from that of the target group of the second operand, so that a positive difference indicates that the second operand has more trailing zeros, and a negative remainder indicates that the first operand has more trailing zeros, and so that the operand with the more trailing zeros is selectable by the multiplier system to be the multiplier.
Claim 18
Dependent Claim
35 words
The system of claim 15, further comprising means providing the address of the target group of the multiplier having more trailing zeros to the multiplier system for skipping over the trailing zeros of the multiplier.
Claim 19
Dependent Claim
24 words
The system of claim 8, wherein the determining means determines the locations of the lowest order non-zero bits of the two operands substantially concurrently.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1991-05-31 | 1991-11-30 | 1992-05-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1995-05-31 | 1995-11-30 | 1996-05-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1999-05-31 | 1999-11-30 | 2000-05-31 | $7700.00 | Window Closed / Lapsed |