The BTEST intrinsic function can be used to extract bits from the representation of an integer. It's useful to be able to store 32
booleans in an int32. What are some applications of the Fortran
bit manipulation intrinsic functions, discussed at http://www2.phys.canterbury.ac.nz/dept/docs/manuals/Fortran-90/HTMLNotesnode158.html for example, that could be tweeted about?
I have read the Wikipedia article https://en.wikipedia.org/wiki/Bit_manipulation .

On Monday, April 18, 2022 at 7:35:42 PM UTC-7, Beliavsky wrote:
> The BTEST intrinsic function can be used to extract bits from the
> representation of an integer. It's useful to be able to store 32
> booleans in an int32. What are some applications of the Fortran
> bit manipulation intrinsic functions, discussed at
> http://www2.phys.canterbury.ac.nz/dept/docs/manuals/Fortran-90/HTMLNotesnode158.html
> for example, that could be tweeted about?
> I have read the Wikipedia article https://en.wikipedia.org/wiki/Bit_manipulation .

A fair number of problems consider bits as bits, and not as numbers.

One common one is bitmap graphics, especially the case where pixels
are either on or off, white or black. You can address a pixel by the location
of a byte or larger word, and bit within the word.

Another that is commonly done with bits, though not always single
bits, is compression algorithms.

On Tuesday, April 19, 2022 at 12:35:42 PM UTC+10, Beliavsky wrote:
> The BTEST intrinsic function can be used to extract bits from the representation of an integer. It's useful to be able to store 32
> booleans in an int32. What are some applications of the Fortran
> bit manipulation intrinsic functions, discussed at http://www2.phys.canterbury.ac.nz/dept/docs/manuals/Fortran-90/HTMLNotesnode158.html for example, that could be tweeted about?
> I have read the Wikipedia article https://en.wikipedia.org/wiki/Bit_manipulation .
..
The algorithm for generating Fibonacci numbers can conveniently dine with bits.

On 4/18/22 9:35 PM, Beliavsky wrote:
> The BTEST intrinsic function can be used to extract bits from the representation of an integer. It's useful to be able to store 32
> booleans in an int32. What are some applications of the Fortran
> bit manipulation intrinsic functions, discussed at http://www2.phys.canterbury.ac.nz/dept/docs/manuals/Fortran-90/HTMLNotesnode158.html for example, that could be tweeted about?
> I have read the Wikipedia article https://en.wikipedia.org/wiki/Bit_manipulation .

Probably the most common application in my field is to pack small values
into larger integer words. If you have some integers that are known to
be between 0 and 31, or example, then they only need 5 bits to represent
their value. So you can pack several within an integer, or you can
combine several such integers of different ranges all together into a
single word. In the old days when memory was scarce, this would reduce
the overall memory footprint, and also it reduces the i/o costs and
external storage requirements. I/O is many hundreds of times more
expensive than the bit operations required to pack and unpack the data,
so this was and still is a good tradeoff. This is usually done with
shifting (ISHFT) and masking operations (IOR).

Another common use is the representation of wave functions in
second-quantized occupation number form. If a bit is 0 then that means
that the spin-orbital is empty in the Slater determinant, if it is 1
then that spin-orbital is occupied. In this application, the programmer
needs to test individual bits (BTEST), set individual bits (IBSET),
clear individual bits (IBCLR), look at mismatches between two
determinants (IEOR), and count the number of bits that are set between
two locations (POPCNT). For some reason, that last operation is not
included in the list at the above link. This application dates back to
the 1960s and 1970s, well before any of the fortran bit operators were
standardized, so originally they were all done with compiler extensions
or with assembly code. As long as the number of spin-orbitals is less
than the integer word length, this is all pretty straightforward to do
with the fortran operators, but when multiple words are required, then
it all gets more complicated. That is where a fortran bitstring data
type would help the programmer. Then all of this could be done with just
fortran intrinsic data types and fortran intrinsic operators. Otherwise,
the programmer needs to do all those operations the hard way.

I have stated in the past that it was almost impossible to write useful
f66 and f77 programs without relying on compiler extensions. This is one
of the applications that displayed the inadequacies of the language in
that era. No standard bit operators, no bitstring data type, there just
wasn't any real support at all in the standard language to do any of
this. Now, the language has improved, but ironically this is no longer
the popular way to do these operations. Now they are usually done with
graphical-network based algorithms which were originally developed as a
workaround for the lack of language support, and eventually became the
preferred approach.

$.02 -Ron Shepard

"Beliavsky" wrote in message
news:16a16dc4-9458-43f6-b769-4a8ea6dd5c76n@googlegroups.com...

