### Bit::Vector (3)

#### Leading comments

Automatically generated by Pod::Man 4.09 (Pod::Simple 3.35) Standard preamble: ========================================================================

#### NAME

Bit::Vector - Efficient bit vector, set of integers and "big int" math library

#### SYNOPSIS

#### OVERLOADED OPERATORS

See Bit::Vector::Overload(3).

#### MORE STRING IMPORT/EXPORT

See Bit::Vector::String(3).

#### CLASS METHODS

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

@veclist = Bit::Vector->new($bits,$count);

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

new

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

@veclist = $vec->new($bits,$count);

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();

inc

$overflow = $vec2->inc($vec1);

dec

$overflow = $vec2->dec($vec1);

add

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

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

subtract

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

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

Neg

Negate

$vec2->Neg($vec1);

$vec2->Negate($vec1);

Abs

Absolute

$vec2->Abs($vec1);

$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)

$vecgcd->GCD($veca,$vecb);

$vecgcd->GCD($vecx,$vecy,$veca,$vecb);

Power

$vec3->Power($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();

Or

Union

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

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

And

Intersection

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

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

AndNot

Difference

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

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

Xor

ExclusiveOr

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

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

Not

Complement

$vec2->Not($vec1);

$set2->Complement($set1);

subset

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

Norm

$norm = $set->Norm();

$norm = $set->Norm2();

$norm = $set->Norm3();

Min

$min = $set->Min();

Max

$max = $set->Max();

Multiplication

$matrix3->Multiplication($rows3,$cols3,

$matrix1,$rows1,$cols1,

$matrix2,$rows2,$cols2);

Product

$matrix3->Product($rows3,$cols3,

$matrix1,$rows1,$cols1,

$matrix2,$rows2,$cols2);

Closure

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

Transpose

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

#### IMPORTANT NOTES

o Method naming conventions

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

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

o Boolean values

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

o Negative numbers

All numeric input parameters passed to any of the methods in this module are regarded as being UNSIGNED (as opposed to the contents of the bit vectors themselves, which are usually considered to be 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.

o 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 ""Block_Read()"" and ""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 ""Block_Read()"" provides and what ""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 ""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 or hexadecimal) 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 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).

o "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) on your machine.

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

o 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 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 ANSIC.

o 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 ""Concat()"", ""Concat_List()"", ""Copy()"", ""Interval_Copy()"" and ""Interval_Substitute()"", where no conditions at all are imposed on the size of their bit vector arguments.

In method ""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 ""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.

o 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.

o 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 (si.

#### Vector(3pm) User Contributed Perl Documentation Vector(3pm)

#### NAME

Bit::Vector - Efficient bit vector, set of integers and "big int" math library

#### SYNOPSIS

#### OVERLOADED OPERATORS

See Bit::Vector::Overload(3).

#### MORE STRING IMPORT/EXPORT

See Bit::Vector::String(3).

#### CLASS METHODS

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

@veclist = Bit::Vector->new($bits,$count);

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

new

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

@veclist = $vec->new($bits,$count);

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();

inc

$overflow = $vec2->inc($vec1);

dec

$overflow = $vec2->dec($vec1);

add

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

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

subtract

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

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

Neg

Negate

$vec2->Neg($vec1);

$vec2->Negate($vec1);

Abs

Absolute

$vec2->Abs($vec1);

$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)

$vecgcd->GCD($veca,$vecb);

$vecgcd->GCD($vecx,$vecy,$veca,$vecb);

Power

$vec3->Power($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();

Or

Union

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

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

And

Intersection

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

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

AndNot

Difference

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

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

Xor

ExclusiveOr

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

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

Not

Complement

$vec2->Not($vec1);

$set2->Complement($set1);

subset

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

Norm

$norm = $set->Norm();

$norm = $set->Norm2();

$norm = $set->Norm3();

Min

$min = $set->Min();

Max

$max = $set->Max();

Multiplication

$matrix3->Multiplication($rows3,$cols3,

$matrix1,$rows1,$cols1,

$matrix2,$rows2,$cols2);

Product

$matrix3->Product($rows3,$cols3,

$matrix1,$rows1,$cols1,

$matrix2,$rows2,$cols2);

Closure

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

Transpose

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

#### IMPORTANT NOTES

o Method naming conventions

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

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

o Boolean values

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

o Negative numbers

All numeric input parameters passed to any of the methods in this module are regarded as being UNSIGNED (as opposed to the contents of the bit vectors themselves, which are usually considered to be 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.

o 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 ""Block_Read()"" and ""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 ""Block_Read()"" provides and what ""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 ""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 or hexadecimal) 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 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).

