MAN page from Mandrake Other perl-Bit-Vector-5.5-1.i386.rpm

Vector

Section: User Contributed Perl Documentation (3)
Updated: perl 5.004, patch 04
Index

NAME

Bit::Vector - efficient base class implementing bit vectors.

PREFACE

This module implements bit vectors of arbitrary sizeand provides efficient methods for handling them.

This goes far beyond the built-in capabilities of Perl forhandling bit vectors (compare with the method list below).

Moreover, the C core of this module can be used ``stand-alone''in other C applications; Perl is not necessarily required.

The module is intended to serve as a base class for other applicationsor application classes, such as implementing sets or performing biginteger arithmetic.

All methods are implemented in C internally for maximum performance.

The module also provides overloaded arithmetic and relational operatorsfor maximum ease of use (Perl only).

Note that there is (of course) a little speed penalty to pay foroverloaded operators. If speed is crucial, use the methods of thismodule directly instead of their corresponding overloaded operators!

This module is useful for a large range of different tasks:

-: for example for implementing sets and performing set operations(like union, difference, intersection, complement, check for subsetrelationship etc.),
-: as a basis for many efficient algorithms, for instance the``Sieve of Erathostenes'' (for calculating prime numbers),
(The complexities of the methods in this module are usually eitherO(1) or O(n/b), where ``b'' is the number of bits in a machine wordon your system.)
-: for shift registers of arbitrary length (for example for cyclicredundancy checksums),
-: to calculate ``look-ahead'', ``first'' and ``follow'' character setsfor parsers and compiler-compilers,
-: for graph algorithms,
-: for efficient storage and retrieval of status information,
-: for performing text synthesis ruled by boolean expressions,
-: for ``big integer'' arithmetic with arbitrarily large integers,
-: for manipulations of chunks of bits of arbitrary size,
-: for bitwise processing of audio CD wave files,
-: to convert formats of data files,

and more.

(A number of example applications is available from my web site athttp://www.engelschall.com/u/sb/download/.)

A large number of import/export methods allow you to access individualbits, contiguous ranges of bits, machine words, arbitrary chunks ofbits, lists (arrays) of chunks of bits or machine words and a wholebit vector at once (for instance for blockwrite/-read to and froma file).

You can also import and export the contents of a bit vector in binary,hexadecimal and decimal representation as well as ``.newsrc'' styleenumerations.

Note that this module is specifically designed for efficiency, which isalso the reason why its methods are implemented in C.

To further increase execution speed, the module doesn't use bytes as itsbasic storage unit, but rather uses machine words, assuming that a machineword is the most efficiently handled size of all scalar types on allmachines (that's what the ANSI C standard proposes and assumes anyway).

In order to achieve this, it automatically determines the number of bitsin a machine word on your system and then adjusts its internal configurationconstants accordingly.

The greater the size of this basic storage unit, the better the complexity(= execution speed) of the methods in this module, but also the greater theaverage waste of unused bits in the last word.

Example applications:

See the module ``Set::IntRange'' for an easy-to-use module for setsof integers of arbitrary ranges.

See the module ``Math::MatrixBool'' for an efficient implementationof boolean matrices and boolean matrix operations.