> The BTEST intrinsic function can be used to extract bits from the
> representation of an integer. It's useful to be able to store 32
> booleans in an int32. What are some applications of the Fortran
> bit manipulation intrinsic functions, discussed at
> http://www2.phys.canterbury.ac.nz/dept/docs/manuals/Fortran-90/HTMLNotesnode158.html
> for example, that could be tweeted about?
> I have read the Wikipedia article
> https://en.wikipedia.org/wiki/Bit_manipulation .

Well, there is the sieve of Eratosthenes. A big sieve table takes less
memory when implemented as a bit array. At some point the algorithm
will experience cache thrashing and that point happens later with
bit arrays. Sieving with small primes can also happen several steps in one
operation because, for example AVX2 can .AND. or .OR. with a 256-bit
wide register.

There is also bit reversal algorithm that stores a bit reversal table of
half the size of the indices to be reversed and then composes pairs
of bit reversed indices from them. It works well for bit reversal in
place.

On Wednesday, April 20, 2022 at 2:21:41 AM UTC+10, Ron Shepard wrote:
> On 4/18/22 9:35 PM, Beliavsky wrote:
> > The BTEST intrinsic function can be used to extract bits from the representation of an integer. It's useful to be able to store 32
> > booleans in an int32. What are some applications of the Fortran
> > bit manipulation intrinsic functions, discussed at http://www2.phys.canterbury.ac.nz/dept/docs/manuals/Fortran-90/HTMLNotesnode158.html for example, that could be tweeted about?
> > I have read the Wikipedia article https://en.wikipedia.org/wiki/Bit_manipulation .
..
> Probably the most common application in my field is to pack small values
> into larger integer words. If you have some integers that are known to
> be between 0 and 31, or example, then they only need 5 bits to represent
> their value. So you can pack several within an integer,
..
Or you could check whether your compiler offers 1-byte integers, which can hold
signed values to 127.
..
>or you can
> combine several such integers of different ranges all together into a
> single word. In the old days when memory was scarce, this would reduce
> the overall memory footprint,
..
In the old days, 16-bit integers were available,
and decimal integers in the range -9 through 9 were available
for arrays containing small values. They weren't available in FORTRAN,
but were available in PL/I without any special programming (and still are).
Signed integers in the range -128 through 127 are currently available
when one byte is used. Unsigned integers in the range 0 thru 255 are
also available. These are useful for handling picture files.
..
> and also it reduces the i/o costs and
> external storage requirements. I/O is many hundreds of times more
> expensive than the bit operations required to pack and unpack the data,
> so this was and still is a good tradeoff. This is usually done with
> shifting (ISHFT) and masking operations (IOR).
>
> Another common use is the representation of wave functions in
> second-quantized occupation number form. If a bit is 0 then that means
> that the spin-orbital is empty in the Slater determinant, if it is 1
> then that spin-orbital is occupied. In this application, the programmer
> needs to test individual bits (BTEST), set individual bits (IBSET),
> clear individual bits (IBCLR), look at mismatches between two
> determinants (IEOR), and count the number of bits that are set between
> two locations (POPCNT). For some reason, that last operation is not
> included in the list at the above link. This application dates back to
> the 1960s and 1970s, well before any of the fortran bit operators were
> standardized,
..
But bit operations were available in PL/I from 1966.
..
> so originally they were all done with compiler extensions
> or with assembly code. As long as the number of spin-orbitals is less
> than the integer word length, this is all pretty straightforward to do
> with the fortran operators, but when multiple words are required, then
> it all gets more complicated. That is where a fortran bitstring data
> type would help the programmer. Then all of this could be done with just
> fortran intrinsic data types and fortran intrinsic operators. Otherwise,
> the programmer needs to do all those operations the hard way.
>
> I have stated in the past that it was almost impossible to write useful
> f66 and f77 programs without relying on compiler extensions. This is one
> of the applications that displayed the inadequacies of the language in
> that era. No standard bit operators, no bitstring data type, there just
> wasn't any real support at all in the standard language to do any of
> this. Now, the language has improved, but ironically this is no longer
> the popular way to do these operations. Now they are usually done with
> graphical-network based algorithms which were originally developed as a
> workaround for the lack of language support, and eventually became the
> preferred approach.

On Tuesday, April 19, 2022 at 9:21:41 AM UTC-7, Ron Shepard wrote:

(snip)

> Probably the most common application in my field is to pack small values
> into larger integer words. If you have some integers that are known to
> be between 0 and 31, or example, then they only need 5 bits to represent
> their value. So you can pack several within an integer, or you can
> combine several such integers of different ranges all together into a
> single word. In the old days when memory was scarce, this would reduce
> the overall memory footprint, and also it reduces the i/o costs and
> external storage requirements. I/O is many hundreds of times more
> expensive than the bit operations required to pack and unpack the data,
> so this was and still is a good tradeoff. This is usually done with
> shifting (ISHFT) and masking operations (IOR).