o "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) on your machine.

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

o 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 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 ANSIC.

o 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 ""Concat()"", ""Concat_List()"", ""Copy()"", ""Interval_Copy()"" and ""Interval_Substitute()"", where no conditions at all are imposed on the size of their bit vector arguments.

In method ""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 ""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.

o 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.

o 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 (si.

#### Vector(3pm) User Contributed Perl Documentation Vector(3pm)

#### NAME

Bit::Vector - Efficient bit vector, set of integers and "big int" math library

#### SYNOPSIS

#### OVERLOADED OPERATORS

See Bit::Vector::Overload(3).

#### MORE STRING IMPORT/EXPORT

See Bit::Vector::String(3).

#### CLASS METHODS

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

@veclist = Bit::Vector->new($bits,$count);

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

new

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

@veclist = $vec->new($bits,$count);

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();

inc

$overflow = $vec2->inc($vec1);

dec

$overflow = $vec2->dec($vec1);

add

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

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

subtract

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

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

Neg

Negate

$vec2->Neg($vec1);

$vec2->Negate($vec1);

Abs

Absolute

$vec2->Abs($vec1);

$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)

$vecgcd->GCD($veca,$vecb);

$vecgcd->GCD($vecx,$vecy,$veca,$vecb);

Power

$vec3->Power($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();

Or

Union

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

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

And

Intersection

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

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

AndNot

Difference

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

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

Xor

ExclusiveOr

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

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

Not

Complement

$vec2->Not($vec1);

$set2->Complement($set1);

subset

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

Norm

$norm = $set->Norm();

$norm = $set->Norm2();

$norm = $set->Norm3();

Min

$min = $set->Min();

Max

$max = $set->Max();

Multiplication

$matrix3->Multiplication($rows3,$cols3,

$matrix1,$rows1,$cols1,

$matrix2,$rows2,$cols2);

Product

$matrix3->Product($rows3,$cols3,

$matrix1,$rows1,$cols1,

$matrix2,$rows2,$cols2);

Closure

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

Transpose

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

#### IMPORTANT NOTES

o Method naming conventions

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

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

o Boolean values

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

o Negative numbers

All numeric input parameters passed to any of the methods in this module are regarded as being UNSIGNED (as opposed to the contents of the bit vectors themselves, which are usually considered to be 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.

o 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 ""Block_Read()"" and ""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 ""Block_Read()"" provides and what ""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 ""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 or hexadecimal) 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 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).

o "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) on your machine.

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

o 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 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 ANSIC.

o 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 ""Concat()"", ""Concat_List()"", ""Copy()"", ""Interval_Copy()"" and ""Interval_Substitute()"", where no conditions at all are imposed on the size of their bit vector arguments.

In method ""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 ""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.

o 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.

o 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 (si.

#### Vector(3pm) User Contributed Perl Documentation Vector(3pm)

#### NAME

Bit::Vector - Efficient bit vector, set of integers and "big int" math library

#### SYNOPSIS

#### OVERLOADED OPERATORS

See Bit::Vector::Overload(3).

#### MORE STRING IMPORT/EXPORT

See Bit::Vector::String(3).

#### CLASS METHODS

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

@veclist = Bit::Vector->new($bits,$count);

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

new

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

@veclist = $vec->new($bits,$count);

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();

inc

$overflow = $vec2->inc($vec1);

dec

$overflow = $vec2->dec($vec1);

add

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

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

subtract

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

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

Neg

Negate

$vec2->Neg($vec1);

$vec2->Negate($vec1);

Abs

Absolute

$vec2->Abs($vec1);

$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)