(Both modules are also available from my web site athttp://www.engelschall.com/u/sb/download/ or any CPAN server.)

An application relying crucially on this ``Bit::Vector'' module is ``Slice'',a tool for generating different document versions out of a singlemaster file, ruled by boolean expressions ("include english versionof text plus examples but not ...").

This tool is itself part of another tool, ``Website META Language'' ("WML"),which allows you to generate and maintain large web sites.

Among many other features, it allows you to define your own HTML tags whichwill be expanded either at generation or at run time, depending on yourchoice.

SYNOPSIS

CLASS METHODS (implemented in C)

  Version      $version = Bit::Vector->Version();

  Word_Bits      $bits = Bit::Vector->Word_Bits();  #  bits in a machine word

  Long_Bits      $bits = Bit::Vector->Long_Bits();  #  bits in an unsigned long

  new      $vector = Bit::Vector->new($bits);  #  bit vector constructor

  new_Hex      $vector = Bit::Vector->new_Hex($bits,$string);

  new_Bin      $vector = Bit::Vector->new_Bin($bits,$string);

  new_Dec      $vector = Bit::Vector->new_Dec($bits,$string);

  new_Enum      $vector = Bit::Vector->new_Enum($bits,$string);

  Concat_List      $vector = Bit::Vector->Concat_List(@vectors);

OBJECT METHODS (implemented in C)

  new      $vec2 = $vec1->new($bits);  #  alternative call of constructor

  Shadow      $vec2 = $vec1->Shadow();  #  new vector, same size but empty

  Clone      $vec2 = $vec1->Clone();  #  new vector, exact duplicate

  Concat      $vector = $vec1->Concat($vec2);

  Concat_List      $vector = $vec1->Concat_List($vec2,$vec3,...);

  Size      $bits = $vector->Size();

  Resize      $vector->Resize($bits);      $vector->Resize($vector->Size()+5);      $vector->Resize($vector->Size()-5);

  Copy      $vec2->Copy($vec1);

  Empty      $vector->Empty();

  Fill      $vector->Fill();

  Flip      $vector->Flip();

  Primes      $vector->Primes();  #  Sieve of Erathostenes

  Reverse      $vec2->Reverse($vec1);

  Interval_Empty      $vector->Interval_Empty($min,$max);

  Interval_Fill      $vector->Interval_Fill($min,$max);

  Interval_Flip      $vector->Interval_Flip($min,$max);

  Interval_Reverse      $vector->Interval_Reverse($min,$max);

  Interval_Scan_inc      if (($min,$max) = $vector->Interval_Scan_inc($start))

  Interval_Scan_dec      if (($min,$max) = $vector->Interval_Scan_dec($start))

  Interval_Copy      $vec2->Interval_Copy($vec1,$offset2,$offset1,$length);

  Interval_Substitute      $vec2->Interval_Substitute($vec1,$off2,$len2,$off1,$len1);

  is_empty      if ($vector->is_empty())

  is_full      if ($vector->is_full())

  equal      if ($vec1->equal($vec2))

  Lexicompare (unsigned)      if ($vec1->Lexicompare($vec2) == 0)      if ($vec1->Lexicompare($vec2) != 0)      if ($vec1->Lexicompare($vec2) <  0)      if ($vec1->Lexicompare($vec2) <= 0)      if ($vec1->Lexicompare($vec2) >  0)      if ($vec1->Lexicompare($vec2) >= 0)

  Compare (signed)      if ($vec1->Compare($vec2) == 0)      if ($vec1->Compare($vec2) != 0)      if ($vec1->Compare($vec2) <  0)      if ($vec1->Compare($vec2) <= 0)      if ($vec1->Compare($vec2) >  0)      if ($vec1->Compare($vec2) >= 0)

  to_Hex      $string = $vector->to_Hex();

  from_Hex      $vector->from_Hex($string);

  to_Bin      $string = $vector->to_Bin();

  from_Bin      $vector->from_Bin($string);

  to_Dec      $string = $vector->to_Dec();

  from_Dec      $vector->from_Dec($string);

  to_Enum      $string = $vector->to_Enum();  #  e.g. "2,3,5-7,11,13-19"

  from_Enum      $vector->from_Enum($string);

  Bit_Off      $vector->Bit_Off($index);

  Bit_On      $vector->Bit_On($index);

  bit_flip      $bit = $vector->bit_flip($index);

  bit_test, contains      $bit = $vector->bit_test($index);      $bit = $vector->contains($index);      if ($vector->bit_test($index))      if ($vector->contains($index))

  Bit_Copy      $vector->Bit_Copy($index,$bit);

  LSB (least significant bit)      $vector->LSB($bit);

  MSB (most significant bit)      $vector->MSB($bit);

  lsb (least significant bit)      $bit = $vector->lsb();

  msb (most significant bit)      $bit = $vector->msb();

  rotate_left      $carry = $vector->rotate_left();

  rotate_right      $carry = $vector->rotate_right();

  shift_left      $carry = $vector->shift_left($carry);

  shift_right      $carry = $vector->shift_right($carry);

  Move_Left      $vector->Move_Left($bits);  #  shift left "$bits" positions

  Move_Right      $vector->Move_Right($bits);  #  shift right "$bits" positions

  Insert      $vector->Insert($offset,$bits);

  Delete      $vector->Delete($offset,$bits);

  increment      $carry = $vector->increment();

  decrement      $carry = $vector->decrement();

  add      $carry = $vec3->add($vec1,$vec2,$carry);

  subtract      $carry = $vec3->subtract($vec1,$vec2,$carry);

  Negate      $vec2->Negate($vec1);

  Absolute      $vec2->Absolute($vec1);

  Sign      if ($vector->Sign() == 0)      if ($vector->Sign() != 0)      if ($vector->Sign() <  0)      if ($vector->Sign() <= 0)      if ($vector->Sign() >  0)      if ($vector->Sign() >= 0)

  Multiply      $vec3->Multiply($vec1,$vec2);

  Divide      $quot->Divide($vec1,$vec2,$rest);

  GCD (Greatest Common Divisor)      $vec3->GCD($vec1,$vec2);

  Block_Store      $vector->Block_Store($buffer);

  Block_Read      $buffer = $vector->Block_Read();

  Word_Size      $size = $vector->Word_Size();  #  number of words in "$vector"

  Word_Store      $vector->Word_Store($offset,$word);

  Word_Read      $word = $vector->Word_Read($offset);

  Word_List_Store      $vector->Word_List_Store(@words);

  Word_List_Read      @words = $vector->Word_List_Read();

  Word_Insert      $vector->Word_Insert($offset,$count);

  Word_Delete      $vector->Word_Delete($offset,$count);

  Chunk_Store      $vector->Chunk_Store($chunksize,$offset,$chunk);

  Chunk_Read      $chunk = $vector->Chunk_Read($chunksize,$offset);

  Chunk_List_Store      $vector->Chunk_List_Store($chunksize,@chunks);

  Chunk_List_Read      @chunks = $vector->Chunk_List_Read($chunksize);

  Index_List_Remove      $vector->Index_List_Remove(@indices);

  Index_List_Store      $vector->Index_List_Store(@indices);

  Index_List_Read      @indices = $vector->Index_List_Read();

  Union      $set3->Union($set1,$set2);

  Intersection      $set3->Intersection($set1,$set2);

  Difference      $set3->Difference($set1,$set2);

  ExclusiveOr      $set3->ExclusiveOr($set1,$set2);

  Complement      $set2->Complement($set1);

  subset      if ($set1->subset($set2))  #  true if $set1 is subset of $set2

  Norm      $norm = $set->Norm();

  Min      $min = $set->Min();

  Max      $max = $set->Max();

  Multiplication      $matrix3->Multiplication($rows3,$cols3,                      $matrix1,$rows1,$cols1,                      $matrix2,$rows2,$cols2);

  Closure      $matrix->Closure($rows,$cols);

  Transpose      $matrix2->Transpose($rows2,$cols2,$matrix1,$rows1,$cols1);

CLASS METHODS (implemented in Perl)

  Configuration      $config = Bit::Vector->Configuration();      Bit::Vector->Configuration($config);      $oldconfig = Bit::Vector->Configuration($newconfig);

OVERLOADED OPERATORS (implemented in Perl)

  String Conversion      $string = "$vector";             #  depending on configuration      print "\$vector = '$vector'\n";

  Emptyness      if ($vector)  #  if not empty (non-zero)      if (! $vector)  #  if empty (zero)      unless ($vector)  #  if empty (zero)

  Complement (one's complement)      $vector2 = ~$vector1;      $vector = ~$vector;

  Negation (two's complement)      $vector2 = -$vector1;      $vector = -$vector;

  Norm      $norm = abs($vector);  #  depending on configuration

  Absolute      $vector2 = abs($vector1);  #  depending on configuration

  Concatenation      $vector3 = $vector1 . $vector2;      $vector1 .= $vector2;      $vector1 = $vector2 . $vector1;      $vector2 = $vector1 . $scalar;  #  depending on configuration      $vector2 = $scalar . $vector1;      $vector .= $scalar;

  Duplication      $vector2 = $vector1 x $factor;      $vector x= $factor;

  Shift Left      $vector2 = $vector1 << $bits;      $vector <<= $bits;

  Shift Right      $vector2 = $vector1 >> $bits;      $vector >>= $bits;

  Union      $vector3 = $vector1 | $vector2;      $vector1 |= $vector2;      $vector2 = $vector1 | $scalar;      $vector |= $scalar;

      $vector3 = $vector1 + $vector2;  #  depending on configuration      $vector1 += $vector2;      $vector2 = $vector1 + $scalar;      $vector += $scalar;

  Intersection      $vector3 = $vector1 & $vector2;      $vector1 &= $vector2;      $vector2 = $vector1 & $scalar;      $vector &= $scalar;

      $vector3 = $vector1 * $vector2;  #  depending on configuration      $vector1 *= $vector2;      $vector2 = $vector1 * $scalar;      $vector *= $scalar;

  ExclusiveOr      $vector3 = $vector1 ^ $vector2;      $vector1 ^= $vector2;      $vector2 = $vector1 ^ $scalar;      $vector ^= $scalar;

  Set Difference      $vector3 = $vector1 - $vector2;  #  depending on configuration      $vector1 -= $vector2;      $vector1 = $vector2 - $vector1;      $vector2 = $vector1 - $scalar;      $vector2 = $scalar - $vector1;      $vector -= $scalar;

  Addition      $vector3 = $vector1 + $vector2;  #  depending on configuration      $vector1 += $vector2;      $vector2 = $vector1 + $scalar;      $vector += $scalar;

  Subtraction      $vector3 = $vector1 - $vector2;  #  depending on configuration      $vector1 -= $vector2;      $vector1 = $vector2 - $vector1;      $vector2 = $vector1 - $scalar;      $vector2 = $scalar - $vector1;      $vector -= $scalar;

  Multiplication      $vector3 = $vector1 * $vector2;  #  depending on configuration      $vector1 *= $vector2;      $vector2 = $vector1 * $scalar;      $vector *= $scalar;

  Division      $vector3 = $vector1 / $vector2;      $vector1 /= $vector2;      $vector1 = $vector2 / $vector1;      $vector2 = $vector1 / $scalar;      $vector2 = $scalar / $vector1;      $vector /= $scalar;

  Modulo      $vector3 = $vector1 % $vector2;      $vector1 %= $vector2;      $vector1 = $vector2 % $vector1;      $vector2 = $vector1 % $scalar;      $vector2 = $scalar % $vector1;      $vector %= $scalar;

  Increment      ++$vector;      $vector++;

  Decrement      --$vector;      $vector--;

  Lexical Comparison (unsigned)      $cmp = $vector1 cmp $vector2;      if ($vector1 lt $vector2)      if ($vector1 le $vector2)      if ($vector1 gt $vector2)      if ($vector1 ge $vector2)

      $cmp = $vector cmp $scalar;      if ($vector lt $scalar)      if ($vector le $scalar)      if ($vector gt $scalar)      if ($vector ge $scalar)

  Comparison (signed)      $cmp = $vector1 <=> $vector2;      if ($vector1 < $vector2)  #  depending on configuration      if ($vector1 <= $vector2)      if ($vector1 > $vector2)      if ($vector1 >= $vector2)

      $cmp = $vector <=> $scalar;      if ($vector < $scalar)  #  depending on configuration      if ($vector <= $scalar)      if ($vector > $scalar)      if ($vector >= $scalar)

  Equality      if ($vector1 eq $vector2)      if ($vector1 ne $vector2)      if ($vector eq $scalar)      if ($vector ne $scalar)

      if ($vector1 == $vector2)      if ($vector1 != $vector2)      if ($vector == $scalar)      if ($vector != $scalar)

  Subset Relationship      if ($vector1 <= $vector2)  #  depending on configuration

  True Subset Relationship      if ($vector1 < $vector2)  #  depending on configuration

  Superset Relationship      if ($vector1 >= $vector2)  #  depending on configuration

  True Superset Relationship      if ($vector1 > $vector2)  #  depending on configuration

IMPORTANT NOTES

•

Method naming conventions

Method names completely in lower case indicate a boolean return value.

(Except for the bit vector constructor method ``new()'', of course.)

•

Boolean values

Boolean values in this module are always a numeric zero ("0") for``false'' and a numeric one ("1") for ``true''.

•

Negative numbers

All numeric input parameters passed to any of the methods of this moduleor (in general, but see below) to overloaded operators are regarded asbeing UNSIGNED.

This affects overloaded operators only where numeric factors (as with``<<'', ``>>'' and ``x") are concerned or when theconfiguration (see also the section ``Overloaded operators configuration''immediately below) states that numeric input (which comes in place of oneof the two bit vector object operands the overloaded operator expects) isto be regarded as bit indices (which is the default, however).

As a consequence, whenever you pass a negative number as an argument tosome method of this module (or an overloaded operator - under the conditionsexplained above), it will be treated as a (usually very large) positivenumber due to its internal two's complement binary representation, usuallyresulting in an ``index out of range'' error message and program abortion.

Note that this does not apply to ``big integer'' decimal numbers, whichare (usually) passed as strings, and which may of course be negative(see also the section ``Big integers'' a little further below).

•

Overloaded operators configuration

Note that the behaviour of certain overloaded operators can be changedin various ways by means of the ``Configuration()'' method (for moredetails, see the description of this method further below).

For instance, scalars (i.e., numbers and strings) provided as operandsto overloaded operators are automatically converted to bit vectors,internally.

These scalars are thereby automatically assumed to be indices or to bein hexadecimal, binary, decimal or enumeration format, depending on theconfiguration.

Similarly, when converting bit vectors to strings using double quotes(""), the output format will also depend on the previously chosenconfiguration.

Finally, some overloaded operators may have different semantics dependingon the proper configuration; for instance, the operator ``+'' can be the``union'' operator from set theory or the arithmetic ``add'' operator.

In all cases (input, output and operator semantics), the defaults havebeen chosen in such a way so that the behaviour of the module is backwardcompatible with previous versions.

•

``Big integers''

As long as ``big integers'' (for ``big integer'' arithmetic) are small enoughso that Perl doesn't need scientific notation (exponents) to be able torepresent them internally, you can provide these ``big integer'' constantsto the overloaded operators of this module (or to the method ``from_Dec()")in numeric form (i.e., either as a numeric constant or expression or as a Perlvariable containing a numeric value).

Note that you will get an error message (resulting in program abortion)if your ``big integer'' numbers exceed that limit.

Because this limit is machine-dependent and not obvious to find out,it is strongly recommended that you enclose ALL your ``big integer''constants in your programs in (double or single) quotes.

Examples:

    $vector /= 10;  #  ok because number is small

    $vector /= -10;  #  ok for same reason

    $vector /= "10";  #  always correct

    $vector += "1152921504606846976";  #  quotes probably required here

All examples assume

    Bit::Vector->Configuration("input=decimal");

having been set beforehand.

Note also that this module does not support scientific notation (exponents)for ``big integer'' decimal numbers because you can always make the bit vectorlarge enough for the whole number to fit without loss of precision (as itwould occur if scientific notation were used).

Finally, note that the only characters allowed in ``big integer'' constantstrings are the digits 0..9 and an optional leading sign ("+'' or ``-").

All other characters produce a syntax error.

•

Valid operands for overloaded operators

All overloaded operators expect at least one bit vector operand,in order for the operator to ``know'' that not the usual operationis to be carried out, but rather the overloaded variant.

This is especially true for all unary operators:

                    "$vector"                    if ($vector)                    if (!$vector)                    ~$vector                    -$vector                    abs($vector)                    ++$vector                    $vector++                    --$vector                    $vector--

For obvious reasons the left operand (the ``lvalue") of allassignment operators is also required to be a bit vector:

                        .=                        x=                        <<=                        >>=                        |=                        &=                        ^=                        +=                        -=                        *=                        /=                        %=

In the case of three special operators, namely ``<<'', ``>>'' and ``x'',as well as their related assignment variants, ``<<='', ``>>='' and ``x='',the left operand is ALWAYS a bit vector and the right operandis ALWAYS a number (which is the factor indicating how many timesthe operator is to be applied).

In all truly binary operators, i.e.,

                        .                        |                        &                        ^                        +                        -                        *                        /                        %                    <=>   cmp                     ==    eq                     !=    ne                     <     lt                     <=    le                     >     gt                     >=    ge

one of either operands may be replaced by a Perl scalar, i.e.,a number or a string, either as a Perl constant, a Perl expressionor a Perl variable yielding a number or a string.

The same applies to the right side operand (the ``rvalue") of theremaining assignment operators, i.e.,

                        .=                        |=                        &=                        ^=                        +=                        -=                        *=                        /=                        %=

Note that this Perl scalar should be of the correct type, i.e.,numeric or string, for the chosen configuration, because otherwisea warning message will occur if your program runs under the ``-w''switch of Perl.

The acceptable scalar types for each possible configuration arethe following:

    input = bit indices    (default)  :    numeric    input = hexadecimal               :    string    input = binary                    :    string    input = decimal                   :    string     (in general)    input = decimal                   :    numeric    (if small enough)    input = enumeration               :    string

NOTE ALSO THAT THESE SCALAR OPERANDS ARE CONVERTED TO BIT VECTORS OFTHE SAME SIZE AS THE BIT VECTOR WHICH IS THE OTHER OPERAND.

The only exception from this rule is the concatenation operator(".") and its assignment variant (".="):

If one of the two operands of the concatenation operator (".") isnot a bit vector object but a Perl scalar, the contents of the remainingbit vector operand are converted into a string (the format of whichdepends on the configuration set with the ``Configuration()'' method),which is then concatenated in the proper order (i.e., as indicated by theorder of the two operands) with the Perl scalar (in other words, a stringis returned in such a case instead of a bit vector object!).

If the right side operand (the ``rvalue") of the assignment variant(".=") of the concatenation operator is a Perl scalar, it is convertedinternally to a bit vector of the same size as the left side operand providedthat the configuration states that scalars are to be regarded as indices,decimal strings or enumerations.

If the configuration states that scalars are to be regarded as hexadecimalor boolean strings, however, these strings are converted to bit vectors ofa size matching the length of the input string, i.e., four times the lengthfor hexadecimal strings (because each hexadecimal digit is worth 4 bits) andonce the length for binary strings.

If a decimal number ("big integer") is too large to be stored in abit vector of the given size, a ``numeric overflow error'' occurs.

If a bit index is out of range for the given bit vector, an ``indexout of range'' error occurs.

If a scalar operand cannot be converted successfully due to invalidsyntax, a fatal ``input string syntax error'' is issued.

If the two operands of the operator ``<<'', ``>>''or ``x'' are reversed, a fatal ``reversed operands error'' occurs.

If an operand is neither a bit vector nor a scalar, then a fatal``illegal operand type error'' occurs.

•

Bit order

Note that bit vectors are stored least order bit and least order word firstinternally.

I.e., bit #0 of any given bit vector corresponds to bit #0 of word #0 in thearray of machine words representing the bit vector.

(Where word #0 comes first in memory, i.e., it is stored at the least memoryaddress in the allocated block of memory holding the given bit vector.)

Note however that machine words can be stored least order byte first or last,depending on your system's implementation.

When you are exporting or importing a whole bit vector at once using themethods ``Block_Read()'' and ``Block_Store()'' (the only time in thismodule where this could make any difference), however, a conversion to andfrom ``least order byte first'' order is automatically supplied.

In other words, what ``Block_Read()'' provides and what ``Block_Store()''expects is always in ``least order byte first'' order, regardless of the orderin which words are stored internally on your machine.

This is to make sure that what you export on one machine using ``Block_Read()''can always be read in correctly with ``Block_Store()'' on a different machine.

Note further that whenever bit vectors are converted to and from (binary orhexadecimal) strings, the RIGHTMOST bit is always the LEAST SIGNIFICANT one,and the LEFTMOST bit is always the MOST SIGNIFICANT bit.

This is because in our western culture, numbers are always represented in thisway (least significant to most significant digits go from right to left).

Of course this requires an internal reversion of order, which the correspondingconversion methods perform automatically (without any additional overhead).

•

``Word'' related methods

Note that all methods whose names begin with ``Word_'' are MACHINE-DEPENDENT!

They depend on the size (number of bits) of an ``unsigned int'' (C type) onyour machine.

Therefore, you should only use these methods if you are ABSOLUTELY CERTAINthat portability of your code is not an issue!

Note that you can use arbitrarily large chunks (i.e., fragments of bit vectors)of up to 32 bits IN A PORTABLE WAY using the methods whose names begin with``Chunk_''.

•

Chunk sizes

Note that legal chunk sizes for all methods whose names begin with ``Chunk_''range from ``1'' to ``Bit::Vector->Long_Bits();'' bits ("0'' is NOTallowed!).

In order to make your programs portable, however, you shouldn't use chunk sizeslarger than 32 bits, since this is the minimum size of an ``unsigned long''(C type) on all systems, as prescribed by ANSI C.

•

Matching sizes

In general, for methods involving several bit vectors at the same time, allbit vector arguments must have identical sizes (number of bits), or a fatal``size mismatch'' error will occur.

Exceptions from this rule are the methods ``Concat()'', ``Concat_List()'',``Interval_Copy()'' and ``Interval_Substitute()'', where no conditions atall are imposed on the size of their bit vector arguments, and the method``Multiply()'', where all three bit vector arguments must in principleobey the rule of matching sizes, but where the bit vector in which theresult of the multiplication is to be stored may be larger than the twobit vector arguments containing the factors for the multiplication.

•

Index ranges

All indices for any given bits must lie between ``0'' and ``$vector->Size()-1'',or a fatal ``index out of range'' error will occur.

DESCRIPTION

CLASS METHODS (implemented in C)

•

$version = Bit::Vector->Version();

Returns the current version number of this module.

•

$bits = Bit::Vector->Word_Bits();

Returns the number of bits of an ``unsigned int'' (C type)on your machine.

(An ``unsigned int'' is also called a ``machine word'',hence the name of this method.)

•

$bits = Bit::Vector->Long_Bits();

Returns the number of bits of an ``unsigned long'' (C type)on your machine.

•

$vector = Bit::Vector->new($bits);

This is the bit vector constructor method.

Call this method to create a new bit vector containing ``$bits''bits (with indices ranging from ``0'' to ``$bits-1").

Note that - in contrast to previous versions - bit vectorsof length zero (i.e., with $bits = 0) are permitted now.

The method returns a reference to the newly created bit vector.

A new bit vector is always initialized so that all bits are cleared(turned off).

An exception will be raised if the method is unable to allocate thenecessary memory.

Note that if you specify a negative number for ``$bits'' it will beinterpreted as a large positive number due to its internal two'scomplement binary representation.

In such a case, the bit vector constructor method will obediently attemptto create a bit vector of that size, probably resulting in an exception,as explained above.

•

$vector = Bit::Vector->new_Hex($bits,$string);

This method is an alternative constructor which allows you to createa new bit vector object (with ``$bits'' bits) and to initialize itall in one go.

The method is more efficient than performing these two steps separatelyfirst because in this method, the memory area occupied by the new bitvector is not initialized to zeros (which is pointless in this case),and second because it saves you from the associated overhead of oneadditional method invocation.

The method first calls the bit vector constructor method ``new()''internally, and then passes the given string to the method ``from_Hex()''.

An exception will be raised if the necessary memory cannot be allocated(see the description of the method ``new()'' immediately above forpossible causes) or if the given string cannot be converted successfully(see the description of the method ``from_Hex()'' further below fordetails).

In the latter case, the memory occupied by the new bit vector isreleased first (i.e., ``free"d) before the exception is actuallyraised.

•

$vector = Bit::Vector->new_Bin($bits,$string);

This method is an alternative constructor which allows you to createa new bit vector object (with ``$bits'' bits) and to initialize itall in one go.

The method first calls the bit vector constructor method ``new()''internally, and then passes the given string to the method ``from_Bin()''.

An exception will be raised if the necessary memory cannot be allocated(see the description of the method ``new()'' above for possible causes)or if the given string cannot be converted successfully (see thedescription of the method ``from_Bin()'' further below for details).

In the latter case, the memory occupied by the new bit vector isreleased first (i.e., ``free"d) before the exception is actuallyraised.

•

$vector = Bit::Vector->new_Dec($bits,$string);

This method is an alternative constructor which allows you to createa new bit vector object (with ``$bits'' bits) and to initialize itall in one go.

The method first calls the bit vector constructor method ``new()''internally, and then passes the given string to the method ``from_Dec()''.

In the latter case, the memory occupied by the new bit vector isreleased first (i.e., ``free"d) before the exception is actuallyraised.

•

$vector = Bit::Vector->new_Enum($bits,$string);

This method is an alternative constructor which allows you to createa new bit vector object (with ``$bits'' bits) and to initialize itall in one go.

The method first calls the bit vector constructor method ``new()''internally, and then passes the given string to the method ``from_Enum()''.

In the latter case, the memory occupied by the new bit vector isreleased first (i.e., ``free"d) before the exception is actuallyraised.

•

$vector = Bit::Vector->Concat_List(@vectors);

This method creates a new vector containing all bit vectors from theargument list in concatenated form.

The argument list may contain any number of arguments (includingzero); the only condition is that all arguments must be bit vectors.

There is no condition concerning the length (in number of bits) ofthese arguments.

The vectors from the argument list are not changed in any way.

If the argument list is empty or if all arguments have length zero,the resulting bit vector will also have length zero.

Note that the RIGHTMOST bit vector from the argument list willbecome the LEAST significant part of the resulting bit vector,and the LEFTMOST bit vector from the argument list willbecome the MOST significant part of the resulting bit vector.

OBJECT METHODS (implemented in C)

•

$vec2 = $vec1->new($bits);

This is an alternative way of calling the bit vector constructor method.

Vector ``$vec1'' is not affected by this, it just serves as an anchorfor the method invocation mechanism.

In fact ALL class methods in this module can be called this way,even though this is probably considered to be ``politically incorrect''by OO ("object-orientation") aficionados. ;-)

So even if you are too lazy to type ``Bit::Vector->'' instead of``$vec1->'' (and even though laziness is - allegedly - a programmer'svirtue :-)), maybe it is better not to use this feature if you don'twant to get booed at. ;-)

•

$vec2 = $vec1->Shadow();

Creates a NEW bit vector ``$vec2'' of the SAME SIZE as ``$vec1''but which is EMPTY.

Just like a shadow that has the same shape as the object itoriginates from, but is flat and has no volume, i.e., containsnothing.

•

$vec2 = $vec1->Clone();

Creates a NEW bit vector ``$vec2'' of the SAME SIZE as ``$vec1''which is an EXACT COPY of ``$vec1''.

•

$vector = $vec1->Concat($vec2);

This method returns a new bit vector object which is the result of theconcatenation of the contents of ``$vec1'' and ``$vec2''.

Note that the contents of ``$vec1'' become the MOST significant partof the resulting bit vector, and ``$vec2'' the LEAST significant part.

If both bit vector arguments have length zero, the resulting bit vectorwill also have length zero.

•

$vector = $vec1->Concat_List($vec2,$vec3,...);

This is an alternative way of calling this (class) method as anobject method.

The method returns a new bit vector object which is the result ofthe concatenation of the contents of $vec1 . $vec2 . $vec3 . ...

See the section ``class methods'' above for a detailed description ofthis method.

Note that the argument list may be empty and that all argumentsmust be bit vectors if it isn't.

•

$bits = $vector->Size();

Returns the size (number of bits) the given vector was created with(or ``Resize()"d to).

•

$vector->Resize($bits);

Changes the size of the given vector to the specified number of bits.

This method allows you to change the size of an existing bit vector,preserving as many bits from the old vector as will fit into thenew one (i.e., all bits with indices smaller than the minimum of thesizes of both vectors, old and new).

If the number of machine words needed to store the new vector is smallerthan or equal to the number of words needed to store the old vector, thememory allocated for the old vector is reused for the new one, and onlythe relevant book-keeping information is adjusted accordingly.

This means that even if the number of bits increases, new memory is notnecessarily being allocated (i.e., if the old and the new number of bitsfit into the same number of machine words).

If the number of machine words needed to store the new vector is greaterthan the number of words needed to store the old vector, new memory isallocated for the new vector, the old vector is copied to the new one,the remaining bits in the new vector are cleared (turned off) and the oldvector is deleted, i.e., the memory that was allocated for it is released.

(An exception will be raised if the method is unable to allocate thenecessary memory for the new vector.)

As a consequence, if you decrease the size of a given vector so thatit will use fewer machine words, and increase it again later so that itwill use more words than immediately before but still less than theoriginal vector, new memory will be allocated anyway because theinformation about the size of the original vector is lost wheneveryou resize it.

Note also that if you specify a negative number for ``$bits'' it willbe interpreted as a large positive number due to its internal two'scomplement binary representation.

In such a case, ``Resize()'' will obediently attempt to create a bitvector of that size, probably resulting in an exception, as explainedabove.

Finally, note that - in contrast to previous versions - resizing a bitvector to a size of zero bits (length zero) is now permitted.

•

$vec2->Copy($vec1);

Copies the contents of bit vector ``$vec1'' tobit vector ``$vec2''.

The previous contents of bit vector ``$vec2''get overwritten, i.e., are lost.

Both vectors must exist beforehand, i.e., this methoddoes not CREATE any new bit vector object.

•

$vector->Empty();

Clears all bits in the given vector.

•

$vector->Fill();

Sets all bits in the given vector.

•

$vector->Flip();

Flips (i.e., complements) all bits in the given vector.

•

$vector->Primes();

Clears the given bit vector and sets all bits whoseindices are prime numbers.

This method uses the algorithm known as the ``Sieve ofErathostenes'' internally.

•

$vec2->Reverse($vec1);

This method copies the given vector ``$vec1'' tothe vector ``$vec2'', thereby reversing the orderof all bits.

I.e., the least significant bit of ``$vec1'' becomes themost significant bit of ``$vec2'', whereas the mostsignificant bit of ``$vec1'' becomes the leastsignificant bit of ``$vec2'', and so forthfor all bits in between.

Note that in-place processing is also possible, i.e.,``$vec1'' and ``$vec2'' may be identical.

(Internally, this is the same as$vec1->Interval_Reverse(0,$vec1->Size()-1);.)

•

$vector->Interval_Empty($min,$max);

Clears all bits in the interval [$min..$max] (including both limits)in the given vector.

``$min'' and ``$max'' may have the same value; this is the sameas clearing a single bit with ``Bit_Off()'' (but less efficient).

Note that $vector->Interval_Empty(0,$vector->Size()-1);is the same as $vector->Empty(); (but less efficient).

•

$vector->Interval_Fill($min,$max);

Sets all bits in the interval [$min..$max] (including both limits)in the given vector.

``$min'' and ``$max'' may have the same value; this is the sameas setting a single bit with ``Bit_On()'' (but less efficient).

Note that $vector->Interval_Fill(0,$vector->Size()-1);is the same as $vector->Fill(); (but less efficient).

•

$vector->Interval_Flip($min,$max);

Flips (i.e., complements) all bits in the interval [$min..$max](including both limits) in the given vector.

``$min'' and ``$max'' may have the same value; this is the sameas flipping a single bit with ``bit_flip()'' (but less efficient).

Note that $vector->Interval_Flip(0,$vector->Size()-1);is the same as $vector->Flip(); and$vector->Complement($vector);(but less efficient).

•

$vector->Interval_Reverse($min,$max);

Reverses the order of all bits in the interval [$min..$max](including both limits) in the given vector.

I.e., bits ``$min'' and ``$max'' swap places, and so forthfor all bits in between.

``$min'' and ``$max'' may have the same value; this has noeffect whatsoever, though.

•

if (($min,$max) = $vector->Interval_Scan_inc($start))

Returns the minimum and maximum indices of the next contiguous blockof set bits (i.e., bits in the ``on'' state).

The search starts at index ``$start'' (i.e., "$min" >= "$start")and proceeds upwards (i.e., "$max" >= "$min"), thus repeatedlyincrements the search pointer ``$start'' (internally).

Note though that the contents of the variable (or scalar literal value)``$start'' is NOT altered. I.e., you have to set it to the desiredvalue yourself prior to each call to ``Interval_Scan_inc()'' (see alsothe example given below).

Actually, the bit vector is not searched bit by bit, but one machineword at a time, in order to speed up execution (which means that thismethod is quite efficient).

An empty list is returned if no such block can be found.

Note that a single set bit (surrounded by cleared bits) is a validblock by this definition. In that case the return values for ``$min''and ``$max'' are the same.

Typical use:

    $start = 0;    while (($start < $vector->Size()) &&        (($min,$max) = $vector->Interval_Scan_inc($start)))    {        $start = $max + 2;

        # do something with $min and $max    }

•

if (($min,$max) = $vector->Interval_Scan_dec($start))

Returns the minimum and maximum indices of the next contiguous blockof set bits (i.e., bits in the ``on'' state).

The search starts at index ``$start'' (i.e., "$max" <= "$start")and proceeds downwards (i.e., "$min" <= "$max"), thus repeatedlydecrements the search pointer ``$start'' (internally).

Actually, the bit vector is not searched bit by bit, but one machineword at a time, in order to speed up execution (which means that thismethod is quite efficient).

An empty list is returned if no such block can be found.

Note that a single set bit (surrounded by cleared bits) is a validblock by this definition. In that case the return values for ``$min''and ``$max'' are the same.

Typical use:

    $start = $vector->Size() - 1;    while (($start >= 0) &&        (($min,$max) = $vector->Interval_Scan_dec($start)))    {        $start = $min - 2;

        # do something with $min and $max    }

•

$vec2->Interval_Copy($vec1,$offset2,$offset1,$length);

This method allows you to copy a stretch of contiguous bits (startingat any position ``$offset1'' you choose, with a length of ``$length''bits) from a given ``source'' bit vector ``$vec1'' to another position``$offset2'' in a ``target'' bit vector ``$vec2''.

Note that the two bit vectors ``$vec1'' and ``$vec2'' do NOTneed to have the same (matching) size!

Consequently, any of the two terms ``$offset1 + $length'' and``$offset2 + $length'' (or both) may exceed the actual lengthof its corresponding bit vector ("$vec1->Size()'' and``$vec2->Size()'', respectively).

In such a case, the ``$length'' parameter is automatically reducedinternally so that both terms above are bounded by the number of bitsof their corresponding bit vector.

This may even result in a length of zero, in which case nothing iscopied at all.

(Of course the value of the ``$length'' parameter, supplied by youin the initial method call, may also be zero right from the start!)

Note also that ``$offset1'' and ``$offset2'' must lie within therange ``0'' and, respectively, ``$vec1->Size()-1'' or``$vec2->Size()-1'', or a fatal ``offset out of range'' errorwill occur.

Note further that ``$vec1'' and ``$vec2'' may be identical, i.e.,you may copy a stretch of contiguous bits from one part of a givenbit vector to another part.

The source and the target interval may even overlap, in which casethe copying is automatically performed in ascending or descendingorder (depending on the direction of the copy - downwards or upwardsin the bit vector, respectively) to handle this situation correctly,i.e., so that no bits are being overwritten before they have beencopied themselves.

•

$vec2->Interval_Substitute($vec1,$off2,$len2,$off1,$len1);

This method is (roughly) the same for bit vectors (i.e., arraysof booleans) as what the ``splice'' function in Perl is for lists(i.e., arrays of scalars).

(See the splice entry in the perlfunc manpage for more details about this function.)

The method allows you to substitute a stretch of contiguous bits(defined by a position (offset) ``$off1'' and a length of ``$len1''bits) from a given ``source'' bit vector ``$vec1'' for a differentstretch of contiguous bits (defined by a position (offset) ``$off2''and a length of ``$len2'' bits) in another, ``target'' bit vector``$vec2''.

Note that the two bit vectors ``$vec1'' and ``$vec2'' do NOTneed to have the same (matching) size!

Note further that ``$off1'' and ``$off2'' must lie within therange ``0'' and, respectively, ``$vec1->Size()'' or``$vec2->Size()'', or a fatal ``offset out of range'' errorwill occur.

Alert readers will have noticed that these upper limits are NOT``$vec1->Size()-1'' and ``$vec2->Size()-1'', as they wouldbe for any other method in this module, but that these offsets mayactually point to one position PAST THE END of the correspondingbit vector.

This is necessary in order to make it possible to APPEND a givenstretch of bits to the target bit vector instead of REPLACINGsomething in it.

For reasons of symmetry and generality, the same applies to the offsetin the source bit vector, even though such an offset (one position pastthe end of the bit vector) does not serve any practical purpose there(but does not cause any harm either).

(Actually this saves you from the need of testing for this special case,in certain circumstances.)

Note that whenever the term ``$off1 + $len1'' exceeds the size``$vec1->Size()'' of bit vector ``$vec1'' (or if ``$off2 + $len2''exceeds ``$vec2->Size()"), the corresponding length ("$len1''or ``$len2'', respectively) is automatically reduced internallyso that ``$off1 + $len1 <= $vec1->Size()'' (and``$off2 + $len2 <= $vec2->Size()") holds.

(Note that this does NOT alter the intended result, even thoughthis may seem counter-intuitive at first!)

This may even result in a length ("$len1'' or ``$len2") of zero.

A length of zero for the interval in the SOURCE bit vector("$len1 == 0") means that the indicated stretch of bits inthe target bit vector (starting at position ``$off2") is tobe replaced by NOTHING, i.e., is to be DELETED.

A length of zero for the interval in the TARGET bit vector("$len2 == 0") means that NOTHING is replaced, and that thestretch of bits from the source bit vector is simply INSERTEDinto the target bit vector at the indicated position ("$off2").

If both length parameters are zero, nothing is done at all.

Note that in contrast to any other method in this module (especially``Interval_Copy()'', ``Insert()'' and ``Delete()"), this methodIMPLICITLY and AUTOMATICALLY adapts the length of the resultingbit vector as needed, as given by

        $size = $vec2->Size();   #  before        $size += $len1 - $len2;  #  after

(The only other method in this module that changes the size of a bitvector is the method ``Resize()''.)

In other words, replacing a given interval of bits in the target bitvector with a longer or shorter stretch of bits from the source bitvector, or simply inserting ("$len2 == 0") a stretch of bits intoor deleting ("$len1 == 0") an interval of bits from the target bitvector will automatically increase or decrease, respectively, the sizeof the target bit vector accordingly.

For the sake of generality, this may even result in a bit vector witha size of zero (containing no bits at all).

This is also the reason why bit vectors of length zero are permittedin this module in the first place, starting with version 5.0.

Finally, note that ``$vec1'' and ``$vec2'' may be identical, i.e.,in-place processing is possible.

(If you think about that for a while or if you look at the code,you will see that this is far from trivial!)

•

if ($vector->is_empty())

Tests wether the given bit vector is empty, i.e., wether ALL ofits bits are cleared (in the ``off'' state).

In ``big integer'' arithmetic, this is equivalent to testing wetherthe number stored in the bit vector is zero ("0").

Returns ``true'' ("1") if the bit vector is empty and ``false'' ("0")otherwise.

Note that this method also returns ``true'' ("1") if the given bitvector has a length of zero, i.e., if it contains no bits at all.

•

if ($vector->is_full())

Tests wether the given bit vector is full, i.e., wether ALL ofits bits are set (in the ``on'' state).

In ``big integer'' arithmetic, this is equivalent to testing wetherthe number stored in the bit vector is minus one (''-1").

Returns ``true'' ("1") if the bit vector is full and ``false'' ("0")otherwise.

If the given bit vector has a length of zero (i.e., if it containsno bits at all), this method returns ``false'' ("0").

•

if ($vec1->equal($vec2))

Tests the two given bit vectors for equality.

Returns ``true'' ("1") if the two bit vectors are exactcopies of one another and ``false'' ("0") otherwise.

•

$cmp = $vec1->Lexicompare($vec2);

Compares the two given bit vectors, which areregarded as UNSIGNED numbers in binary representation.

The method returns ``-1'' if the first bit vector is smallerthan the second bit vector, ``0'' if the two bit vectors areexact copies of one another and ``1'' if the first bit vectoris greater than the second bit vector.

•

$cmp = $vec1->Compare($vec2);

Compares the two given bit vectors, which areregarded as SIGNED numbers in binary representation.

•

$string = $vector->to_Hex();

Returns a hexadecimal string representing the given bit vector.

Note that this representation is quite compact, in that it onlyneeds twice the number of bytes needed to store the bit vectoritself, internally.

Note also that since a hexadecimal digit is always worth four bits,the length of the resulting string is always a multiple of four bits,regardless of the true length (in bits) of the given bit vector.

Moreover, in order to simplify the conversion, the unused bits inthe bit vector (if any) are also converted, which may produce someextra (but innocuous) leading hexadecimal zeros.

Finally, note that the LEAST significant hexadecimal digit islocated at the RIGHT end of the resulting string, and the MOSTsignificant digit at the LEFT end.

•

$vector->from_Hex($string);

Allows to read in the contents of a bit vector from a hexadecimalstring, such as returned by the method ``to_Hex()'' (see above).

Remember that the least significant bits are always to the right of ahexadecimal string, and the most significant bits to the left. Therefore,the string is actually read in from right to left while the bit vectoris filled accordingly, 4 bits at a time, starting with the least significantbits and going upward to the most significant bits.

If the given string contains less hexadecimal digits than are neededto completely fill the given bit vector, the remaining (most significant)bits are all cleared.

This also means that, even if the given string does not contain enough digitsto completely fill the given bit vector, the previous contents of thebit vector are erased completely.

If the given string is longer than it needs to fill the given bit vector,the superfluous characters are simply ignored.

(In fact they are ignored completely - they are not even checked forproper syntax. See also below for more about that.)

This behaviour is intentional so that you may read in the stringrepresenting one bit vector into another bit vector of differentsize, i.e., as much of it as will fit.

If during the process of reading the given string any character isencountered which is not a hexadecimal digit, a fatal syntax errorensues ("input string syntax error").

•

$string = $vector->to_Bin();

Returns a binary string representing the given bit vector.

Example:

  $vector = Bit::Vector->new(8);  $vector->Primes();  $string = $vector->to_Bin();  print "'$string'\n";

This prints:

  '10101100'

(Bits #7, #5, #3 and #2 are set.)

Note that the LEAST significant bit is located at the RIGHTend of the resulting string, and the MOST significant bit atthe LEFT end.

•

$vector->from_Bin($string);

This method allows you to read in the contents of a bit vector from abinary string, such as returned by the method ``to_Bin()'' (see above).

Note that this method assumes that the LEAST significant bit is located atthe RIGHT end of the binary string, and the MOST significant bit at theLEFT end. Therefore, the string is actually read in from right to leftwhile the bit vector is filled accordingly, one bit at a time, starting withthe least significant bit and going upward to the most significant bit.

If the given string contains less binary digits ("0'' and ``1") than areneeded to completely fill the given bit vector, the remaining (most significant)bits are all cleared.

This also means that, even if the given string does not contain enough digitsto completely fill the given bit vector, the previous contents of thebit vector are erased completely.

If the given string is longer than it needs to fill the given bit vector,the superfluous characters are simply ignored.

(In fact they are ignored completely - they are not even checked forproper syntax. See also below for more about that.)

This behaviour is intentional so that you may read in the stringrepresenting one bit vector into another bit vector of differentsize, i.e., as much of it as will fit.

If during the process of reading the given string any character isencountered which is not either ``0'' or ``1'', a fatal syntax errorensues ("input string syntax error").

•

$string = $vector->to_Dec();

This method returns a string representing the contents of the given bitvector converted to decimal (base 10).

Note that this method assumes the given bit vector to be SIGNED (andto contain a number in two's complement binary representation).

Consequently, whenever the most significant bit of the given bit vectoris set, the number stored in it is regarded as being NEGATIVE.

The resulting string can be fed into ``from_Dec()'' (see below) in orderto copy the contents of this bit vector to another one (or to restore thecontents of this one). This is not advisable, though, since this would bevery inefficient (there are much more efficient methods for storing andcopying bit vectors in this module).

Note that such conversion from binary to decimal is inherently slowsince the bit vector has to be repeatedly divided by 10 with remainderuntil the quotient becomes 0 (each remainder in turn represents a singledecimal digit of the resulting string).

This is also true for the implementation of this method in this module,even though a considerable effort has been made to speed it up: instead ofrepeatedly dividing by 10, the bit vector is repeatedly divided by thelargest power of 10 that will fit into a machine word. The remainder isthen repeatedly divided by 10 using only machine word arithmetics, whichis much faster than dividing the whole bit vector ("divide and rule'' principle).

According to my own measurements, this resulted in an 8-fold speed increaseover the straightforward approach.

Still, conversion to decimal should be used only where absolutely necessary.

Keep the resulting string stored in some variable if you need it again,instead of converting the bit vector all over again.

Beware that if you set the configuration for overloaded operators to``output=decimal'', this method will be called for every bit vectorenclosed in double quotes!

•

$vector->from_Dec($string);

This method allows you to convert a given decimal number, which may bepositive or negative, into two's complement binary representation, whichis then stored in the given bit vector.

The decimal number should always be provided as a string, to avoid possibletruncation (due to the limited precision of integers in Perl) or formatting(due to Perl's use of scientific notation for large numbers), which wouldlead to errors.

If the binary representation of the given decimal number is too big to fitinto the given bit vector (if the given bit vector does not contain enoughbits to hold it), a fatal ``numeric overflow error'' occurs.

If the input string contains other characters than decimal digits (0-9)and an optional leading sign ("+'' or ``-"), a fatal ``input stringsyntax error'' occurs.

If possible program abortion is unwanted or intolerable, use``eval'', like this:

  eval { $vector->from_Dec("1152921504606846976"); };  if ($@)  {      # an error occurred  }

There are four possible error messages:

  if ($@ =~ /item is not a string/)

  if ($@ =~ /input string syntax error/)

  if ($@ =~ /numeric overflow error/)

  if ($@ =~ /unable to allocate memory/)

Note that the conversion from decimal to binary is costly in terms ofprocessing time, since a lot of multiplications have to be carried out(in principle, each decimal digit must be multiplied with the binaryrepresentation of the power of 10 corresponding to its position inthe decimal number, i.e., 1, 10, 100, 1000, 10000 and so on).

This is not as time consuming as the opposite conversion, from binaryto decimal (where successive divisions have to be carried out, whichare even more expensive than multiplications), but still noticeable.

Again (as in the case of ``to_Dec()"), the implementation of thismethod in this module uses the principle of ``divide and rule'' in orderto speed up the conversion, i.e., as many decimal digits as possibleare first accumulated (converted) in a machine word and only thenstored in the given bit vector.

Even so, use this method only where absolutely necessary if speed isan important consideration in your application.

Beware that if you set the configuration for overloaded operators to``input=decimal'', this method will be called for every scalar operandyou use!

•

$string = $vector->to_Enum();

Converts the given bit vector or set into an enumeration of singleindices and ranges of indices (''.newsrc'' style), representing thebits that are set ("1") in the bit vector.

Example:

  $vector = Bit::Vector->new(20);  $vector->Bit_On(2);  $vector->Bit_On(3);  $vector->Bit_On(11);  $vector->Interval_Fill(5,7);  $vector->Interval_Fill(13,19);  print "'", $vector->to_Enum(), "'\n";

which prints

  '2,3,5-7,11,13-19'

If the given bit vector is empty, the resulting string willalso be empty.

Note, by the way, that the above example can also be writtena little handier, perhaps, as follows:

  Bit::Vector->Configuration("out=enum");  $vector = Bit::Vector->new(20);  $vector->Index_List_Store(2,3,5,6,7,11,13,14,15,16,17,18,19);  print "'$vector'\n";

•

$vector->from_Enum($string);

This method first empties the given bit vector and then tries toset the bits and ranges of bits specified in the given string.

The string ``$string'' must only contain unsigned integersor ranges of integers (two unsigned integers separated by adash ``-"), separated by commas ('',").

All other characters are disallowed (including white space!)and will lead to a fatal ``input string syntax error''.

In each range, the first integer (the lower limit of the range)must always be less than or equal to the second integer (theupper limit), or a fatal ``minimum > maximum index'' error occurs.

All integers must lie in the permitted range for the givenbit vector, i.e., they must lie between ``0'' and``$vector->Size()-1''.

If this condition is not met, a fatal ``index out of range''error occurs.

If possible program abortion is unwanted or intolerable, use``eval'', like this:

  eval { $vector->from_Enum("2,3,5-7,11,13-19"); };  if ($@)  {      # an error occurred  }

There are four possible error messages:

  if ($@ =~ /item is not a string/)

  if ($@ =~ /input string syntax error/)

  if ($@ =~ /index out of range/)

  if ($@ =~ /minimum > maximum index/)

Note that the order of the indices and ranges is irrelevant,i.e.,

  eval { $vector->from_Enum("11,5-7,3,13-19,2"); };

results in the same vector as in the example above.

Ranges and indices may also overlap.

This is because each (single) index in the string is passedto the method ``Bit_On()'', internally, and each range tothe method ``Interval_Fill()''.

This means that the resulting bit vector is just the unionof all the indices and ranges specified in the given string.

•

$vector->Bit_Off($index);

Clears the bit with index ``$index'' in the given vector.

•

$vector->Bit_On($index);

Sets the bit with index ``$index'' in the given vector.

•

$vector->bit_flip($index)

Flips (i.e., complements) the bit with index ``$index''in the given vector.

Moreover, this method returns the NEW state of thebit in question, i.e., it returns ``0'' if the bit iscleared or ``1'' if the bit is set (AFTER flipping it).

•

if ($vector->bit_test($index))

Returns the current state of the bit with index ``$index''in the given vector, i.e., returns ``0'' if it is cleared(in the ``off'' state) or ``1'' if it is set (in the ``on'' state).

•

$vector->Bit_Copy($index,$bit);

Sets the bit with index ``$index'' in the given vector eitherto ``0'' or ``1'' depending on the boolean value ``$bit''.

•

$vector->LSB($bit);

Allows you to set the least significant bit in the given bitvector to the value given by the boolean parameter ``$bit''.

This is a (faster) shortcut for ``$vector->Bit_Copy(0,$bit);''.

•

$vector->MSB($bit);

Allows you to set the most significant bit in the given bitvector to the value given by the boolean parameter ``$bit''.

This is a (faster) shortcut for``$vector->Bit_Copy($vector->Size()-1,$bit);''.

•

$bit = $vector->lsb();

Returns the least significant bit of the given bit vector.

This is a (faster) shortcut for ``$bit = $vector->bit_test(0);''.

•

$bit = $vector->msb();

Returns the most significant bit of the given bit vector.

This is a (faster) shortcut for``$bit = $vector->bit_test($vector->Size()-1);''.

•

$carry_out = $vector->rotate_left();

  carry             MSB           vector:           LSB   out:  +---+            +---+---+---+---     ---+---+---+---+  |   |  <---+---  |   |   |   |    ...    |   |   |   |  <---+  +---+      |     +---+---+---+---     ---+---+---+---+      |             |                                                |             +------------------------------------------------+

The least significant bit (LSB) is the bit with index ``0'', the mostsignificant bit (MSB) is the bit with index ``$vector->Size()-1''.

•

$carry_out = $vector->rotate_right();

          MSB           vector:           LSB            carry                                                          out:         +---+---+---+---     ---+---+---+---+           +---+  +--->  |   |   |   |    ...    |   |   |   |  ---+---> |   |  |      +---+---+---+---     ---+---+---+---+     |     +---+  |                                                |  +------------------------------------------------+

The least significant bit (LSB) is the bit with index ``0'', the mostsignificant bit (MSB) is the bit with index ``$vector->Size()-1''.

•

$carry_out = $vector->shift_left($carry_in);

  carry         MSB           vector:           LSB         carry   out:                                                      in:  +---+        +---+---+---+---     ---+---+---+---+        +---+  |   |  <---  |   |   |   |    ...    |   |   |   |  <---  |   |  +---+        +---+---+---+---     ---+---+---+---+        +---+

The least significant bit (LSB) is the bit with index ``0'', the mostsignificant bit (MSB) is the bit with index ``$vector->Size()-1''.

•

$carry_out = $vector->shift_right($carry_in);

  carry         MSB           vector:           LSB         carry   in:                                                       out:  +---+        +---+---+---+---     ---+---+---+---+        +---+  |   |  --->  |   |   |   |    ...    |   |   |   |  --->  |   |  +---+        +---+---+---+---     ---+---+---+---+        +---+

The least significant bit (LSB) is the bit with index ``0'', the mostsignificant bit (MSB) is the bit with index ``$vector->Size()-1''.

•

$vector->Move_Left($bits);

Shifts the given bit vector left by ``$bits'' bits, i.e., inserts ``$bits''new bits at the lower end (least significant bit) of the bit vector,moving all other bits up by ``$bits'' places, thereby losing the ``$bits''most significant bits.

The inserted new bits are all cleared (set to the ``off'' state).

This method does nothing if ``$bits'' is equal to zero.

Beware that the whole bit vector is cleared WITHOUT WARNING if``$bits'' is greater than or equal to the size of the given bit vector!

In fact this method is equivalent to

  for ( $i = 0; $i < $bits; $i++ ) { $vector->shift_left(0); }

except that it is much more efficient (for ``$bits'' greater than orequal to the number of bits in a machine word on your system) thanthis straightforward approach.

•

$vector->Move_Right($bits);

Shifts the given bit vector right by ``$bits'' bits, i.e., deletes the``$bits'' least significant bits of the bit vector, moving all other bitsdown by ``$bits'' places, thereby creating ``$bits'' new bits at the upperend (most significant bit) of the bit vector.

These new bits are all cleared (set to the ``off'' state).

This method does nothing if ``$bits'' is equal to zero.

Beware that the whole bit vector is cleared WITHOUT WARNING if``$bits'' is greater than or equal to the size of the given bit vector!

In fact this method is equivalent to

  for ( $i = 0; $i < $bits; $i++ ) { $vector->shift_right(0); }

except that it is much more efficient (for ``$bits'' greater than orequal to the number of bits in a machine word on your system) thanthis straightforward approach.

•

$vector->Insert($offset,$bits);

This method inserts ``$bits'' fresh new bits at position ``$offset''in the given bit vector.

The ``$bits'' most significant bits are lost, and all bits startingwith bit number ``$offset'' up to and including bit number``$vector->Size()-$bits-1'' are moved up by ``$bits'' places.

The now vacant ``$bits'' bits starting at bit number ``$offset''(up to and including bit number ``$offset+$bits-1") are then setto zero (cleared).

Note that this method does NOT increase the size of the given bitvector, i.e., the bit vector is NOT extended at its upper end to``rescue'' the ``$bits'' uppermost (most significant) bits - instead,these bits are lost forever.

If you don't want this to happen, you have to increase the size of thegiven bit vector EXPLICITLY and BEFORE you perform the ``Insert''operation, with a statement such as the following:

  $vector->Resize($vector->Size() + $bits);

Or use the method ``Interval_Substitute()'' instead of ``Insert()'',which performs automatic growing and shrinking of its target bit vector.

Note also that ``$offset'' must lie in the permitted range between``0'' and ``$vector->Size()-1'', or a fatal ``offset out of range''error will occur.

If the term ``$offset + $bits'' exceeds ``$vector->Size()-1'',all the bits starting with bit number ``$offset'' up to bit number``$vector->Size()-1'' are simply cleared.

•

$vector->Delete($offset,$bits);

This method deletes, i.e., removes the bits starting at position``$offset'' up to and including bit number ``$offset+$bits-1''from the given bit vector.

The remaining uppermost bits (starting at position ``$offset+$bits''up to and including bit number ``$vector->Size()-1") are moveddown by ``$bits'' places.

The now vacant uppermost (most significant) ``$bits'' bits are thenset to zero (cleared).

Note that this method does NOT decrease the size of the given bitvector, i.e., the bit vector is NOT clipped at its upper end to``get rid of'' the vacant ``$bits'' uppermost bits.

If you don't want this, i.e., if you want the bit vector to shrinkaccordingly, you have to do so EXPLICITLY and AFTER the ``Delete''operation, with a couple of statements such as these:

  $size = $vector->Size();  if ($bits > $size) { $bits = $size; }  $vector->Resize($size - $bits);

Or use the method ``Interval_Substitute()'' instead of ``Delete()'',which performs automatic growing and shrinking of its target bit vector.

Note also that ``$offset'' must lie in the permitted range between``0'' and ``$vector->Size()-1'', or a fatal ``offset out of range''error will occur.

If the term ``$offset + $bits'' exceeds ``$vector->Size()-1'',all the bits starting with bit number ``$offset'' up to bit number``$vector->Size()-1'' are simply cleared.

•

$carry = $vector->increment();

This method increments the given bit vector.

Note that this method regards bit vectors as being unsigned,i.e., the largest possible positive number is directlyfollowed by the smallest possible (or greatest possible,speaking in absolute terms) negative number:

  before:  2 ^ (b-1) - 1    (= "0111...1111")  after:   2 ^ (b-1)        (= "1000...0000")

where ``b'' is the number of bits of the given bit vector.

The method returns ``false'' ("0") in all cases except when acarry-over occurs (in which case it returns ``true'', i.e., ``1"),which happens when the number ``1111...1111'' is incremented,which gives ``0000...0000'' plus a carry-over to the next higher(binary) digit.

This can be used for the terminating condition of a ``while'' loop,for instance, in order to cycle through all possible values thebit vector can assume.

•

$carry = $vector->decrement();

This method decrements the given bit vector.

Note that this method regards bit vectors as being unsigned,i.e., the smallest possible (or greatest possible, speakingin absolute terms) negative number is directly followed bythe largest possible positive number:

  before:  2 ^ (b-1)        (= "1000...0000")  after:   2 ^ (b-1) - 1    (= "0111...1111")

where ``b'' is the number of bits of the given bit vector.

The method returns ``false'' ("0") in all cases except when acarry-over occurs (in which case it returns ``true'', i.e., ``1"),which happens when the number ``0000...0000'' is decremented,which gives ``1111...1111'' minus a carry-over to the next higher(binary) digit.

This can be used for the terminating condition of a ``while'' loop,for instance, in order to cycle through all possible values thebit vector can assume.

•

$carry = $vec3->add($vec1,$vec2,$carry);

This method adds the two numbers contained in bit vector ``$vec1''and ``$vec2'' with carry ``$carry'' and stores the result inbit vector ``$vec3''.

I.e.,
$vec3 = $vec1 + $vec2 + $carry

Note that the ``$carry'' parameter is a boolean value, i.e.,only its least significant bit is taken into account. (Think ofit as though ``$carry &= 1;'' was always executed internally.)

The method returns a boolean value which indicates if a carry-over(to the next higher bit) has occured.

The carry in- and output is needed mainly for cascading, i.e.,to add numbers that are fragmented into several pieces.

Example:

  # initialize

  for ( $i = 0; $i < $n; $i++ )  {      $a[$i] = Bit::Vector->new($bits);      $b[$i] = Bit::Vector->new($bits);      $c[$i] = Bit::Vector->new($bits);  }

  # fill @a and @b

  # $a[  0 ] is low order part,  # $a[$n-1] is high order part,  # and same for @b

  # add

  $carry = 0;  for ( $i = 0; $i < $n; $i++ )  {      $carry = $c[$i]->add($a[$i],$b[$i],$carry);  }

Note that it makes no difference to this method wether the numbersin ``$vec1'' and ``$vec2'' are unsigned or signed (i.e., in two'scomplement binary representation).

Note however that the return value (carry-over) is not meaningfulwhen the numbers are SIGNED.

Moreover, when the numbers are signed, a special type of error canoccur which is commonly called an ``overflow error''.

An overflow error occurs when the sign of the result (its mostsignificant bit) is flipped (i.e., falsified) by a carry-overfrom the next-lower bit position.

It is your own responsibility to make sure that no overflow erroroccurs if the numbers are signed.

To make absolutely sure that no overflow error can occur, makeyour bit vectors at least one bit longer than the largest numberyou wish to represent needs, right from the start, or proceed asfollows:

    $msb1 = $vec1->msb();    $msb2 = $vec2->msb();    $vec1->Resize($vec1->Size()+1);    $vec2->Resize($vec2->Size()+1);    $vec3->Resize($vec3->Size()+1);    $vec1->MSB($msb1);    $vec2->MSB($msb2);    $c_o = $vec3->add($vec1,$vec2,$c_i);

•

$carry = $vec3->subtract($vec1,$vec2,$carry);

This method subtracts the two numbers contained in bit vector``$vec1'' and ``$vec2'' with carry ``$carry'' and stores theresult in bit vector ``$vec3''.

I.e.,
$vec3 = $vec1 - $vec2 - $carry

Note that the ``$carry'' parameter is a boolean value, i.e.,only its least significant bit is taken into account. (Think ofit as though ``$carry &= 1;'' was always executed internally.)

The method returns a boolean value which indicates if a carry-over(to the next higher bit) has occured.

The carry in- and output is needed mainly for cascading, i.e.,to subtract numbers that are fragmented into several pieces.

Example:

  # initialize

  for ( $i = 0; $i < $n; $i++ )  {      $a[$i] = Bit::Vector->new($bits);      $b[$i] = Bit::Vector->new($bits);      $c[$i] = Bit::Vector->new($bits);  }

  # fill @a and @b

  # $a[  0 ] is low order part,  # $a[$n-1] is high order part,  # and same for @b

  # subtract

  $carry = 0;  for ( $i = 0; $i < $n; $i++ )  {      $carry = $c[$i]->subtract($a[$i],$b[$i],$carry);  }

Note that it makes no difference to this method wether the numbersin ``$vec1'' and ``$vec2'' are unsigned or signed (i.e., in two'scomplement binary representation).

Note however that the return value (carry-over) is not meaningfulwhen the numbers are SIGNED.

Moreover, when the numbers are signed, a special type of error canoccur which is commonly called an ``overflow error''.

An overflow error occurs when the sign of the result (its mostsignificant bit) is flipped (i.e., falsified) by a carry-overfrom the next-lower bit position.

It is your own responsibility to make sure that no overflow erroroccurs if the numbers are signed.

To make absolutely sure that no overflow error can occur, makeyour bit vectors at least one bit longer than the largest numberyou wish to represent needs, right from the start, or proceed asfollows:

    $msb1 = $vec1->msb();    $msb2 = $vec2->msb();    $vec1->Resize($vec1->Size()+1);    $vec2->Resize($vec2->Size()+1);    $vec3->Resize($vec3->Size()+1);    $vec1->MSB($msb1);    $vec2->MSB($msb2);    $c_o = $vec3->subtract($vec1,$vec2,$c_i);

•

$vec2->Negate($vec1);

This method calculates the two's complement of the number in bitvector ``$vec1'' and stores the result in bit vector ``$vec2''.

Calculating the two's complement of a given number in binary representationconsists of inverting all bits and incrementing the result by one.

This is the same as changing the sign of the given number from ``+'' to``-'' or vice-versa. In other words, applying this method twice on a givennumber yields the original number again.

Note that in-place processing is also possible, i.e., ``$vec1'' and``$vec2'' may be identical.

Most importantly, beware that this method produces a counter-intuitiveresult if the number contained in bit vector ``$vec1'' is 2 ^ (n-1)(i.e., ``1000...0000"), where ``n'' is the number of bits the given bitvector contains: The negated value of this number is the number itself!

•

$vec2->Absolute($vec1);

Depending on the sign (i.e., the most significant bit) of the number inbit vector ``$vec1'', the contents of bit vector ``$vec1'' are copiedto bit vector ``$vec2'' either with the method ``Copy()'' (if the numberin bit vector ``$vec1'' is positive), or with ``Negate()'' (if the numberin bit vector ``$vec1'' is negative).

In other words, this method calculates the absolute value of the numberin bit vector ``$vec1'' and stores the result in bit vector ``$vec2''.

Note that in-place processing is also possible, i.e., ``$vec1'' and``$vec2'' may be identical.

•

$sign = $vector->Sign();

This method returns ``0'' if all bits in the given bit vector are cleared,i.e., if the given bit vector contains the number ``0'', or if the givenbit vector has a length of zero (contains no bits at all).

If not all bits are cleared, this method returns ``-1'' if the mostsignificant bit is set (i.e., if the bit vector contains a negativenumber), or ``1'' otherwise (i.e., if the bit vector contains apositive number).

•

$vec3->Multiply($vec1,$vec2);

This method multiplies the two numbers contained in bit vector ``$vec1''and ``$vec2'' and stores the result in bit vector ``$vec3''.

Note that this method regards its arguments as SIGNED.

If you want to make sure that a large number can never be treated as beingnegative by mistake, make your bit vectors at least one bit longer than thelargest number you wish to represent, right from the start, or proceed asfollows:

    $msb1 = $vec1->msb();    $msb2 = $vec2->msb();    $vec1->Resize($vec1->Size()+1);    $vec2->Resize($vec2->Size()+1);    $vec3->Resize($vec3->Size()+1);    $vec1->MSB($msb1);    $vec2->MSB($msb2);    $vec3->Multiply($vec1,$vec2);

Note also that all three bit vector arguments must in principle obey therule of matching sizes, but that the bit vector ``$vec3'' may be largerthan the two factors ``$vec1'' and ``$vec2''.

In fact multiplying two binary numbers with ``n'' bits may yield a resultwhich is at most ``2n'' bits long.

Therefore, it is usually a good idea to let bit vector ``$vec3'' havetwice the size of bit vector ``$vec1'' and ``$vec2'', unless you areabsolutely sure that the result will fit into a bit vector of the samesize as the two factors.

If you are wrong, a fatal ``numeric overflow error'' will occur.

Finally, note that in-place processing is possible, i.e., ``$vec3''may be identical with ``$vec1'' or ``$vec2'', or both.

•

$quot->Divide($vec1,$vec2,$rest);

This method divides the two numbers contained in bit vector ``$vec1''and ``$vec2'' and stores the quotient in bit vector ``$quot'' andthe remainder in bit vector ``$rest''.

I.e.,
$quot = $vec1 / $vec2; # div
$rest = $vec1 % $vec2; # mod

Therefore, ``$quot'' and ``$rest'' must be two DISTINCT bit vectors,or a fatal ``Q and R must be distinct'' error will occur.

Note also that a fatal ``division by zero error'' will occur if ``$vec2''is equal to zero.

Note further that this method regards its arguments as SIGNED.

    $msb1 = $vec1->msb();    $msb2 = $vec2->msb();    $vec1->Resize($vec1->Size()+1);    $vec2->Resize($vec2->Size()+1);    $quot->Resize($quot->Size()+1);    $rest->Resize($rest->Size()+1);    $vec1->MSB($msb1);    $vec2->MSB($msb2);    $quot->Divide($vec1,$vec2,$rest);

Finally, note that in-place processing is possible, i.e., ``$quot''may be identical with ``$vec1'' or ``$vec2'' or both, and ``$rest''may also be identical with ``$vec1'' or ``$vec2'' or both, as longas ``$quot'' and ``$rest'' are distinct. (!)

•

$vec3->GCD($vec1,$vec2);

This method calculates the ``Greatest Common Divisor'' of the two numberscontained in bit vector ``$vec1'' and ``$vec2'' and stores the resultin bit vector ``$vec3''.

The method uses Euklid's algorithm internally:

    int GCD(int a, int b)    {        int t;

        while (b != 0)        {            t = a % b; /* = remainder of (a div b) */            a = b;            b = t;        }        return(a);    }

Note that a fatal ``division by zero error'' will occur if any of the twonumbers is equal to zero.

Note also that this method regards its two arguments as SIGNED butthat it actually uses the ABSOLUTE VALUE of its two arguments internally,i.e., the RESULT of this method will ALWAYS be POSITIVE.

•

$vector->Block_Store($buffer);

This method allows you to load the contents of a given bit vector inone go.

This is useful when you store the contents of a bit vector in a file,for instance (using method ``Block_Read()"), and when you want torestore the previously saved bit vector.

For this, ``$buffer'' MUST be a string (NO automatic conversionfrom numeric to string is provided here as would normally in Perl!)containing the bit vector in ``low order byte first'' order.

If the given string is shorter than what is needed to completely fillthe given bit vector, the remaining (most significant) bytes of thebit vector are filled with zeros, i.e., the previous contents of thebit vector are always erased completely.

If the given string is longer than what is needed to completely fillthe given bit vector, the superfluous bytes are simply ignored.

See the sysread entry in the perlfunc manpage for how to read in the contents of ``$buffer''from a file prior to passing it to this method.

•

$buffer = $vector->Block_Read();

This method allows you to export the contents of a given bit vector inone block.

This is useful when you want to save the contents of a bit vector forlater, for instance in a file.

The advantage of this method is that it allows you to do so in thecompactest possible format, in binary.

The method returns a Perl string which contains an exact copy of thecontents of the given bit vector in ``low order byte first'' order.

See the syswrite entry in the perlfunc manpage for how to write the data from this stringto a file.

•

$size = $vector->Word_Size();

Each bit vector is internally organized as an array of machine words.

The methods whose names begin with ``Word_'' allow you to access thisinternal array of machine words.

Note that because the size of a machine word may vary from system tosystem, these methods are inherently MACHINE-DEPENDENT!

Therefore, DO NOT USE these methods unless you are absolutely certainthat portability of your code is not an issue!

You have been warned!

To be machine-independent, use the methods whose names begin with ``Chunk_''instead, with chunks sizes no greater than 32 bits.

The method ``Word_Size()'' returns the number of machine words that theinternal array of words of the given bit vector contains.

This is similar in function to the term ``scalar(@array)'' for a Perl array.

•

$vector->Word_Store($offset,$word);

This method allows you to store a given value ``$word'' at a givenposition ``$offset'' in the internal array of words of the givenbit vector.

Note that ``$offset'' must lie in the permitted range between ``0''and ``$vector->Word_Size()-1'', or a fatal ``offset out of range''error will occur.

This method is similar in function to the expression``$array[$offset] = $word;'' for a Perl array.

•

$word = $vector->Word_Read($offset);

This method allows you to access the value of a given machine wordat position ``$offset'' in the internal array of words of the givenbit vector.

Note that ``$offset'' must lie in the permitted range between ``0''and ``$vector->Word_Size()-1'', or a fatal ``offset out of range''error will occur.

This method is similar in function to the expression``$word = $array[$offset];'' for a Perl array.

•

$vector->Word_List_Store(@words);

This method allows you to store a list of values ``@words'' in theinternal array of machine words of the given bit vector.

Thereby the LEFTMOST value in the list ("$words[0]") is storedin the LEAST significant word of the internal array of words (theone with offset ``0"), the next value from the list ("$words[1]")is stored in the word with offset ``1'', and so on, as intuitivelyexpected.

If the list ``@words'' contains fewer elements than the internalarray of words of the given bit vector contains machine words,the remaining (most significant) words are filled with zeros.

If the list ``@words'' contains more elements than the internalarray of words of the given bit vector contains machine words,the superfluous values are simply ignored.

This method is comparable in function to the expression``@array = @words;'' for a Perl array.

•

@words = $vector->Word_List_Read();

This method allows you to retrieve the internal array of machinewords of the given bit vector all at once.

Thereby the LEFTMOST value in the returned list ("$words[0]")is the LEAST significant word from the given bit vector, and theRIGHTMOST value in the returned list ("$words[$#words]") isthe MOST significant word of the given bit vector.

This method is similar in function to the expression``@words = @array;'' for a Perl array.

•

$vector->Word_Insert($offset,$count);

This method inserts ``$count'' empty new machine words at position``$offset'' in the internal array of words of the given bit vector.

The ``$count'' most significant words are lost, and all words startingwith word number ``$offset'' up to and including word number``$vector->Word_Size()-$count-1'' are moved up by ``$count'' places.

The now vacant ``$count'' words starting at word number ``$offset''(up to and including word number ``$offset+$count-1") are then setto zero (cleared).

Note that this method does NOT increase the size of the given bitvector, i.e., the bit vector is NOT extended at its upper end to``rescue'' the ``$count'' uppermost (most significant) words - instead,these words are lost forever.

If you don't want this to happen, you have to increase the size of thegiven bit vector EXPLICITLY and BEFORE you perform the ``Insert''operation, with a statement such as the following:

  $vector->Resize($vector->Size() + $count * Bit::Vector->Word_Bits());

Note also that ``$offset'' must lie in the permitted range between``0'' and ``$vector->Word_Size()-1'', or a fatal ``offset outof range'' error will occur.

If the term ``$offset + $count'' exceeds ``$vector->Word_Size()-1'',all the words starting with word number ``$offset'' up to word number``$vector->Word_Size()-1'' are simply cleared.

•

$vector->Word_Delete($offset,$count);

This method deletes, i.e., removes the words starting at position``$offset'' up to and including word number ``$offset+$count-1''from the internal array of machine words of the given bit vector.

The remaining uppermost words (starting at position ``$offset+$count''up to and including word number ``$vector->Word_Size()-1") aremoved down by ``$count'' places.

The now vacant uppermost (most significant) ``$count'' words are thenset to zero (cleared).

Note that this method does NOT decrease the size of the given bitvector, i.e., the bit vector is NOT clipped at its upper end to``get rid of'' the vacant ``$count'' uppermost words.

If you don't want this, i.e., if you want the bit vector to shrinkaccordingly, you have to do so EXPLICITLY and AFTER the ``Delete''operation, with a couple of statements such as these:

  $bits = $vector->Size();  $count *= Bit::Vector->Word_Bits();  if ($count > $bits) { $count = $bits; }  $vector->Resize($bits - $count);

Note also that ``$offset'' must lie in the permitted range between``0'' and ``$vector->Word_Size()-1'', or a fatal ``offset outof range'' error will occur.

If the term ``$offset + $count'' exceeds ``$vector->Word_Size()-1'',all the words starting with word number ``$offset'' up to word number``$vector->Word_Size()-1'' are simply cleared.

•

$vector->Chunk_Store($chunksize,$offset,$chunk);

This method allows you to set more than one bit at a time withdifferent values.

You can access chunks (i.e., ranges of contiguous bits) betweenone and at most ``Bit::Vector->Long_Bits()'' bits wide.

In order to be portable, though, you should never use chunk sizeslarger than 32 bits.

If the given ``$chunksize'' does not lie between ``1'' and``Bit::Vector->Long_Bits()'', a fatal ``chunk size out of range''error will occur.

The method copies the ``$chunksize'' least significant bitsfrom the value ``$chunk'' to the given bit vector, starting atbit position ``$offset'' and proceeding upwards until bit number``$offset+$chunksize-1''.

(I.e., bit number ``0'' of ``$chunk'' becomes bit number ``$offset''in the given bit vector, and bit number ``$chunksize-1'' becomesbit number ``$offset+$chunksize-1''.)

If the term ``$offset+$chunksize-1'' exceeds ``$vector->Size()-1'',the corresponding superfluous (most significant) bits from ``$chunk''are simply ignored.

Note that ``$offset'' itself must lie in the permitted range between``0'' and ``$vector->Size()-1'', or a fatal ``offset out of range''error will occur.

This method (as well as the other ``Chunk_'' methods) is useful, forexample, when you are reading in data in chunks of, say, 8 bits, whichyou need to access later, say, using 16 bits at a time (like audio CDwave files, for instance).

•

$chunk = $vector->Chunk_Read($chunksize,$offset);

This method allows you to read the values of more than one bit ata time.

You can read chunks (i.e., ranges of contiguous bits) betweenone and at most ``Bit::Vector->Long_Bits()'' bits wide.

In order to be portable, though, you should never use chunk sizeslarger than 32 bits.

If the given ``$chunksize'' does not lie between ``1'' and``Bit::Vector->Long_Bits()'', a fatal ``chunk size out of range''error will occur.

The method returns the ``$chunksize'' bits from the given bit vectorstarting at bit position ``$offset'' and proceeding upwards untilbit number ``$offset+$chunksize-1''.

(I.e., bit number ``$offset'' of the given bit vector becomes bit number``0'' of the returned value, and bit number ``$offset+$chunksize-1''becomes bit number ``$chunksize-1''.)

If the term ``$offset+$chunksize-1'' exceeds ``$vector->Size()-1'',the non-existent bits are simply not returned.

Note that ``$offset'' itself must lie in the permitted range between``0'' and ``$vector->Size()-1'', or a fatal ``offset out of range''error will occur.

•

$vector->Chunk_List_Store($chunksize,@chunks);

This method allows you to fill the given bit vector with a list ofdata packets ("chunks") of any size ("$chunksize") you like(within certain limits).

In fact the given ``$chunksize'' must lie in the range between ``1''and ``Bit::Vector->Long_Bits()'', or a fatal ``chunk size out ofrange'' error will occur.

In order to be portable, though, you should never use chunk sizeslarger than 32 bits.

The given bit vector is thereby filled in ascending order: The firstchunk from the list (i.e., ``$chunks[0]") fills the ``$chunksize''least significant bits, the next chunk from the list ("$chunks[1]")fills the bits number ``$chunksize'' to number ``2*$chunksize-1'',the third chunk ("$chunks[2]") fills the bits number ``2*$chunksize'',to number ``3*$chunksize-1'', and so on.

If there a less chunks in the list than are needed to fill the entirebit vector, the remaining (most significant) bits are cleared, i.e.,the previous contents of the given bit vector are always erased completely.

If there are more chunks in the list than are needed to fill the entirebit vector, and/or if a chunk extends beyond ``$vector->Size()-1''(which happens whenever ``$vector->Size()'' is not a multiple of``$chunksize"), the superfluous chunks and/or bits are simply ignored.

The method is useful, for example (and among many other applications),for the conversion of packet sizes in a data stream.

This method can also be used to store an octal string in a givenbit vector:

  $vector->Chunk_List_Store(3, split(//, reverse $string));

Note however that unlike the conversion methods ``from_Hex()'',``from_Bin()'', ``from_Dec()'' and ``from_Enum()'',this statement does not include any syntax checking, i.e.,it may fail silently, without warning.

To perform syntax checking, add the following statements:

  if ($string =~ /^[0-7]+$/)  {      # okay, go ahead with conversion as shown above  }  else  {      # error, string contains other than octal characters  }

Another application is to store a repetitive pattern in a givenbit vector:

  $pattern = 0xDEADBEEF;  $length = 32;            # = length of $pattern in bits  $size = $vector->Size();  $factor = int($size / $length);  if ($size % $length) { $factor++; }  $vector->Chunk_List_Store($length, ($pattern) x $factor);

•

@chunks = $vector->Chunk_List_Read($chunksize);

This method allows you to access the contents of the given bit vector inform of a list of data packets ("chunks") of a size ("$chunksize")of your choosing (within certain limits).

In fact the given ``$chunksize'' must lie in the range between ``1''and ``Bit::Vector->Long_Bits()'', or a fatal ``chunk size out ofrange'' error will occur.

In order to be portable, though, you should never use chunk sizeslarger than 32 bits.

The given bit vector is thereby read in ascending order: The``$chunksize'' least significant bits (bits number ``0'' to``$chunksize-1") become the first chunk in the returned list(i.e., ``$chunks[0]"). The bits number ``$chunksize'' to``2*$chunksize-1'' become the next chunk in the list("$chunks[1]"), and so on.

If ``$vector->Size()'' is not a multiple of ``$chunksize'',the last chunk in the list will contain fewer bits than ``$chunksize''.

BEWARE that for large bit vectors and/or small values of ``$chunksize'',the number of returned list elements can be extremely large! BE CAREFUL!

You could blow up your application with lack of memory (each list elementis a full-grown Perl scalar, internally, with an associated memory overheadfor its administration!) or at least cause a noticeable, more or lesslong-lasting ``freeze'' of your application!

Possible applications:

The method is especially useful in the conversion of packet sizes ina data stream.

This method can also be used to convert a given bit vector to a stringof octal numbers:

  $string = reverse join('', $vector->Chunk_List_Read(3));

•

$vector->Index_List_Remove(@indices);

This method allows you to specify a list of indices of bits whichshould be turned off in the given bit vector.

In fact this method is a shortcut for

    foreach $index (@indices)    {        $vector->Bit_Off($index);    }

In contrast to all other import methods in this module, this methoddoes NOT clear the given bit vector before processing its listof arguments.

Instead, this method allows you to accumulate the results of variousconsecutive calls.

(The same holds for the method ``Index_List_Store()''. As aconsequence, you can ``wipe out'' what you did using the method``Index_List_Remove()'' by passing the identical argument listto the method ``Index_List_Store()''.)

•

$vector->Index_List_Store(@indices);

This method allows you to specify a list of indices of bits whichshould be turned on in the given bit vector.

In fact this method is a shortcut for

    foreach $index (@indices)    {        $vector->Bit_On($index);    }

In contrast to all other import methods in this module, this methoddoes NOT clear the given bit vector before processing its listof arguments.

Instead, this method allows you to accumulate the results of variousconsecutive calls.

(The same holds for the method ``Index_List_Remove()''. As aconsequence, you can ``wipe out'' what you did using the method``Index_List_Store()'' by passing the identical argument listto the method ``Index_List_Remove()''.)

•

@indices = $vector->Index_List_Read();

This method returns a list of Perl scalars.

The list contains one scalar for each set bit in the givenbit vector.

BEWARE that for large bit vectors, this can result in a literallyoverwhelming number of list elements! BE CAREFUL! You could runout of memory or slow down your application considerably!

Each scalar contains the number of the index corresponding tothe bit in question.

These indices are always returned in ascending order.

If the given bit vector is empty (contains only cleared bits)or if it has a length of zero (if it contains no bits at all),the method returns an empty list.

This method can be useful, for instance, to obtain a list ofprime numbers:

    $limit = 1000; # or whatever    $vector = Bit::Vector->new($limit+1);    $vector->Primes();    @primes = $vector->Index_List_Read();

•

$set3->Union($set1,$set2);

This method calculates the union of ``$set1'' and ``$set2'' and storesthe result in ``$set3''.

This is usually written as ``$set3 = $set1 u $set2'' in set theory(where ``u'' is the ``cup'' operator).

(On systems where the ``cup'' character is unavailable this operatoris often denoted by a plus sign ``+''.)

In-place calculation is also possible, i.e., ``$set3'' may be identicalwith ``$set1'' or ``$set2'' or both.

•

$set3->Intersection($set1,$set2);

This method calculates the intersection of ``$set1'' and ``$set2'' andstores the result in ``$set3''.

This is usually written as ``$set3 = $set1 n $set2'' in set theory(where ``n'' is the ``cap'' operator).

(On systems where the ``cap'' character is unavailable this operatoris often denoted by an asterisk ``*''.)

In-place calculation is also possible, i.e., ``$set3'' may be identicalwith ``$set1'' or ``$set2'' or both.

•

$set3->Difference($set1,$set2);

This method calculates the difference of ``$set1'' less ``$set2'' andstores the result in ``$set3''.

This is usually written as ``$set3 = $set1 \ $set2'' in set theory(where ``\'' is the ``less'' operator).

In-place calculation is also possible, i.e., ``$set3'' may be identicalwith ``$set1'' or ``$set2'' or both.

•

$set3->ExclusiveOr($set1,$set2);

This method calculates the symmetric difference of ``$set1'' and ``$set2''and stores the result in ``$set3''.

This can be written as ``$set3 = ($set1 u $set2) \ ($set1 n $set2)'' in settheory (the union of the two sets less their intersection).

When sets are implemented as bit vectors then the above formula isequivalent to the exclusive-or between corresponding bits of the twobit vectors (hence the name of this method).

Note that this method is also much more efficient than evaluating theabove formula explicitly since it uses a built-in machine languageinstruction internally.

In-place calculation is also possible, i.e., ``$set3'' may be identicalwith ``$set1'' or ``$set2'' or both.

•

$set2->Complement($set1);

This method calculates the complement of ``$set1'' and stores the resultin ``$set2''.

In ``big integer'' arithmetic, this is equivalent to calculating the one'scomplement of the number stored in the bit vector ``$set1'' in binaryrepresentation.

In-place calculation is also possible, i.e., ``$set2'' may be identicalwith ``$set1''.

•

if ($set1->subset($set2))

Returns ``true'' ("1") if ``$set1'' is a subset of ``$set2''(i.e., completely contained in ``$set2") and ``false'' ("0")otherwise.

This means that any bit which is set ("1") in ``$set1'' mustalso be set in ``$set2'', but ``$set2'' may contain set bitswhich are not set in ``$set1'', in order for the conditionof subset relationship to be true between these two sets.

Note that by definition, if two sets are identical, they arealso subsets (and also supersets) of each other.

•

$norm = $set->Norm();

Returns the norm (number of bits which are set) of the given vector.

This is equivalent to the number of elements contained in the givenset.

•

$min = $set->Min();

Returns the minimum of the given set, i.e., the minimum of allindices of all set bits in the given bit vector ``$set''.

If the set is empty (no set bits), plus infinity (representedby the constant ``MAX_LONG'' on your system) is returned.

(This constant is usually 2 ^ (n-1) - 1, where ``n'' is thenumber of bits of an unsigned long on your machine.)

•

$max = $set->Max();

Returns the maximum of the given set, i.e., the maximum of allindices of all set bits in the given bit vector ``$set''.

If the set is empty (no set bits), minus infinity (representedby the constant ``MIN_LONG'' on your system) is returned.

(This constant is usually -(2 ^ (n-1) - 1) or -(2 ^ (n-1)),where ``n'' is the number of bits of an unsigned long on your machine.)

•

$m3->Multiplication($r3,$c3,$m1,$r1,$c1,$m2,$r2,$c2);

This method multiplies two boolean matrices (stored as bit vectors)``$m1'' and ``$m2'' and stores the result in matrix ``$m3''.

An exception is raised if the product of the number of rows andcolumns of any of the three matrices differs from the actual sizeof their underlying bit vector.

An exception is also raised if the numbers of rows and columnsof the three matrices do not harmonize in the required manner:

  rows3 == rows1  cols3 == cols2  cols1 == rows2

This method is used by the module ``Math::MatrixBool''.

See the Math::MatrixBool(3) manpage for details.

•

$matrix->Closure($rows,$cols);

This method calculates the reflexive transitive closure of thegiven boolean matrix (stored as a bit vector) using Kleene'salgoritm.

(See the Math::Kleene(3) manpage for a brief introduction into thetheory behind Kleene's algorithm.)

The reflexive transitive closure answers the question wethera path exists between any two vertices of a graph whose edgesare given as a matrix:

If a (directed) edge exists going from vertex ``i'' to vertex ``j'',then the element in the matrix with coordinates (i,j) is set to``1'' (otherwise it remains set to ``0").

If the edges are undirected, the resulting matrix is symmetric,i.e., elements (i,j) and (j,i) always contain the same value.

The matrix representing the edges of the graph only answers thequestion wether an EDGE exists between any two vertices ofthe graph or not, whereas the reflexive transitive closureanswers the question wether a PATH (a series of adjacentedges) exists between any two vertices of the graph!

Note that the contents of the given matrix are modified bythis method, so make a copy of the initial matrix in timeif you are going to need it again later.

An exception is raised if the given matrix is not quadratic,i.e., if the number of rows and columns of the given matrixis not identical.

An exception is also raised if the product of the number ofrows and columns of the given matrix differs from the actualsize of its underlying bit vector.

This method is used by the module ``Math::MatrixBool''.

See the Math::MatrixBool(3) manpage for details.

•

$matrix2->Transpose($rows2,$cols2,$matrix1,$rows1,$cols1);

This method calculates the transpose of a boolean matrix ``$matrix1''(stored as a bit vector) and stores the result in matrix ``$matrix2''.

The transpose of a boolean matrix, representing the edges of a graph,can be used for finding the strongly connected components of that graph.

An exception is raised if the product of the number of rows andcolumns of any of the two matrices differs from the actual sizeof its underlying bit vector.

An exception is also raised if the following conditions are notmet:

  rows2 == cols1  cols2 == rows1

Note that in-place processing ("$matrix1'' and ``$matrix2'' areidentical) is only possible if the matrix is quadratic. Otherwise,a fatal ``matrix is not quadratic'' error will occur.

This method is used by the module ``Math::MatrixBool''.

See the Math::MatrixBool(3) manpage for details.

CLASS METHODS (implemented in Perl)

•

$config = Bit::Vector->Configuration();

•

Bit::Vector->Configuration($config);

•

$oldconfig = Bit::Vector->Configuration($newconfig);

This method serves to alter the semantics (i.e., behaviour) of certainoverloaded operators (which are all implemented in Perl, by the way).

It does not have any effect whatsoever on anything else. In particular,it does not affect the methods implemented in C.

The method accepts an (optional) string as input in which certain keywordsare expected, which influence some or almost all of the overloaded operatorsin several possible ways.

The method always returns a string (which you do not need to take care of, i.e.,to store, in case you aren't interested in keeping it) which is a completerepresentation of the current configuration (i.e., BEFORE any modificationsare applied) and which can be fed back to this method later in order to restorethe previous configuration.

There are three aspects of the way certain overloaded operators behave whichcan be controlled with this method:

  +  the way scalar operands (replacing one of the two     bit vector object operands) are automatically     converted internally into a bit vector object of     their own,

  +  the operation certain overloaded operators perform,     i.e., an operation with sets or an arithmetic     operation,

  +  the format to which bit vectors are converted     automatically when they are enclosed in double     quotes.

The input string may contain any number of assignments, each of whichcontrols one of these three aspects.

Each assignment has the form ``<which>=<value>''.

``<which>'' and ``<value>'' thereby consist of letters([a-zA-Z]) and white space.

Multiple assignments have to be separated by one or more comma ('',"),semi-colon ('';"), colon (":"), vertical bar ("|"), slash ("/"),newline (''\n"), ampersand ("&"), plus ("+") or dash (''-").

Empty lines or statements (only white space) are allowed but will beignored.

``<which>'' has to contain one or more keywords from one ofthree groups, each group representing one of the three aspects thatthe ``Configuration()'' method controls:

  +  "^scalar", "^input", "^in$"

  +  "^operator", "^semantic", "^ops$"

  +  "^string", "^output", "^out$"

The character ``^'' thereby denotes the beginning of a word, and ``$''denotes the end. Case is ignored (!).

Using these keywords, you can build any phrase you like to select oneof the three aspects (see also examples given below).

The only condition is that no other keyword from any of the other twogroups may match - otherwise a syntax error will occur (i.e., ambiguitiesare forbidden). A syntax error also occurs if none of the keywordsmatches.

This same principle applies to ``<value>":

Depending on which aspect you specified for ``<which>'',there are different groups of keywords that determine the valuethe selected aspect will be set to:

  +  "<which>" = "^scalar", "^input", "^in$":

       "<value>" =

       *  "^bit$", "^index", "^indice"       *  "^hex"       *  "^bin"       *  "^dec"       *  "^enum"

  +  "<which>" = "^operator", "^semantic", "^ops$":

       "<value>" =

       *  "^set$"       *  "^arithmetic"

  +  "<which>" = "^string", "^output", "^out$":

       "<value>" =

       *  "^hex"       *  "^bin"       *  "^dec"       *  "^enum"

Examples:

  "Any scalar input I provide should be considered to be = a bit index"

  "I want to have operator semantics suitable for = arithmetics"

  "Any bit vector in double quotes is to be output as = an enumeration"

Scalar input:

In the case of scalar input, ``^bit$'', ``^index'', or ``^indice''all cause scalar input to be considered to represent a bit index, i.e.,``$vector ^= 5;'' will flip bit #5 in the given bit vector (this isessentially the same as ``$vector->bit_flip(5);").

Note that ``bit indices'' is the default setting for ``scalar input''.

The keyword ``^hex'' will cause scalar input to be considered as being inhexadecimal, i.e., ``$vector ^= 5;'' will flip bit #0 and bit #2 (becausehexadecimal ``5'' is binary ``0101").

(Note though that hexadecimal input should always be enclosed in quotes,otherwise it will be interpreted as a decimal number by Perl! The examplerelies on the fact that hexadecimal 0-9 and decimal 0-9 are the same.)

The keyword ``^bin'' will cause scalar input to be considered as being inbinary format. All characters except ``0'' and ``1'' are forbidden inthis case (i.e., produce a syntax error).

``$vector ^= '0101';'', for instance, will flip bit #0 and bit #2.

The keyword ``^dec'' causes scalar input to be considered as integersin decimal format, i.e., ``$vector ^= 5;'' will flip bit #0 and bit #2(because decimal ``5'' is binary ``0101").

(Note though that all decimal input should be enclosed in quotes, becausefor large numbers, Perl will use scientific notation internally forrepresenting them, which produces a syntax error because scientificnotation is neither supported by this module nor needed.)

Finally, the keyword ``^enum'' causes scalar input to be consideredas being a list ("enumeration") of indices and ranges of (contiguous)indices, i.e., ``$vector |= '2,3,5,7-13,17-23';'' will cause bits #2,#3, #5, #7 through #13 and #17 through #23 to be set.

Operator semantics:

Several overloaded operators can have two distinct functions dependingon this setting.

The affected operators are: ``+'', ``-'', ``*'', ``<'', ``<='',``>'' and ``>=''.

With the default setting, ``set operations'', these operators perform:

  +       set union                           ( set1  u   set2 )  -       set difference                      ( set1  \   set2 )  *       set intersection                    ( set1  n   set2 )  <       true subset relationship            ( set1  <   set2 )  <=      subset relationship                 ( set1  <=  set2 )  >       true superset relationship          ( set1  >   set2 )  >=      superset relationship               ( set1  >=  set2 )

With the alternative setting, ``arithmetic operations'', these operatorsperform:

  +       addition                            ( num1  +   num2 )  -       subtraction                         ( num1  -   num2 )  *       multiplication                      ( num1  *   num2 )  <       "less than" comparison              ( num1  <   num2 )  <=      "less than or equal" comparison     ( num1  <=  num2 )  >       "greater than" comparison           ( num1  >   num2 )  >=      "greater than or equal" comparison  ( num1  >=  num2 )

Note that these latter comparison operators ("<'', ``<='',``>'' and ``>=") regard their operands as being SIGNED.

To perform comparisons with UNSIGNED operands, use the operators``lt'', ``le'', ``gt'' and ``ge'' instead (in contrast to theoperators above, these operators are NOT affected by the``operator semantics'' setting).

String output:

There are four methods which convert the contents of a given bit vectorinto a string: ``to_Hex()'', ``to_Bin()'', ``to_Dec()'' and ``to_Enum()''(not counting ``Block_Read()'', since this method does not return ahuman-readable string).

(For conversion to octal, see the description of the method``Chunk_List_Read()''.)

Therefore, there are four possible formats into which a bit vector canbe converted when it is enclosed in double quotes, for example:

  print "\$vector = '$vector'\n";  $string = "$vector";

Hence you can set ``string output'' to four different values: To ``hex''for hexadecimal format (which is the default), to ``bin'' for binaryformat, to ``dec'' for conversion to decimal numbers and to ``enum''for conversion to enumerations (''.newsrc'' style sets).

BEWARE that the conversion to decimal numbers is inherently slow;it can easily take up several seconds for a single large bit vector!

Therefore you should store the decimal strings returned to yourather than converting a given bit vector again.

Examples:

The default setting as returned by the method ``Configuration()''is:

        Scalar Input       = Bit Index        Operator Semantics = Set Operators        String Output      = Hexadecimal

Performing a statement such as:

  Bit::Vector->Configuration("in=bin,ops=arithmetic,out=bin");  print Bit::Vector->Configuration(), "\n";

yields the following output:

        Scalar Input       = Binary        Operator Semantics = Arithmetic Operators        String Output      = Binary

Note that you can always feed this output back into the ``Configuration()''method to restore that setting later.

This also means that you can enter the same given setting with almost anydegree of verbosity you like (as long as the required keywords appear andno ambiguities arise).

Note further that any aspect you do not specify is not changed, i.e.,the statement

  Bit::Vector->Configuration("operators = arithmetic");

leaves all other aspects unchanged.

OVERLOADED OPERATORS (implemented in Perl)

•

"$vector"

Remember that variables enclosed in double quotes are alwaysinterpolated in Perl.

Whenever a Perl variable containing the reference of a ``Bit::Vector''object is enclosed in double quotes (either alone or together withother text and/or variables), the contents of the correspondingbit vector are converted into a printable string.

Since there are several conversion methods available in this module(see the description of the methods ``to_Hex()'', ``to_Bin()'',``to_Dec()'' and ``to_Enum()"), it is of course desirable tobe able to choose which of these methods should be applied in thiscase.

This can actually be done by changing the configuration of thismodule using the method ``Configure()'' (see the previous chapter,immediately above).

The default is conversion to hexadecimal.

•

if ($vector)

It is possible to use a Perl variable containing the reference of a``Bit::Vector'' object as a boolean expression.

The condition above is true if the corresponding bit vector containsat least one set bit, and it is false if ALL bits of the correspondingbit vector are cleared.

•

if (!$vector)

Since it is possible to use a Perl variable containing the reference of a``Bit::Vector'' object as a boolean expression, you can of course also negatethis boolean expression.

The condition above is true if ALL bits of the corresponding bit vectorare cleared, and it is false if the corresponding bit vector contains atleast one set bit.

Note that this is NOT the same as using the method ``is_full()'',which returns true if ALL bits of the corresponding bit vector areSET.

•

~$vector

This term returns a new bit vector object which is the one's complementof the given bit vector.

This is equivalent to inverting all bits.

•

-$vector (unary minus)

This term returns a new bit vector object which is the two's complementof the given bit vector.

This is equivalent to inverting all bits and incrementing the result by one.

(This is the same as changing the sign of a number in two's complementbinary representation.)

•

abs($vector)

Depending on the configuration (see the description of the method``Configuration()'' for more details), this term either returnsthe number of set bits in the given bit vector (this is the sameas calculating the number of elements which are contained in thegiven set) - which is the default behaviour, or it returns a newbit vector object which contains the absolute value of the numberstored in the given bit vector.

•

$vector1 . $vector2

This term usually returns a new bit vector object which is theresult of the concatenation of the two bit vector operands.

The left operand becomes the most significant, and the right operandbecomes the least significant part of the new bit vector object.

If one of the two operands is not a bit vector object but a Perl scalar,however, the contents of the remaining bit vector operand are convertedinto a string (the format of which depends on the configuration set withthe ``Configuration()'' method), which is then concatenated in the properorder (i.e., as indicated by the order of the two operands) with the Perlscalar.

In other words, a string is returned in such a case instead of abit vector object!

•

$vector x $factor

This term returns a new bit vector object which is the concatenationof as many copies of the given bit vector operand (the left operand)as the factor (the right operand) specifies.

If the factor is zero, a bit vector object with a length of zero bitsis returned.

If the factor is one, just a new copy of the given bit vector isreturned.

Note that a fatal ``reversed operands error'' occurs if the two operandsare swapped.

•

$vector << $bits

This term returns a new bit vector object which is a copy of the givenbit vector (the left operand), which is then shifted left (towards themost significant bit) by as many places as the right operand, ``$bits'',specifies.

This means that the ``$bits'' most significant bits are lost, all otherbits move up by ``$bits'' positions, and the ``$bits'' least significantbits that have been left unoccupied by this shift are all set to zero.

If ``$bits'' is greater than the number of bits of the given bit vector,this term returns an empty bit vector (i.e., with all bits cleared) ofthe same size as the given bit vector.

Note that a fatal ``reversed operands error'' occurs if the two operandsare swapped.

•

$vector >> $bits

This term returns a new bit vector object which is a copy of the givenbit vector (the left operand), which is then shifted right (towards theleast significant bit) by as many places as the right operand, ``$bits'',specifies.

This means that the ``$bits'' least significant bits are lost, all otherbits move down by ``$bits'' positions, and the ``$bits'' most significantbits that have been left unoccupied by this shift are all set to zero.

If ``$bits'' is greater than the number of bits of the given bit vector,this term returns an empty bit vector (i.e., with all bits cleared) ofthe same size as the given bit vector.

Note that a fatal ``reversed operands error'' occurs if the two operandsare swapped.

•

$vector1 | $vector2

This term returns a new bit vector object which is the result ofa bitwise OR operation between the two bit vector operands.

This is the same as calculating the union of two sets.

•

$vector1 & $vector2

This term returns a new bit vector object which is the result ofa bitwise AND operation between the two bit vector operands.

This is the same as calculating the intersection of two sets.

•

$vector1 ^ $vector2

This term returns a new bit vector object which is the result ofa bitwise XOR (exclusive-or) operation between the two bit vectoroperands.

This is the same as calculating the symmetric difference of two sets.

•

$vector1 + $vector2

Depending on the configuration (see the description of the method``Configuration()'' for more details), this term either returnsa new bit vector object which is the result of a bitwise OR operationbetween the two bit vector operands (this is the same as calculatingthe union of two sets) - which is the default behaviour, or it returnsa new bit vector object which contains the sum of the two numbersstored in the two bit vector operands.

•

$vector1 - $vector2

Depending on the configuration (see the description of the method``Configuration()'' for more details), this term either returnsa new bit vector object which is the set difference of the two setsrepresented in the two bit vector operands - which is the defaultbehaviour, or it returns a new bit vector object which containsthe difference of the two numbers stored in the two bit vectoroperands.

•

$vector1 * $vector2

Depending on the configuration (see the description of the method``Configuration()'' for more details), this term either returnsa new bit vector object which is the result of a bitwise AND operationbetween the two bit vector operands (this is the same as calculatingthe intersection of two sets) - which is the default behaviour, or itreturns a new bit vector object which contains the product of the twonumbers stored in the two bit vector operands.

•

$vector1 / $vector2

This term returns a new bit vector object containing the result of thedivision of the two numbers stored in the two bit vector operands.

•

$vector1 % $vector2

This term returns a new bit vector object containing the remainder ofthe division of the two numbers stored in the two bit vector operands.

•

$vector1 .= $vector2;

This statement ``appends'' the right bit vector operand (the ``rvalue")to the left one (the ``lvalue").

The former contents of the left operand become the most significantpart of the resulting bit vector, and the right operand becomes theleast significant part.

Since bit vectors are stored in ``least order bit first'' order, thisactually requires the left operand to be shifted ``up'' by the lengthof the right operand, which is then copied to the now freed leastsignificant part of the left operand.

If the right operand is a Perl scalar, it is first converted to abit vector of the same size as the left operand, provided that theconfiguration states that scalars are to be regarded as indices,decimal strings or enumerations.

•

$vector x= $factor;

This statement replaces the given bit vector by a concatenation of as manycopies of the original contents of the given bit vector as the factor (theright operand) specifies.

If the factor is zero, the given bit vector is resized to a length of zerobits.

If the factor is one, the given bit vector is not changed at all.

•

$vector <<= $bits;

This statement moves the contents of the given bit vector left by ``$bits''positions (towards the most significant bit).

If ``$bits'' is greater than the number of bits of the given bit vector,the given bit vector is erased completely (i.e., all bits are cleared).

•

$vector >>= $bits;

This statement moves the contents of the given bit vector right by ``$bits''positions (towards the least significant bit).

If ``$bits'' is greater than the number of bits of the given bit vector,the given bit vector is erased completely (i.e., all bits are cleared).

•

$vector1 |= $vector2;

This statement performs a bitwise OR operation between the twobit vector operands and stores the result in the left operand.

This is the same as calculating the union of two sets.

•

$vector1 &= $vector2;

This statement performs a bitwise AND operation between the twobit vector operands and stores the result in the left operand.

This is the same as calculating the intersection of two sets.

•

$vector1 ^= $vector2;

This statement performs a bitwise XOR (exclusive-or) operationbetween the two bit vector operands and stores the result in theleft operand.

This is the same as calculating the symmetric difference of two sets.

•

$vector1 += $vector2;

Depending on the configuration (see the description of the method``Configuration()'' for more details), this statement either performsa bitwise OR operation between the two bit vector operands (this isthe same as calculating the union of two sets) - which is the defaultbehaviour, or it calculates the sum of the two numbers stored in thetwo bit vector operands.

The result of this operation is stored in the left operand.

•

$vector1 -= $vector2;

Depending on the configuration (see the description of the method``Configuration()'' for more details), this statement either calculatesthe set difference of the two sets represented in the two bit vectoroperands - which is the default behaviour, or it calculates thedifference of the two numbers stored in the two bit vector operands.

The result of this operation is stored in the left operand.

•

$vector1 *= $vector2;

Depending on the configuration (see the description of the method``Configuration()'' for more details), this statement either performsa bitwise AND operation between the two bit vector operands (this isthe same as calculating the intersection of two sets) - which is thedefault behaviour, or it calculates the product of the two numbersstored in the two bit vector operands.

The result of this operation is stored in the left operand.

•

$vector1 /= $vector2;

This statement puts the result of the division of the two numbersstored in the two bit vector operands into the left operand.

•

$vector1 %= $vector2;

This statement puts the remainder of the division of the two numbersstored in the two bit vector operands into the left operand.

•

++$vector, $vector++

This operator performs pre- and post-incrementation of thegiven bit vector.

The value returned by this term is a reference of the givenbit vector object (after or before the incrementation,respectively).

•

--$vector, $vector--

This operator performs pre- and post-decrementation of thegiven bit vector.

The value returned by this term is a reference of the givenbit vector object (after or before the decrementation,respectively).

•

($vector1 cmp $vector2)

This term returns ``-1'' if ``$vector1'' is less than ``$vector2'',``0'' if ``$vector1'' and ``$vector2'' are the same, and ``1''if ``$vector1'' is greater than ``$vector2''.

This comparison assumes UNSIGNED bit vectors.

•

($vector1 eq $vector2)

This term returns true ("1") if the contents of the two bit vectoroperands are the same and false ("0") otherwise.

•

($vector1 ne $vector2)

This term returns true ("1") if the two bit vector operands differand false ("0") otherwise.

•

($vector1 lt $vector2)

This term returns true ("1") if ``$vector1'' is less than ``$vector2'',and false ("0") otherwise.

This comparison assumes UNSIGNED bit vectors.

•

($vector1 le $vector2)

This term returns true ("1") if ``$vector1'' is less than or equal to``$vector2'', and false ("0") otherwise.

This comparison assumes UNSIGNED bit vectors.

•

($vector1 gt $vector2)

This term returns true ("1") if ``$vector1'' is greater than ``$vector2'',and false ("0") otherwise.

This comparison assumes UNSIGNED bit vectors.

•

($vector1 ge $vector2)

This term returns true ("1") if ``$vector1'' is greater than or equal to``$vector2'', and false ("0") otherwise.

This comparison assumes UNSIGNED bit vectors.

•

($vector1 <=> $vector2)

This term returns ``-1'' if ``$vector1'' is less than ``$vector2'',``0'' if ``$vector1'' and ``$vector2'' are the same, and ``1''if ``$vector1'' is greater than ``$vector2''.

This comparison assumes SIGNED bit vectors.

•

($vector1 == $vector2)

This term returns true ("1") if the contents of the two bit vectoroperands are the same and false ("0") otherwise.

•

($vector1 != $vector2)

This term returns true ("1") if the two bit vector operands differand false ("0") otherwise.

•

($vector1 < $vector2)

Depending on the configuration (see the description of the method``Configuration()'' for more details), this term either returnstrue ("1") if ``$vector1'' is a true subset of ``$vector2''(and false ("0") otherwise) - which is the default behaviour,or it returns true ("1") if ``$vector1'' is less than``$vector2'' (and false ("0") otherwise).

The latter comparison assumes SIGNED bit vectors.

•

($vector1 <= $vector2)

Depending on the configuration (see the description of the method``Configuration()'' for more details), this term either returnstrue ("1") if ``$vector1'' is a subset of ``$vector2'' (andfalse ("0") otherwise) - which is the default behaviour, or itreturns true ("1") if ``$vector1'' is less than or equal to``$vector2'' (and false ("0") otherwise).

The latter comparison assumes SIGNED bit vectors.

•

($vector1 > $vector2)

Depending on the configuration (see the description of the method``Configuration()'' for more details), this term either returnstrue ("1") if ``$vector1'' is a true superset of ``$vector2''(and false ("0") otherwise) - which is the default behaviour,or it returns true ("1") if ``$vector1'' is greater than``$vector2'' (and false ("0") otherwise).

The latter comparison assumes SIGNED bit vectors.

•

($vector1 >= $vector2)

Depending on the configuration (see the description of the method``Configuration()'' for more details), this term either returnstrue ("1") if ``$vector1'' is a superset of ``$vector2'' (andfalse ("0") otherwise) - which is the default behaviour, or itreturns true ("1") if ``$vector1'' is greater than or equal to``$vector2'' (and false ("0") otherwise).

The latter comparison assumes SIGNED bit vectors.

VERSION

This man page documents ``Bit::Vector'' version 5.5.

AUTHOR

  Steffen Beyer  Ainmillerstr. 5 / App. 513  D-80801 Munich  Germany

  mailto:sbAATTengelschall.com  http://www.engelschall.com/u/sb/download/

Please contact me by e-mail whenever possible!

COPYRIGHT

LICENSE

This package is free software; you can redistribute it and/ormodify it under the same terms as Perl itself, i.e., under theterms of the ``Artistic License'' or the ``GNU General Public License''.

The C library at the core of this Perl module can additionallybe redistributed and/or modified under the terms of the ``GNULibrary General Public License''.

Please refer to the files ``Artistic.txt'', ``GNU_GPL.txt'' and``GNU_LGPL.txt'' in this distribution for details!

DISCLAIMER

This package is distributed in the hope that it will be useful,but WITHOUT ANY WARRANTY; without even the implied warranty ofMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

See the ``GNU General Public License'' for more details.

This document was created byman2html,using the manual pages.

Vector

NAME

PREFACE

SYNOPSIS

IMPORTANT NOTES

DESCRIPTION

SEE ALSO

VERSION

AUTHOR

COPYRIGHT

LICENSE

DISCLAIMER

Index