Without bit shifting and IOR, though usually without using the
sign bit, you can easily do it with divide and MOD.

Even more, with divide and MOD, you are not limited to only
powers of two, thought it might be a little slower.

On 4/18/2022 9:35 PM, Beliavsky wrote:
> The BTEST intrinsic function can be used to extract bits from the representation of an integer. It's useful to be able to store 32
> booleans in an int32. What are some applications of the Fortran
> bit manipulation intrinsic functions, discussed at http://www2.phys.canterbury.ac.nz/dept/docs/manuals/Fortran-90/HTMLNotesnode158.html for example, that could be tweeted about?
> I have read the Wikipedia article https://en.wikipedia.org/wiki/Bit_manipulation .
In aerospace/avionics, we had to interface dozens to 100s of small
embedded processors communicating via serial bus. Because bandwidth was
limited, we defined our data as efficiently as possible to fit within
the 16-bit words of the serial bus (and many of the target processors).
We also hosted simulations/emulations of some of those small embedded
processors on minicomputers (Datacraft/Gould/Encore/Harris/Concurrent
VOS primarily) depending on the particular test environment needs (all
other or only some embedded processors may be modeled). Also, data
recording and retrieval processes hosted on the minis would conveniently
format the serial bus (or internal) data into useful units if requested.
Needless to say, there is a huge amount of bit manipulation to
translate betweeen the serial bus data formats and the needs internally
of the models which were 24-bit word-based. Harris Fortran had
extensions which allowed you to write these in the form:

intval1 = intval2 .shift. -8 .and. '177 .or. '1 .rotat. 2

The "Purdue" bit extensions were implemented, but rarely used in favor
of the above syntax.

On Tuesday, April 19, 2022 at 5:09:48 PM UTC-4, Gary Scott wrote:
> On 4/18/2022 9:35 PM, Beliavsky wrote:
> > The BTEST intrinsic function can be used to extract bits from the representation of an integer. It's useful to be able to store 32
> > booleans in an int32. What are some applications of the Fortran
> > bit manipulation intrinsic functions, discussed at http://www2.phys.canterbury.ac.nz/dept/docs/manuals/Fortran-90/HTMLNotesnode158.html for example, that could be tweeted about?
> > I have read the Wikipedia article https://en.wikipedia.org/wiki/Bit_manipulation .
> In aerospace/avionics, we had to interface dozens to 100s of small
> embedded processors communicating via serial bus. Because bandwidth was
> limited, we defined our data as efficiently as possible to fit within
> the 16-bit words of the serial bus (and many of the target processors).
> We also hosted simulations/emulations of some of those small embedded
> processors on minicomputers (Datacraft/Gould/Encore/Harris/Concurrent
> VOS primarily) depending on the particular test environment needs (all
> other or only some embedded processors may be modeled). Also, data
> recording and retrieval processes hosted on the minis would conveniently
> format the serial bus (or internal) data into useful units if requested.
> Needless to say, there is a huge amount of bit manipulation to
> translate betweeen the serial bus data formats and the needs internally
> of the models which were 24-bit word-based. Harris Fortran had
> extensions which allowed you to write these in the form:
>
> intval1 = intval2 .shift. -8 .and. '177 .or. '1 .rotat. 2
>
> The "Purdue" bit extensions were implemented, but rarely used in favor
> of the above syntax.

Thanks to you and others for the informative replies.

Beliavsky <beliavsky@aol.com> wrote:
> The BTEST intrinsic function can be used to extract bits from the representation of an integer. It's useful to be able to store 32
> booleans in an int32. What are some applications of the Fortran
> bit manipulation intrinsic functions, discussed at http://www2.phys.canterbury.ac.nz/dept/docs/manuals/Fortran-90/HTMLNotesnode158.html for example, that could be tweeted about?
> I have read the Wikipedia article https://en.wikipedia.org/wiki/Bit_manipulation .

Reading bitcodes from C

integer(c_int) :: ir
character (len=2), dimension(0:3), parameter :: sizes = &
(/'16', '32', '64', 'Ot'/)
ir=zlibcompileflags()
write(outstr, '(2a)', advance='no') ' uInt:', sizes(ibits(ir,0,2))
write(outstr, '(2a)') ' z_off_t:', sizes(ibits(ir,6,2))

Hash codes

! hash code to memoize (unique file name for) a matrix - after the Java equivalent
! function hashmat(n, c)
character (len=16) :: hashmat
integer, intent(in) :: n
double precision, dimension(:), intent(in) :: c
integer (kind=8) :: bits, h

h=123456789
do i=1, n
bits = transfer(c(i), bits)
h = h * 31 + ieor(bits, ishft(bits, -32))
end do
write(hashmat,'(z16)') h
end function hashmat
!

Cheers, David Duffy.