$vecgcd->GCD($veca,$vecb);

$vecgcd->GCD($vecx,$vecy,$veca,$vecb);

Power

$vec3->Power($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();

Or

Union

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

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

And

Intersection

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

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

AndNot

Difference

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

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

Xor

ExclusiveOr

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

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

Not

Complement

$vec2->Not($vec1);

$set2->Complement($set1);

subset

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

Norm

$norm = $set->Norm();

$norm = $set->Norm2();

$norm = $set->Norm3();

Min

$min = $set->Min();

Max

$max = $set->Max();

Multiplication

$matrix3->Multiplication($rows3,$cols3,

$matrix1,$rows1,$cols1,

$matrix2,$rows2,$cols2);

Product

$matrix3->Product($rows3,$cols3,

$matrix1,$rows1,$cols1,

$matrix2,$rows2,$cols2);

Closure

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

Transpose

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

#### IMPORTANT NOTES

o Method naming conventions

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

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

o Boolean values

o Negative numbers

o Bit order

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

o "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) on your machine.

o Chunk sizes

o Matching sizes

o Index ranges

o Object persistence

This is also true for nested data structures (si.

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

except that it is much more efficient (for "$bits" greater than or equal to the number of bits in a machine word on your system) than this straightforward approach.

o "$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 bits down by "$bits" places, thereby creating "$bits" new bits at the upper end (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 or equal to the number of bits in a machine word on your system) than this straightforward approach.

o "$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 starting with 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 set to zero (cleared).

Note that this method does NOT increase the size of the given bit vector, 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 the given 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.

o "$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 moved down by "$bits" places.

The now vacant uppermost (most significant) "$bits" bits are then set to zero (cleared).

Note that this method does NOT decrease the size of the given bit vector, 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 shrink accordingly, 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.

o "$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 directly followed 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 a carry 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 the bit vector can assume.

o "$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, speaking in absolute terms) negative number is directly followed by the 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 a carry 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 the bit vector can assume.

o "$overflow = $vec2->inc($vec1);"

This method copies the contents of bit vector "$vec1" to bit vector "$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 ("1"), or false ("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., "$vec1" and "$vec2" may be identical.

o "$overflow = $vec2->dec($vec1);"

This method copies the contents of bit vector "$vec1" to bit vector "$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 ("1"), or false ("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., "$vec1" and "$vec2" may be identical.

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

"($carry,$overflow) = $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 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 of it as though ""$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 ("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 "$vec1" and "$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 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.

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

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

This method subtracts the two numbers contained in bit vector "$vec1" and "$vec2" with carry "$carry" and stores the result 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 of it as though ""$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 ("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 "$vec1" and "$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 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.

o "$vec2->Neg($vec1);"

"$vec2->Negate($vec1);"

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

Calculating the two's complement of a given number in binary representation consists 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 given number 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-intuitive result 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 bit vector contains: The negated value of this number is the number itself!

o "$vec2->Abs($vec1);"

"$vec2->Absolute($vec1);"

Depending on the sign (i.e., the most significant bit) of the number in bit vector "$vec1", the contents of bit vector "$vec1" are copied to bit vector "$vec2" either with the method ""Copy()"" (if the number in bit vector "$vec1" is positive), or with ""Negate()"" (if the number in bit vector "$vec1" is negative).

In other words, this method calculates the absolute value of the number in 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.

Most importantly, beware that this method produces a counter-intuitive result 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 bit vector contains: The absolute value of this number is the number itself, even though this number is still negative by definition (the most significant bit is still set)!

o "$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 given bit vector has a length of zero (contains no bits at all).

If not all bits are cleared, this method returns ""-1"" if the most significant bit is set (i.e., if the bit vector contains a negative number), or "1" otherwise (i.e., if the bit vector contains a positive number).

o "$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 being negative by mistake, make your bit vectors at least one bit longer than the largest number you wish to represent, right from the start, or proceed as follows:

$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 the rule of matching sizes, but that the bit vector "$vec3" may be larger than the two factors "$vec1" and "$vec2".

In fact multiplying two binary numbers with ""n"" bits may yield a result which is at most ""2n"" bits long.

Therefore, it is usually a good idea to let bit vector "$vec3" have twice the size of bit vector "$vec1" and "$vec2", unless you are absolutely sure that the result will fit into a bit vector of the same size 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.

o "$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" and the 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 "result vector(s) 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.

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

$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 long as "$quot" and "$rest" are distinct. (!)

o "$vecgcd->GCD($veca,$vecb);"

This method calculates the "Greatest Common Divisor" of the two numbers contained in bit vector "$veca" and "$vecb" and stores the result in bit vector "$vecgcd".

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 "GCD(z,0) == GCD(0,z) == z".

o "$vecgcd->GCD($vecx,$vecy,$veca,$vecb);"

This variant of the "GCD" method calculates the "Greatest Common Divisor" of the two numbers contained in bit vector "$veca" and "$vecb" and stores the result in bit vector "$vecgcd".

Moreover, it determines the two factors which are necessary in order to represent the greatest common divisor as a linear combination of its two arguments, i.e., the two factors "x" and "y" so that "GCD(a,b) == x * a + y * b", and stores them in bit vector "$vecx" and "$vecy", respectively.

For example:

a = 2322

b = 654

GCD( 2322, 654 ) == 6

x = 20

y = -71

20 * 2322 - 71 * 654 == 6

Please see http://www.cut-the-knot.org/blue/extension.shtml for an explanation of how this extension of Euklid's algorithm works.

o "$vec3->Power($vec1,$vec2);"

This method calculates the exponentiation of base "$vec1" elevated to the "$vec2" power, i.e., ""$vec1 ** $vec2"", and stores the result in bit vector "$vec3".

The method uses an efficient divide-and-conquer algorithm:

Suppose the exponent is (decimal) 13, for example. The binary representation of this exponent is "1101".

This means we want to calculate

$vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 *

$vec1 * $vec1 * $vec1 * $vec1 *

$vec1

That is, "$vec1" multiplied with itself 13 times. The grouping into lines above is no coincidence. The first line comprises 8 factors, the second contains 4, and the last line just one. This just happens to be the binary representation of 13. ";-)"

We then calculate a series of squares (of squares of squares...) of the base, i.e.,

$power[0] = $vec1;

$power[1] = $vec1 * $vec1;

$power[2] = $power[1] * $power[1];

$power[3] = $power[2] * $power[2];

etc.

To calculate the power of our example, we simply initialize our result with 1 and consecutively multiply it with the items of the series of powers we just calculated, if the corresponding bit of the binary representation of the exponent is set:

$result = 1;

$result *= $power[0] if ($vec2 & 1);

$result *= $power[1] if ($vec2 & 2);

$result *= $power[2] if ($vec2 & 4);

$result *= $power[3] if ($vec2 & 8);

etc.

The bit vector "$vec3" must be of the same size as the base "$vec1" or greater. "$vec3" and "$vec1" may be the same vector (i.e., in-place calculation as in ""$vec1 **= $vec2;"" is possible), but "$vec3" and "$vec2" must be distinct. Finally, the exponent "$vec2" must be positive. A fatal error occurs if any of these conditions is not met.

o "$vector->Block_Store($buffer);"

This method allows you to load the contents of a given bit vector in one 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 to restore the previously saved bit vector.

For this, "$buffer" MUST be a string (NO automatic conversion from 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 fill the given bit vector, the remaining (most significant) bytes of the bit vector are filled with zeros, i.e., the previous contents of the bit vector are always erased completely.

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

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

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

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

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

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

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

See "syswrite" in perlfunc for how to write the data from this string to a file.

o "$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 this internal array of machine words.

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

Therefore, DO NOT USE these methods unless you are absolutely certain that 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 chunk sizes no greater than 32 bits.

The method ""Word_Size()"" returns the number of machine words that the internal array of words of the given bit vector contains.

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

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

This method allows you to store a given value "$word" at a given position "$offset" in the internal array of words of the given bit 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.

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

This method allows you to access the value of a given machine word at position "$offset" in the internal array of words of the given bit 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.

o "$vector->Word_List_Store(@words);"

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

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

If the list "@words" contains fewer elements than the internal array 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 internal array 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.

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

This method allows you to retrieve the internal array of machine words 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 the RIGHTMOST value in the returned list ("$words[$#words]") is the MOST significant word of the given bit vector.

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

o "$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 starting with 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 set to zero (cleared).

Note that this method does NOT increase the size of the given bit vector, 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 the given 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 out of 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.

o "$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"") are moved down by "$count" places.

The now vacant uppermost (most significant) "$count" words are then set to zero (cleared).

Note that this method does NOT decrease the size of the given bit vector, 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 shrink accordingly, 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 out of 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.

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

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

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

In order to be portable, though, you should never use chunk sizes larger 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 bits from the value "$chunk" to the given bit vector, starting at bit 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"" becomes bit 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, for example, when you are reading in data in chunks of, say, 8 bits, which you need to access later, say, using 16 bits at a time (like audio CD wave files, for instance).

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

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

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

In order to be portable, though, you should never use chunk sizes larger 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 vector starting at bit position "$offset" and proceeding upwards until bit 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.

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

This method allows you to fill the given bit vector with a list of data 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 of range" error will occur.

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

The given bit vector is thereby filled in ascending order: The first chunk 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 entire bit 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 entire bit 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 given bit 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 given bit 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);

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

This method allows you to access the contents of the given bit vector in form 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 of range" error will occur.

In order to be portable, though, you should never use chunk sizes larger 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 element is a full-grown Perl scalar, internally, with an associated memory overhead for its administration!) or at least cause a noticeable, more or less long-lasting "freeze" of your application!

Possible applications:

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

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

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

o "$vector->Index_List_Remove(@indices);"

This method allows you to specify a list of indices of bits which should 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 method does NOT clear the given bit vector before processing its list of arguments.

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

(The same holds for the method ""Index_List_Store()"". As a consequence, you can "wipe out" what you did using the method ""Index_List_Remove()"" by passing the identical argument list to the method ""Index_List_Store()"".)

o "$vector->Index_List_Store(@indices);"

This method allows you to specify a list of indices of bits which should 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 method does NOT clear the given bit vector before processing its list of arguments.

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

(The same holds for the method ""Index_List_Remove()"". As a consequence, you can "wipe out" what you did using the method ""Index_List_Store()"" by passing the identical argument list to the method ""Index_List_Remove()"".)

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

This method returns a list of Perl scalars.

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

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

Each scalar contains the number of the index corresponding to the 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 of prime numbers:

$limit = 1000; # or whatever

$vector = Bit::Vector->new($limit+1);

$vector->Primes();

@primes = $vector->Index_List_Read();

o "$vec3->Or($vec1,$vec2);"

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

This method calculates the union of "$set1" and "$set2" and stores the 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 operator is often denoted by a plus sign "+".)

In-place calculation is also possible, i.e., "$set3" may be identical with "$set1" or "$set2" or both.

o "$vec3->And($vec1,$vec2);"

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

This method calculates the intersection of "$set1" and "$set2" and stores 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 operator is often denoted by an asterisk "*".)

