From: Guy Steele <[email-masked]>
Date: Wed, 20 May 92 18:03:56 EDT

Proposal for HPF intrinsics POPCNT, POPPAR, LEADZ, and ILEN

Guy L. Steele Jr.
Thinking Machines Corporation
Version of May 20, 1992

(a) An elemental population count intrinsic.  Its action on a scalar is:

  POPCNT(x) = COUNT( (/ (BTEST(x,J), J=0, BIT_SIZE(x)-1) /) )

The result is the number of 1-bits in the integer x, according to the
bit-manipulation model in section 13.5.7 of the Fortran 90 standard.

(b) An elemental population-parity intrinsic.  Its action on a scalar is:

  POPPAR(x) = MERGE(1,0,BTEST(POPCNT(x),0))

The result is 1 if the number of 1-bits in the integer x is odd,
or 0 if the number of 1-bits in the integer x is even.

(c) An elemental count-leading-zeros intrinsic.  Its action on a scalar is:

  LEADZ(x) = MINVAL( (/ (J, J=0,BIT_SIZE(x)) /),
		MASK=(/ (BTEST(x,J), J=BIT_SIZE(x)-1,0,-1), .TRUE. /) )

The result is a count of the number of leading 0-bits in the integer
x, according to the bit-manipulation model in section 13.5.7 of the
Fortran 90 standard.

Note that a given integer value may produce different results from
LEADZ, depending on the number of bits in the representation of the
integer.  That is because bits are counted from the left (the most
significant bit).
intrinsics-popcnt-proposal, version 2
----------------------------------------------------------------

The intent is to define POPCNT, POPPAR, and LEADZ consistent with
their use in Cray Fortran, but to limit them to integer arguments.

----------------------------------------------------------------

(d) An elemental integer-length intrinsic.  Its action on a scalar is:

  ILEN(X) = ceiling(log2( IF x < 0 THEN -x ELSE x+1 ))

This is related to LEADZ but is often much more convenient for
the calculation of array dimensions, etc.  It is the number of bits
required to store a 2's-complement signed integer x.  As examples of
its use,  2**ILEN(N-1)  rounds N up to a power of 2 (for N > 0),
whereas  2**(ILEN(N)-1)  rounds N down to a power of 2.

Note that a given integer value will always produce the same result
from ILEN, independent on the number of bits in the representation of
the integer.  That is because bits are counted from the right (the
least significant bit).

The definition of ILEN is equivalent to that of the built-in function
integer-length in Common Lisp, which has proven to be quite useful.