Prior to Fortran 77, there was no character data type. Hollerith constants were used to set character strings into numeric variables.
String size fixed to the number of characters a 'numeric storage unit' (NSU) could hold. Various machines allowed packing anywhere from 2 to 10 characters per integer, and 4 to 10 characters per real. (The compilers with 2 characters per integer/4 characters per real didn't conform to the Standard - since a NSU is supposed to be the same number of bits regardless of data type.) Unless one restricted oneself to a single character per NSU, which could be terribly wasteful of memory in those days, it was hard to write portable character string handling code. Bit manipulation for accessing individual characters in packed words was extremely common, non-portable, and error prone.

Fortran 77 changed all that with its character data type. Though it took years for some programmers to update their codes to use it. There are early adopters who take advantage of new features to clean up their code, make things more reliable and easier to maintain. Then there are those who wait until the very last moment before their favorite computer system or compiler disappears and they are forced to change. Or they retire first, and their codes die after they leave because no one wants to touch the. (Then complain about it for the next 20 years on these Internet forums...)

I've rarely needed to use the bit intrinsics since Fortran 77 (+ Mil Spec extensions) came out. But at least when I do, the spelling and functionality of the intrinsics are standardized now.

On Monday, May 9, 2022 at 2:32:38 PM UTC+10, Walter Spector wrote:
> Prior to Fortran 77, there was no character data type.
..
Not in FORTRAN, but available in COBOL and PL/I for more than a decade.
..
> Hollerith constants were used to set character strings into numeric variables.
> String size fixed to the number of characters a 'numeric storage unit' (NSU)
> could hold.
..
> Various machines allowed packing anywhere from 2 to 10 characters per integer, and 4 to 10 characters per real.
> (The compilers with 2 characters per integer/4 characters per real didn't conform to the Standard -
> since a NSU is supposed to be the same number of bits regardless of data type.)
> Unless one restricted oneself to a single character per NSU, which could be terribly wasteful
> of memory in those days, it was hard to write portable character string handling code.
..
PL/I provided character strings of arbitrary length from 1966 -- in both fixed-length and varying-length.
An advantage of varying-length character strings in PL/I is that each element
of an array can be of different length.
..
> Bit manipulation for accessing individual characters in packed words was extremely common, non-portable, and error prone.
..
Again, bit strings of arbitrary length were available in PL/I from 1966.
..
And, like the character strings, they could be of fixed length and varying-length.
..
> Fortran 77 changed all that with its character data type. Though it took years for some programmers to update their codes to use it. There are early adopters who take advantage of new features to clean up their code, make things more reliable and easier to maintain. Then there are those who wait until the very last moment before their favorite computer system or compiler disappears and they are forced to change. Or they retire first, and their codes die after they leave because no one wants to touch the. (Then complain about it for the next 20 years on these Internet forums...)
>
> I've rarely needed to use the bit intrinsics since Fortran 77 (+ Mil Spec extensions) came out. But at least when I do, the spelling and functionality of the intrinsics are standardized now.

On Monday, May 9, 2022 at 12:10:33 AM UTC-7, Robin Vowels wrote:
> On Monday, May 9, 2022 at 2:32:38 PM UTC+10, Walter Spector wrote:
> > Prior to Fortran 77, there was no character data type.
> .
> PL/I provided character strings of arbitrary length from 1966 -- in both fixed-length and varying-length.
> An advantage of varying-length character strings in PL/I is that each element
> of an array can be of different length.
> .
> > Bit manipulation for accessing individual characters in packed words was extremely common, non-portable, and error prone.
> .
> Again, bit strings of arbitrary length were available in PL/I from 1966.

I was posting in the context of Fortran. Of course there were many languages prior to Fortran 77, dating back to the 1950s, that had character and even bit-level data types.

On Tuesday, May 10, 2022 at 12:48:36 AM UTC+10, Walter Spector wrote:
> On Monday, May 9, 2022 at 12:10:33 AM UTC-7, Robin Vowels wrote:
> > On Monday, May 9, 2022 at 2:32:38 PM UTC+10, Walter Spector wrote:
> > > Prior to Fortran 77, there was no character data type.
> > .
> > PL/I provided character strings of arbitrary length from 1966 -- in both fixed-length and varying-length.
> > An advantage of varying-length character strings in PL/I is that each element
> > of an array can be of different length.
> > .
> > > Bit manipulation for accessing individual characters in packed words was extremely common, non-portable, and error prone.
> > .
> > Again, bit strings of arbitrary length were available in PL/I from 1966.
..
> I was posting in the context of Fortran.
..
I was merely pointing out that bit strings and character strings had been available
in FORTRAN VI for more than a decade prior to F77. Of course, FORTRAN VI
was better known as PL/I.
..
> Of course there were many languages prior to Fortran 77, dating back to the 1950s,
> that had character and even bit-level data types.