In-place calculation is also possible, i.e., "$set3" may be identical with "$set1" or "$set2" or both.

o "$vec3->AndNot($vec1,$vec2);"

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

This method calculates the difference of "$set1" less "$set2" and stores 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 identical with "$set1" or "$set2" or both.

o "$vec3->Xor($vec1,$vec2);"

"$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 set theory (the union of the two sets less their intersection).

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

Note that this method is also much more efficient than evaluating the above formula explicitly since it uses a built-in machine language instruction internally.

o "$vec2->Not($vec1);"

"$set2->Complement($set1);"

This method calculates the complement of "$set1" and stores the result in "$set2".

In "big integer" arithmetic, this is equivalent to calculating the one's complement of the number stored in the bit vector "$set1" in binary representation.

In-place calculation is also possible, i.e., "$set2" may be identical with "$set1".

o "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" must also be set in "$set2", but "$set2" may contain set bits which are not set in "$set1", in order for the condition of subset relationship to be true between these two sets.

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

o "$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 given set.

Uses a byte lookup table for calculating the number of set bits per byte, and thus needs a time for evaluation (and a number of loops) linearly proportional to the length of the given bit vector (in bytes).

This should be the fastest algorithm on average.

o "$norm = $set->Norm2();"

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

This is equivalent to the number of elements contained in the given set.

