view release on metacpan or  search on metacpan

Vector.pod  view on Meta::CPAN

bit vectors themselves, which are usually considered to be B<SIGNED>).

As a consequence, whenever you pass a negative number as an argument to
some method of this module, it will be treated as a (usually very large)
positive number due to its internal two's complement binary representation,
usually resulting in an "index out of range" error message and program
abortion.

=item *

Bit order

Note that bit vectors are stored least order bit and least order word first
internally.

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

(Where word #0 comes first in memory, i.e., it is stored at the least memory
address 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 the
methods "C<Block_Read()>" and "C<Block_Store()>" (the only time in this
module where this could make any difference), however, a conversion to and
from "least order byte first" order is automatically supplied.

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

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

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

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

Of course this requires an internal reversion of order, which the corresponding
conversion methods perform automatically (without any additional overhead, it's
just a matter of starting the internal loop at the bottom or the top end).

=item *

"Word" related methods

Note that all methods whose names begin with "C<Word_>" are
B<MACHINE-DEPENDENT>!

They depend on the size (number of bits) of an "unsigned int" (C type) on
your machine.

Therefore, you should only use these methods if you are B<ABSOLUTELY CERTAIN>
that 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 B<IN A PORTABLE WAY> using the methods whose names begin with
"C<Chunk_>".

=item *

Chunk sizes

Note that legal chunk sizes for all methods whose names begin with "C<Chunk_>"
range from "C<1>" to "C<Bit::Vector-E<gt>Long_Bits();>" bits ("C<0>" is B<NOT>
allowed!).

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

=item *

Matching sizes

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

Exceptions from this rule are the methods "C<Concat()>", "C<Concat_List()>",
"C<Copy()>", "C<Interval_Copy()>" and "C<Interval_Substitute()>", where no
conditions at all are imposed on the size of their bit vector arguments.

In method "C<Multiply()>", all three bit vector arguments must in principle
obey the rule of matching sizes, but the bit vector in which the result of
the multiplication is to be stored may be larger than the two bit vector
arguments containing the factors for the multiplication.

In method "C<Power()>", the bit vector for the result must be the same
size or greater than the base of the exponentiation term. The exponent
can be any size.

=item *

Index ranges

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

=item *

Object persistence

Since version 6.5, "Bit::Vector" objects can be serialized
and de-serialized automatically with "Storable", out-of-the-box,
without requiring any further user action for this to work.

This is also true for nested data structures (since version 6.8).

See the L<Storable(3)> documentation for more details.

=back

=head1 DESCRIPTION

Vector.pod  view on Meta::CPAN

=item *

C<$overflow = $vec2-E<gt>inc($vec1);>

This method copies the contents of bit vector "C<$vec1>" to bit
vector "C<$vec2>" and increments the copy (not the original).

If by incrementing the number its sign becomes invalid, the return
value ("overflow" flag) will be true ("C<1>"), or false ("C<0>")
if not. (See the description of the method "add()" below for
a more in-depth explanation of what "overflow" means).

Note that in-place operation is also possible, i.e., "C<$vec1>"
and "C<$vec2>" may be identical.

=item *

C<$overflow = $vec2-E<gt>dec($vec1);>

This method copies the contents of bit vector "C<$vec1>" to bit
vector "C<$vec2>" and decrements the copy (not the original).

If by decrementing the number its sign becomes invalid, the return
value ("overflow" flag) will be true ("C<1>"), or false ("C<0>")
if not. (See the description of the method "subtract()" below
for a more in-depth explanation of what "overflow" means).

Note that in-place operation is also possible, i.e., "C<$vec1>"
and "C<$vec2>" may be identical.

=item *

C<$carry = $vec3-E<gt>add($vec1,$vec2,$carry);>

C<($carry,$overflow) = $vec3-E<gt>add($vec1,$vec2,$carry);>

This method adds the two numbers contained in bit vector "C<$vec1>"
and "C<$vec2>" with carry "C<$carry>" and stores the result in
bit vector "C<$vec3>".

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

Note that the "C<$carry>" parameter is a boolean value, i.e.,
only its least significant bit is taken into account. (Think of
it as though "C<$carry &= 1;>" was always executed internally.)

In scalar context, the method returns a boolean value which
indicates if a carry over (to the next higher bit position)
has occured. In list context, the method returns the carry
and the overflow flag (in this order).

The overflow flag is true ("C<1>") if the sign (i.e., the most
significant bit) of the result is wrong. This can happen when
adding two very large positive numbers or when adding two (by
their absolute value) very large negative numbers. See also
further below.

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 whether the numbers
in "C<$vec1>" and "C<$vec2>" are unsigned or signed (i.e., in two's
complement binary representation).

Note however that the return value (carry flag) is not meaningful
when the numbers are B<SIGNED>.

Moreover, when the numbers are signed, a special type of error can
occur which is commonly called an "overflow error".

An overflow error occurs when the sign of the result (its most
significant bit) is flipped (i.e., falsified) by a carry over
from the next-lower bit position ("MSB-1").

In fact matters are a bit more complicated than that: the overflow
flag is set to "true" whenever there is a carry over from bit
position MSB-1 to the most significant bit (MSB) but no carry
over from the MSB to the output carry flag, or vice-versa, i.e.,
when there is no carry over from bit position MSB-1 to the most
significant bit (MSB) but a carry over to the output carry flag.

Thus the overflow flag is the result of an exclusive-or operation
between incoming and outgoing carry over at the most significant
bit position.

=item *

C<$carry = $vec3-E<gt>subtract($vec1,$vec2,$carry);>

C<($carry,$overflow) = $vec3-E<gt>subtract($vec1,$vec2,$carry);>

This method subtracts the two numbers contained in bit vector
"C<$vec1>" and "C<$vec2>" with carry "C<$carry>" and stores the
result in bit vector "C<$vec3>".

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

Note that the "C<$carry>" parameter is a boolean value, i.e.,
only its least significant bit is taken into account. (Think of
it as though "C<$carry &= 1;>" was always executed internally.)

In scalar context, the method returns a boolean value which
indicates if a carry over (to the next higher bit position)
has occured. In list context, the method returns the carry
and the overflow flag (in this order).

The overflow flag is true ("C<1>") if the sign (i.e., the most
significant bit) of the result is wrong. This can happen when
subtracting a very large negative number from a very large
positive number or vice-versa. See also further below.

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 whether the numbers
in "C<$vec1>" and "C<$vec2>" are unsigned or signed (i.e., in two's
complement binary representation).

Note however that the return value (carry flag) is not meaningful
when the numbers are B<SIGNED>.

Moreover, when the numbers are signed, a special type of error can
occur which is commonly called an "overflow error".

An overflow error occurs when the sign of the result (its most
significant bit) is flipped (i.e., falsified) by a carry over
from the next-lower bit position ("MSB-1").

In fact matters are a bit more complicated than that: the overflow
flag is set to "true" whenever there is a carry over from bit
position MSB-1 to the most significant bit (MSB) but no carry
over from the MSB to the output carry flag, or vice-versa, i.e.,
when there is no carry over from bit position MSB-1 to the most
significant bit (MSB) but a carry over to the output carry flag.

Thus the overflow flag is the result of an exclusive-or operation
between incoming and outgoing carry over at the most significant
bit position.

=item *

C<$vec2-E<gt>Neg($vec1);>

C<$vec2-E<gt>Negate($vec1);>

This method calculates the two's complement of the number in bit
vector "C<$vec1>" and stores the result in bit vector "C<$vec2>".