Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Algorithm for Finding the Leading One of a Data Stream

IP.com Disclosure Number: IPCOM000109679D
Original Publication Date: 1992-Sep-01
Included in the Prior Art Database: 2005-Mar-24
Document File: 4 page(s) / 96K

Publishing Venue

IBM

Related People

Burton, RWB: AUTHOR [+2]

Abstract

For many operations, it is necessary to find the first occurrence of a binary '1' in a data stream. An example would be a floating point operation where it is necessary to shift the data until the most significant bit (MSB) is a one. With this method, the hardwares find the bit position of the first binary '1' in one cycle and outputs a position of where the leading one is located. With the bit position of a leading one, the hardware can then be programmed to shift the data so that the leading one is the MSB. This particular algorithm can find the leading one of a quadword in 4 levels.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Algorithm for Finding the Leading One of a Data Stream

       For many operations, it is necessary to find the first
occurrence of a binary '1' in a data stream.  An example would be a
floating point operation where it is necessary to shift the data
until the most significant bit (MSB) is a one.  With this method, the
hardwares find the bit position of the first binary '1' in one cycle
and outputs a position of where the leading one is located.  With the
bit position of a leading one, the hardware can then be programmed to
shift the data so that the leading one is the MSB.  This particular
algorithm can find the leading one of a quadword in 4 levels.

      The following algorithm describes how the hardware can find the
leading one of a data stream.  The high-level description is:
o  In parallel do for each halfword
    -  Find position of first 1 (in each halfword)
o  Find first halfword with a 1 bit
o  Encode low order 5 bits of result: position in halfword
o  Encode higher-order bits of result: which halfword

      A more detailed explanation follows.

      Each halfword has logic determining these functions:
BITLOW      whether the first 1 bit in it is an odd-numbered or
even-numbered bit.  Used in generating Pk.
NIBLOW      whether the first 1 bit in it is in an odd-numbered or
even-numbered pair of bits.  Used in generating P(k-1).
BYTELOW     whether the first 1 bit in it is in an odd-numbered or
even-numbered nibble.  Used in generating P(k-2).
HWLOW       whether the first 1 bit in it is in an odd-numbered or
even-numbered byte.  Used in generating P(k-3).
SELHWX      A signal for each halfword that indicates whether it is
the first halfword with a 1-bit in it.

      These results are combined to produce a result -- 4 bits for
each halfword indicating the bit number of the first 1-bit in the
halfword (or 0 if there is no 1-bit).  Other values generated by
other logic select the halfword with the first 1-bit, and the bits
described above from that halfword form the low-order 4 bits of the
result.

      Each halfword also has logic to detect whether it has at least
one 1-bit in it.  This is the OR of four functions, each of which is
the OR of all the bits in a nybble of the halfword.  The nybble-OR
functions are used in the previous logic, too.

      A signal is generated for each halfword that declares whether
it is the first halfword to have a 1-bit.  It is the AND of the
signal stating whether the halfword has a 1-bit and the inverse of
all the signals from more significant halfwords.  These SELHWx
signals, only one of which is true, select the result of the
low-order 4 bits of the result from the output of the halfword with
the first 1-bit.  The SELHWx bits are encoded to produce the
...