This does the same as the method ""Norm()"" above, only with a different algorithm:

This method counts the number of set and cleared bits at the same time and will stop when either of them has been exhausted, thus needing at most half as many loops per machine word as the total number of bits in a machine word - in fact it will need a number of loops equal to the minimum of the number of set bits and the number of cleared bits.

This might be a faster algorithm than of the method ""Norm()"" above on some systems, depending on the system's architecture and the compiler and optimisation used, for bit vectors with sparse set bits and for bit vectors with sparse cleared bits (i.e., predominantly set bits).

o "$norm = $set->Norm3();"

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

This is equivalent to the number of elements contained in the given set.

This does the same as the two methods ""Norm()"" and ""Norm2()"" above, however with a different algorithm.

In fact this is the implementation of the method ""Norm()"" used in previous versions of this module.

The method needs a number of loops per machine word equal to the number of set bits in that machine word.

Only for bit vectors with sparse set bits will this method be fast; it will depend on a system's architecture and compiler whether the method will be faster than any of the two methods above in such cases.

On average however, this is probably the slowest method of the three.

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

Returns the minimum of the given set, i.e., the minimum of all indices of all set bits in the given bit vector "$set".

If the set is empty (no set bits), plus infinity (represented by the constant "MAX_LONG" on your system) is returned.

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

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

