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

Counting "On" Bits in a Bit String

IP.com Disclosure Number: IPCOM000083765D
Original Publication Date: 1975-Jul-01
Included in the Prior Art Database: 2005-Mar-01
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Sheets, MR: AUTHOR

Abstract

This technique has two major parts: a) translation of the bit string into one-byte numbers, each representing the number of bits "on" in the corresponding byte, and b) summing these one-byte numbers in a parallel fashion to find the total bit count of the string. The number of bits "off" in a string can be counted by complementing either the string itself or the translate table. This method is an improvement over previous methods, because of the parallelism achieved in the additions.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 90% of the total text.

Page 1 of 1

Counting "On" Bits in a Bit String

This technique has two major parts: a) translation of the bit string into one- byte numbers, each representing the number of bits "on" in the corresponding byte, and b) summing these one-byte numbers in a parallel fashion to find the total bit count of the string. The number of bits "off" in a string can be counted by complementing either the string itself or the translate table. This method is an improvement over previous methods, because of the parallelism achieved in the additions.

After the translation (via the TR instruction on the IBM 370 family of computers), the bit string has been converted into a string of one-byte numbers. Each element of this string is a number in range of 0-8 inclusive. Because a byte can represent 0-255 inclusive, the partial sum of thirty-one elements can also be represented in one byte. By using the add logical instruction, four of these partial sums may be made in parallel into a word logically partitioned into four parts.

At the end of the string, a staging operation (which is explained in detail below) must occur to place the result into a full-length word. As well, if the string is longer than 124 bytes (i.e., 31 x 4), staging must occur for each 124 bytes of the string processed so that overflow from one byte to another cannot occur.

Staging can be accomplished by an insert character, add register for each of the four bytes containing the partial sums in the logically partitioned word. This ...