Patent ID: 6105032
Filing Date: 2000-08-15
Classification: G06F,Y10S

Abstract:
A method for locating a set bit within a nonzero data entity, the method comprising:a) providing the nonzero data entity, having a length of N bits, N being an integer power of two;b) examining a first part of the nonzero data entity to detect any set bit, the first part being contiguous and having a length of N/2 bits;c) if b) does not detect any set bit, examining a second part of the nonzero data entity to detect any set bit, the second part being contiguous and having a length of N/2 bits, the second part not overlapping with the first part;d) halving the number of contiguous bits to be examined within a remaining part, the remaining part being either the first part or the second part, corresponding to that part within which any set bit was detected by either b) or c);e) examining a first remaining part within the remaining part to detect any set bit;f) if e) does not detect any set bit, examining a second remaining part within the remaining part to detect any set bit, the second remaining part not overlapping with the first remaining part;g) assigning either the first remaining part or the second remaining part to be the remaining part, corresponding to that remaining part within which any set bit was detected by either e) or f), and halving the number of contiguous bits to be examined within the assigned remaining part;h) iteratively repeating e) through g) until the number of bits examined is equal to one.