Returns the maximum of the given set, i.e., the maximum of all indices of all set bits in the given bit vector "$set".

If the set is empty (no set bits), minus infinity (represented by 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.)

o "$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".

The method uses the binary "xor" operation (""^"") as the boolean addition operator (""+"").

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

An exception is also raised if the numbers of rows and columns of 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 Math::MatrixBool(3) for details.

o "$m3->Product($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".

This special method uses the binary "or" operation (""|"") as the boolean addition operator (""+"").

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

An exception is also raised if the numbers of rows and columns of 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 Math::MatrixBool(3) for details.

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

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

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

The reflexive transitive closure answers the question whether a path exists between any two vertices of a graph whose edges are 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 the question whether an EDGE exists between any two vertices of the graph or not, whereas the reflexive transitive closure answers the question whether a PATH (a series of adjacent edges) exists between any two vertices of the graph!

Note that the contents of the given matrix are modified by this method, so make a copy of the initial matrix in time if 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 matrix is not identical.

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

This method is used by the module "Math::MatrixBool".

See Math::MatrixBool(3) for details.

o "$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 and columns of any of the two matrices differs from the actual size of its underlying bit vector.

An exception is also raised if the following conditions are not met:

rows2 == cols1

cols2 == rows1

Note that in-place processing ("$matrix1" and "$matrix2" are identical) 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 Math::MatrixBool(3) for details.

#### SEE ALSO

Bit::Vector::Overload(3), Bit::Vector::String(3), Storable(3).

Set::IntRange(3), Math::MatrixBool(3), Math::MatrixReal(3), DFA::Kleene(3), Math::Kleene(3), Graph::Kruskal(3).

#### VERSION

This man page documents "Bit::Vector" version 7.4.

#### AUTHOR

Steffen Beyer

mailto:STBEY@cpan.org

http://www.engelschall.com/u/sb/download/

#### COPYRIGHT

Copyright (c) 1995 - 2013 by Steffen Beyer. All rights reserved.

#### LICENSE

This package is free software; you can redistribute it and/or modify it under the same terms as Perl itself, i.e., under the terms of the "Artistic License" or the "GNU General Public License".

The C library at the core of this Perl module can additionally be redistributed and/or modified under the terms of the "GNU Library 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 of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

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