Browse Prior Art Database

Bit Counting

IP.com Disclosure Number: IPCOM000074336D
Original Publication Date: 1971-Apr-01
Included in the Prior Art Database: 2005-Feb-23
Document File: 1 page(s) / 11K

Publishing Venue

IBM

Related People

Stump, ME: AUTHOR

Abstract

The number of bits in a given field which are set is equal to the number of successive logical intersections required between the field and the field minus 1 to produce a field of all 0's. A narrative code for this algorithm is as follows: Let N represent the field in question. Step 1. Set a counter to 0. Step 2. If N=0 go to finish. Step 3. Set N equal to N 'AND' (N-1). Step 4. Increment the counter by 1. Step 5. Go to Step 2. Finish: The counter now contains the number of bits that were set in the original N.

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

Page 1 of 1

Bit Counting

The number of bits in a given field which are set is equal to the number of successive logical intersections required between the field and the field minus 1 to produce a field of all 0's. A narrative code for this algorithm is as follows: Let N represent the field in question.

Step 1. Set a counter to 0.

Step 2. If N=0 go to finish.

Step 3. Set N equal to N 'AND' (N-1).

Step 4. Increment the counter by 1.

Step 5. Go to Step 2.

Finish: The counter now contains the number of bits that

were set in the original N.

Example: Given the octal number 10 000 600 002 expressed in binary as:

10 000 60O 002 - 01 000 000 000 000 110 00O 000 000 000 010 AND 10 000 600 001 - 01 000 000 000 000 110 000 000 000 000 001 10 000 600 000 - 01 000 000 000 000 110 000 000 000 000 000
AND 10 000 577 777 - 01 000 000 000 000 101 111 111 111 111 111 10 000 400 000 - 01 000 000 000 000 100 000 000 000 000 000
AND 10 000 377 777 - 01 000 000 000 000 011 111 111 111 111 111 10 00O 000 000 - 01 000 000 000 000 000 000 000 000 000 000
AND 07 777 777 777 - 00 111 111 111 111 111 111 111 111 111 111 00 000 000 000 - 00 000 000 000 000 000 000 000 000 000 000.

Four AND's were required to produce the field of all 0's and thus there were 4-bits set in the original number.

Similarly, the number of reset bits in a given field is equal to the number of logical exclusive OR's required between the field and the field plus 1 to produce a field of all 1 bits.

1