Integers as bit arrays

Roberto Bagnara
Sun, 13 Jul 2003 10:35:15 +0200

Brian Hurt wrote:
> The basic functionality I was thinking of implementing was:
> - get, set (to 1), clear (to 0), invert individual bits
> - get, set, clear, invert ranges of bits
> - bitwise operators- and, or, xor, negation
> - shifts (already implemented), rotates.

It is in fact very useful to use GMP integers as sets of naturals
(i.e., the set of their positions containing a bit set to one).
For this, the following functionality is desirable:

- searching 0 or 1 bits scanning towards less significant bits;
- efficiently deciding whether a set of naturals is a (proper
   or non proper) subset of another.

You can look at our code for doing that at



Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy