HELP BIT                                        Robert Duncan, July 1990

Bitwise operations on integers.


    CONTENTS - (Use <ENTER> g to access required sections)

 -- The Bit Module
 -- Bitwise Operators and Functions


-- The Bit Module -----------------------------------------------------

signature Bit
structure Bit : Bit
    The structure -Bit- is an autoloadable library module which  enables
    integers  to  be  manipulated  as  bit  patterns  according  to  the
    two's-complement representation.  Because  integers can  be  of  any
    size, the number of bits in an integer is (conceptually) indefinite,
    with the sign bit being considered to  extend as far to the left  as
    necessary in any particular context. Thus everywhere above its  most
    significant bit,  a  positive integer  has  0 bits  and  a  negative
    integer has 1 bits.

    The bits within an integer are numbered from 0 upwards. Although  in
    principal bit  numbers of  any magnitude  should be  legal,  certain
    functions impose a limit on bit numbers for efficiency reasons. This
    limit is  determined by  the  largest number  which can  fit  into a
    machine word and may vary  between different implementations; it  is
    considerably larger than is typically required by applications.  The
    exception -BitNumber- is raised if ever the limit is exceeded.

    The -Bit- structure is described by the following signature:

        signature Bit = sig

            exception BitNumber

            val ||          : int * int -> int
            val &&          : int * int -> int
            val &~          : int * int -> int
            val &?          : int * int -> bool
            val ~~          : int -> int

            val set         : int -> int -> int
            val mask        : int -> int -> int
            val clear       : int -> int -> int
            val test        : int -> int -> bool
            val complement  : int -> int

            val <<          : int * int -> int
            val >>          : int * int -> int

            val shiftl      : int -> int -> int
            val shiftr      : int -> int -> int

            val setbit      : int -> int -> int
            val clearbit    : int -> int -> int
            val testbit     : int -> int -> bool

            val size        : int -> int
            val bitcount    : int -> int

        end


-- Bitwise Operators and Functions ------------------------------------

exception BitNumber
    Raised whenever  a  bit number  exceeds  the  implementation-defined
    limit (see above).


infix 6 ||
val (i : int) || (j : int) : int
val set (i : int) (j : int) : int
    Bitwise logical OR: sets those bits in -i- which are set in -j-.


infix 7 &&
val (i : int) && (j : int) : int
val mask (i : int) (j : int) : int
    Bitwise logical AND: clears those bits  in -i- which are not set  in
    -j-.


infix 7 &~
val (i : int) &~ (j : int) : int
val clear (i : int) (j : int) : int
    Bitwise logical AND-NOT: clears those bits  in -i- which are set  in
    -j-.

    Definition:

        infix 7 &~
        fun i &~ j = i && ~~j;


infix 7 &?
val (i : int) &? (j : int) : bool
val test (i : int) (j : int) : bool
    Bitwise test: returns  -true- if -i-  and -j- have  any bits set  in
    common.

    Definition:

        infix 7 &?
        fun i &? j = i && j <> 0;


val ~~ (i : int) : int
val complement (i : int) : int
    Bitwise logical complement: inverts each bit in -i-.


infix 5 <<
val (i : int) << (j : int) : int
val shiftl (i : int) (j : int) : int
    Arithmetic left shift:  shifts -i-  left by -j-  places. A  negative
    value of  -j- causes  a  right shift  by  the absolute  amount.  The
    exception -BitNumber- will be raised if -j- is out of range.


infix 5 >>
val (i : int) >> (j : int) : int
val shiftr (i : int) (j : int) : int
    Arithmetic right shift: shifts -i-  right by -j- places. A  negative
    value of  -j-  causes a  left  shift  by the  absolute  amount.  The
    exception -BitNumber- will be raised if -j- is out of range.


val setbit (n : int) (i : int) : int
    Sets bit -n-  of -i-.  Raises the  exception -BitNumber-  if -n-  is
    negative or larger than the bit-number limit.

    Definition:

        fun setbit n i =
            if n < 0 then
                raise BitNumber
            else
                set i (1 << n);


val clearbit (n : int) (i : int) : int
    Clears bit -n- of  -i-. Raises the exception  -BitNumber- if -n-  is
    negative or larger than the bit-number limit.

    Definition:

        fun clearbit n i =
            if n < 0 then
                raise BitNumber
            else
                clear i (1 << n);


val testbit (n : int) (i : int) : int
    Tests bit -n- of -i-, returning -true- if the bit is set. Raises the
    exception  -BitNumber-  if  -n-  is  negative  or  larger  than  the
    bit-number limit.

    Definition:

        fun testbit n i =
            if n < 0 then
                raise BitNumber
            else
                test i (1 << n);


val size (i : int) : int
    Returns the length of -i- in bits, i.e. the smallest number -n- such
    that:

        i  <    (1 << n),   i >= 0
        i  >=  (-1 << n),   i <  0

    If -i-  is non-negative,  then -n-  is the  minimum number  of  bits
    needed to represent -i- as  an unsigned integer; otherwise at  least
    (n+1) bits  are  required  to  represent -i-  as  a  signed  integer
    regardless of its sign.


val bitcount (i : int) : int
    Returns the number of 1 or 0 bits in -i-: 1 bits if -i- is  positive
    or 0 bits  if -i- is  negative (a positive  integer has an  infinite
    number of 0 bits because of the indefinite sign extension;  likewise
    for 1 bits in a negative number).


--- C.all/pml/help/bit
--- Copyright University of Sussex 1991. All rights reserved. ----------