Bit::Vector - Efficient bit vector, set of integers and "big int" math library
NAME
Bit::Vector - Efficient bit vector, set of integers and "big int" math library
SYNOPSIS
OVERLOADED OPERATORS
See the Bit::Vector::Overload(3) manpage.
MORE STRING IMPORT/EXPORT
See the Bit::Vector::String(3) manpage.
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
-
Method naming conventions
Method names completely in lower case indicate a boolean return value.
(Except for the bit vector constructor method "
new()", of course.) -
Boolean values
Boolean values in this module are always a numeric zero ("
0") for "false" and a numeric one ("1") for "true". -
Negative numbers
All numeric input parameters passed to any of the methods 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.
-
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).
-
"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_". -
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 ANSI C.
-
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. -
Index ranges
All indices for any given bits must lie between "
0" and "$vector->Size()-1", or a fatal "index out of range" error will occur.
DESCRIPTION
OVERLOADED OPERATORS
See the Bit::Vector::Overload(3) manpage.
MORE STRING IMPORT/EXPORT
See the Bit::Vector::String(3) manpage.
CLASS METHODS
-
$version = Bit::Vector->Version();Returns the current version number of this module.
-
$bits = Bit::Vector->Word_Bits();Returns the number of bits of an "unsigned int" (C type) on your machine.
(An "unsigned int" is also called a "machine word", hence the name of this method.)
-
$bits = Bit::Vector->Long_Bits();Returns the number of bits of an "unsigned long" (C type) on your machine.
-
$vector = Bit::Vector->new($bits);This is the bit vector constructor method.
Call this method to create a new bit vector containing "
$bits" bits (with indices ranging from "0" to "$bits-1").Note that - in contrast to previous versions - bit vectors of length zero (i.e., with
$bits = 0) are permitted now.The method returns a reference to the newly created bit vector.
A new bit vector is always initialized so that all bits are cleared (turned off).
An exception will be raised if the method is unable to allocate the necessary memory.
Note that if you specify a negative number for "
$bits" it will be interpreted as a large positive number due to its internal two's complement binary representation.In such a case, the bit vector constructor method will obediently attempt to create a bit vector of that size, probably resulting in an exception, as explained above.
-
@veclist = Bit::Vector->new($bits,$count);You can also create more than one bit vector at a time if you specify the optional second parameter "
$count".The method returns a list of "
$count" bit vectors which all have the same number of bits "$bits" (and which are all initialized, i.e., all bits are cleared).If "
$count" is zero, an empty list is returned.If "
$bits" is zero, a list of null-sized bit vectors is returned.Note again that if you specify a negative number for "
$count" it will be interpreted as a large positive number due to its internal two's complement binary representation.In such a case, the bit vector constructor method will obediently attempt to create that many bit vectors, probably resulting in an exception ("out of memory").
-
$vector = Bit::Vector->new_Hex($bits,$string);This method is an alternative constructor which allows you to create a new bit vector object (with "
$bits" bits) and to initialize it all in one go.The method internally first calls the bit vector constructor method "
new()" and then passes the given string to the method "from_Hex()".However, this method is more efficient than performing these two steps separately: First because in this method, the memory area occupied by the new bit vector is not initialized to zeros (which is pointless in this case), and second because it saves you from the associated overhead of one additional method invocation.
An exception will be raised if the necessary memory cannot be allocated (see the description of the method "
new()" immediately above for possible causes) or if the given string cannot be converted successfully (see the description of the method "from_Hex()" further below for details).In the latter case, the memory occupied by the new bit vector is released first (i.e., "free"d) before the exception is actually raised.
-
$vector = Bit::Vector->new_Bin($bits,$string);This method is an alternative constructor which allows you to create a new bit vector object (with "
$bits" bits) and to initialize it all in one go.The method internally first calls the bit vector constructor method "
new()" and then passes the given string to the method "from_Bin()".However, this method is more efficient than performing these two steps separately: First because in this method, the memory area occupied by the new bit vector is not initialized to zeros (which is pointless in this case), and second because it saves you from the associated overhead of one additional method invocation.
An exception will be raised if the necessary memory cannot be allocated (see the description of the method "
new()" above for possible causes) or if the given string cannot be converted successfully (see the description of the method "from_Bin()" further below for details).In the latter case, the memory occupied by the new bit vector is released first (i.e., "free"d) before the exception is actually raised.
-
$vector = Bit::Vector->new_Dec($bits,$string);This method is an alternative constructor which allows you to create a new bit vector object (with "
$bits" bits) and to initialize it all in one go.The method internally first calls the bit vector constructor method "
new()" and then passes the given string to the method "from_Dec()".However, this method is more efficient than performing these two steps separately: First because in this method, "
new()" does not initialize the memory area occupied by the new bit vector with zeros (which is pointless in this case, because "from_Dec()" will do it anyway), and second because it saves you from the associated overhead of one additional method invocation.An exception will be raised if the necessary memory cannot be allocated (see the description of the method "
new()" above for possible causes) or if the given string cannot be converted successfully (see the description of the method "from_Dec()" further below for details).In the latter case, the memory occupied by the new bit vector is released first (i.e., "free"d) before the exception is actually raised.
-
$vector = Bit::Vector->new_Enum($bits,$string);This method is an alternative constructor which allows you to create a new bit vector object (with "
$bits" bits) and to initialize it all in one go.The method internally first calls the bit vector constructor method "
new()" and then passes the given string to the method "from_Enum()".However, this method is more efficient than performing these two steps separately: First because in this method, "
new()" does not initialize the memory area occupied by the new bit vector with zeros (which is pointless in this case, because "from_Enum()" will do it anyway), and second because it saves you from the associated overhead of one additional method invocation.An exception will be raised if the necessary memory cannot be allocated (see the description of the method "
new()" above for possible causes) or if the given string cannot be converted successfully (see the description of the method "from_Enum()" further below for details).In the latter case, the memory occupied by the new bit vector is released first (i.e., "free"d) before the exception is actually raised.
-
$vector = Bit::Vector->Concat_List(@vectors);This method creates a new vector containing all bit vectors from the argument list in concatenated form.
The argument list may contain any number of arguments (including zero); the only condition is that all arguments must be bit vectors.
There is no condition concerning the length (in number of bits) of these arguments.
The vectors from the argument list are not changed in any way.
If the argument list is empty or if all arguments have length zero, the resulting bit vector will also have length zero.
Note that the RIGHTMOST bit vector from the argument list will become the LEAST significant part of the resulting bit vector, and the LEFTMOST bit vector from the argument list will become the MOST significant part of the resulting bit vector.
OBJECT METHODS
-
$vec2 = $vec1->new($bits);@veclist = $vec->new($bits);This is an alternative way of calling the bit vector constructor method.
Vector "
$vec1" (or "$vec") is not affected by this, it just serves as an anchor for the method invocation mechanism.In fact ALL class methods in this module can be called this way, even though this is probably considered to be "politically incorrect" by OO ("object-orientation") aficionados. ;-)
So even if you are too lazy to type "
Bit::Vector->" instead of "$vec1->" (and even though laziness is - allegedly - a programmer's virtue:-)), maybe it is better not to use this feature if you don't want to get booed at. ;-) -
$vec2 = $vec1->Shadow();Creates a NEW bit vector "
$vec2" of the SAME SIZE as "$vec1" but which is EMPTY.Just like a shadow that has the same shape as the object it originates from, but is flat and has no volume, i.e., contains nothing.
-
$vec2 = $vec1->Clone();Creates a NEW bit vector "
$vec2" of the SAME SIZE as "$vec1" which is an EXACT COPY of "$vec1". -
$vector = $vec1->Concat($vec2);This method returns a new bit vector object which is the result of the concatenation of the contents of "
$vec1" and "$vec2".Note that the contents of "
$vec1" become the MOST significant part of the resulting bit vector, and "$vec2" the LEAST significant part.If both bit vector arguments have length zero, the resulting bit vector will also have length zero.
-
$vector = $vec1->Concat_List($vec2,$vec3,...);This is an alternative way of calling this (class) method as an object method.
The method returns a new bit vector object which is the result of the concatenation of the contents of
$vec1 . $vec2 . $vec3 . ...See the section "class methods" above for a detailed description of this method.
Note that the argument list may be empty and that all arguments must be bit vectors if it isn't.
-
$bits = $vector->Size();Returns the size (number of bits) the given vector was created with (or "
Resize()"d to). -
$vector->Resize($bits);Changes the size of the given vector to the specified number of bits.
This method allows you to change the size of an existing bit vector, preserving as many bits from the old vector as will fit into the new one (i.e., all bits with indices smaller than the minimum of the sizes of both vectors, old and new).
If the number of machine words needed to store the new vector is smaller than or equal to the number of words needed to store the old vector, the memory allocated for the old vector is reused for the new one, and only the relevant book-keeping information is adjusted accordingly.
This means that even if the number of bits increases, new memory is not necessarily being allocated (i.e., if the old and the new number of bits fit into the same number of machine words).
If the number of machine words needed to store the new vector is greater than the number of words needed to store the old vector, new memory is allocated for the new vector, the old vector is copied to the new one, the remaining bits in the new vector are cleared (turned off) and the old vector is deleted, i.e., the memory that was allocated for it is released.
(An exception will be raised if the method is unable to allocate the necessary memory for the new vector.)
As a consequence, if you decrease the size of a given vector so that it will use fewer machine words, and increase it again later so that it will use more words than immediately before but still less than the original vector, new memory will be allocated anyway because the information about the size of the original vector is lost whenever you resize it.
Note also that if you specify a negative number for "
$bits" it will be interpreted as a large positive number due to its internal two's complement binary representation.In such a case, "Resize()" will obediently attempt to create a bit vector of that size, probably resulting in an exception, as explained above.
Finally, note that - in contrast to previous versions - resizing a bit vector to a size of zero bits (length zero) is now permitted.
-
$vec2->Copy($vec1);Copies the contents of bit vector "
$vec1" to bit vector "$vec2".The previous contents of bit vector "
$vec2" get overwritten, i.e., are lost.Both vectors must exist beforehand, i.e., this method does not CREATE any new bit vector object.
The two vectors may be of any size.
If the source bit vector is larger than the target, this method will copy as much of the least significant bits of the source vector as will fit into the target vector, thereby discarding any extraneous most significant bits.
BEWARE that this causes a brutal cutoff in the middle of your data, and it will also leave you with an almost unpredictable sign if subsequently the number in the target vector is going to be interpreted as a number! (You have been warned!)
If the target bit vector is larger than the source, this method fills up the remaining most significant bits in the target bit vector with either 0's or 1's, depending on the sign (= the most significant bit) of the source bit vector. This is also known as "sign extension".
This makes it possible to copy numbers from a smaller bit vector into a larger one while preserving the number's absolute value as well as its sign (due to the two's complement binary representation of numbers).
-
$vector->Empty();Clears all bits in the given vector.
-
$vector->Fill();Sets all bits in the given vector.
-
$vector->Flip();Flips (i.e., complements) all bits in the given vector.
-
$vector->Primes();Clears the given bit vector and sets all bits whose indices are prime numbers.
This method uses the algorithm known as the "Sieve of Erathostenes" internally.
-
$vec2->Reverse($vec1);This method copies the given vector "
$vec1" to the vector "$vec2", thereby reversing the order of all bits.I.e., the least significant bit of "
$vec1" becomes the most significant bit of "$vec2", whereas the most significant bit of "$vec1" becomes the least significant bit of "$vec2", and so forth for all bits in between.Note that in-place processing is also possible, i.e., "
$vec1" and "$vec2" may be identical.(Internally, this is the same as
$vec1->Interval_Reverse(0,$vec1->Size()-1);.) -
$vector->Interval_Empty($min,$max);Clears all bits in the interval
[$min..$max](including both limits) in the given vector."
$min" and "$max" may have the same value; this is the same as clearing a single bit with "Bit_Off()" (but less efficient).Note that
$vector->Interval_Empty(0,$vector->Size()-1);is the same as$vector->Empty();(but less efficient). -
$vector->Interval_Fill($min,$max);Sets all bits in the interval
[$min..$max](including both limits) in the given vector."
$min" and "$max" may have the same value; this is the same as setting a single bit with "Bit_On()" (but less efficient).Note that
$vector->Interval_Fill(0,$vector->Size()-1);is the same as$vector->Fill();(but less efficient). -
$vector->Interval_Flip($min,$max);Flips (i.e., complements) all bits in the interval
[$min..$max](including both limits) in the given vector."
$min" and "$max" may have the same value; this is the same as flipping a single bit with "bit_flip()" (but less efficient).Note that
$vector->Interval_Flip(0,$vector->Size()-1);is the same as$vector->Flip();and$vector->Complement($vector);(but less efficient). -
$vector->Interval_Reverse($min,$max);Reverses the order of all bits in the interval
[$min..$max](including both limits) in the given vector.I.e., bits "
$min" and "$max" swap places, and so forth for all bits in between."
$min" and "$max" may have the same value; this has no effect whatsoever, though. -
if (($min,$max) = $vector->Interval_Scan_inc($start))Returns the minimum and maximum indices of the next contiguous block of set bits (i.e., bits in the "on" state).
The search starts at index "
$start" (i.e.,"$min" >= "$start") and proceeds upwards (i.e.,"$max" >= "$min"), thus repeatedly increments the search pointer "$start" (internally).Note though that the contents of the variable (or scalar literal value) "
$start" is NOT altered. I.e., you have to set it to the desired value yourself prior to each call to "Interval_Scan_inc()" (see also the example given below).Actually, the bit vector is not searched bit by bit, but one machine word at a time, in order to speed up execution (which means that this method is quite efficient).
An empty list is returned if no such block can be found.
Note that a single set bit (surrounded by cleared bits) is a valid block by this definition. In that case the return values for "
$min" and "$max" are the same.Typical use:
$start = 0; while (($start < $vector->Size()) && (($min,$max) = $vector->Interval_Scan_inc($start))) { $start = $max + 2;# do something with $min and $max } -
if (($min,$max) = $vector->Interval_Scan_dec($start))Returns the minimum and maximum indices of the next contiguous block of set bits (i.e., bits in the "on" state).
The search starts at index "
$start" (i.e.,"$max" <= "$start") and proceeds downwards (i.e.,"$min" <= "$max"), thus repeatedly decrements the search pointer "$start" (internally).Note though that the contents of the variable (or scalar literal value) "
$start" is NOT altered. I.e., you have to set it to the desired value yourself prior to each call to "Interval_Scan_dec()" (see also the example given below).Actually, the bit vector is not searched bit by bit, but one machine word at a time, in order to speed up execution (which means that this method is quite efficient).
An empty list is returned if no such block can be found.
Note that a single set bit (surrounded by cleared bits) is a valid block by this definition. In that case the return values for "
$min" and "$max" are the same.Typical use:
$start = $vector->Size() - 1; while (($start >= 0) && (($min,$max) = $vector->Interval_Scan_dec($start))) { $start = $min - 2;# do something with $min and $max } -
$vec2->Interval_Copy($vec1,$offset2,$offset1,$length);This method allows you to copy a stretch of contiguous bits (starting at any position "
$offset1" you choose, with a length of "$length" bits) from a given "source" bit vector "$vec1" to another position "$offset2" in a "target" bit vector "$vec2".Note that the two bit vectors "
$vec1" and "$vec2" do NOT need to have the same (matching) size!Consequently, any of the two terms "
$offset1 + $length" and "$offset2 + $length" (or both) may exceed the actual length of its corresponding bit vector ("$vec1->Size()" and "$vec2->Size()", respectively).In such a case, the "
$length" parameter is automatically reduced internally so that both terms above are bounded by the number of bits of their corresponding bit vector.This may even result in a length of zero, in which case nothing is copied at all.
(Of course the value of the "
$length" parameter, supplied by you in the initial method call, may also be zero right from the start!)Note also that "
$offset1" and "$offset2" must lie within the range "0" and, respectively, "$vec1->Size()-1" or "$vec2->Size()-1", or a fatal "offset out of range" error will occur.Note further that "
$vec1" and "$vec2" may be identical, i.e., you may copy a stretch of contiguous bits from one part of a given bit vector to another part.The source and the target interval may even overlap, in which case the copying is automatically performed in ascending or descending order (depending on the direction of the copy - downwards or upwards in the bit vector, respectively) to handle this situation correctly, i.e., so that no bits are being overwritten before they have been copied themselves.
-
$vec2->Interval_Substitute($vec1,$off2,$len2,$off1,$len1);This method is (roughly) the same for bit vectors (i.e., arrays of booleans) as what the "splice" function in Perl is for lists (i.e., arrays of scalars).
(See splice in the perlfunc manpage for more details about this function.)
The method allows you to substitute a stretch of contiguous bits (defined by a position (offset) "
$off1" and a length of "$len1" bits) from a given "source" bit vector "$vec1" for a different stretch of contiguous bits (defined by a position (offset) "$off2" and a length of "$len2" bits) in another, "target" bit vector "$vec2".Note that the two bit vectors "
$vec1" and "$vec2" do NOT need to have the same (matching) size!Note further that "
$off1" and "$off2" must lie within the range "0" and, respectively, "$vec1->Size()" or "$vec2->Size()", or a fatal "offset out of range" error will occur.Alert readers will have noticed that these upper limits are NOT "
$vec1->Size()-1" and "$vec2->Size()-1", as they would be for any other method in this module, but that these offsets may actually point to one position PAST THE END of the corresponding bit vector.This is necessary in order to make it possible to APPEND a given stretch of bits to the target bit vector instead of REPLACING something in it.
For reasons of symmetry and generality, the same applies to the offset in the source bit vector, even though such an offset (one position past the end of the bit vector) does not serve any practical purpose there (but does not cause any harm either).
(Actually this saves you from the need of testing for this special case, in certain circumstances.)
Note that whenever the term "
$off1 + $len1" exceeds the size "$vec1->Size()" of bit vector "$vec1" (or if "$off2 + $len2" exceeds "$vec2->Size()"), the corresponding length ("$len1" or "$len2", respectively) is automatically reduced internally so that "$off1 + $len1 <= $vec1->Size()" (and "$off2 + $len2 <= $vec2->Size()") holds.(Note that this does NOT alter the intended result, even though this may seem counter-intuitive at first!)
This may even result in a length ("
$len1" or "$len2") of zero.A length of zero for the interval in the SOURCE bit vector ("
$len1 == 0") means that the indicated stretch of bits in the target bit vector (starting at position "$off2") is to be replaced by NOTHING, i.e., is to be DELETED.A length of zero for the interval in the TARGET bit vector ("
$len2== 0") means that NOTHING is replaced, and that the stretch of bits from the source bit vector is simply INSERTED into the target bit vector at the indicated position ("$off2").If both length parameters are zero, nothing is done at all.
Note that in contrast to any other method in this module (especially "
Interval_Copy()", "Insert()" and "Delete()"), this method IMPLICITLY and AUTOMATICALLY adapts the length of the resulting bit vector as needed, as given by$size = $vec2->Size(); # before $size += $len1 - $len2; # after(The only other method in this module that changes the size of a bit vector is the method "
Resize()".)In other words, replacing a given interval of bits in the target bit vector with a longer or shorter stretch of bits from the source bit vector, or simply inserting ("
$len2 == 0") a stretch of bits into or deleting ("$len1 == 0") an interval of bits from the target bit vector will automatically increase or decrease, respectively, the size of the target bit vector accordingly.For the sake of generality, this may even result in a bit vector with a size of zero (containing no bits at all).
This is also the reason why bit vectors of length zero are permitted in this module in the first place, starting with version 5.0.
Finally, note that "
$vec1" and "$vec2" may be identical, i.e., in-place processing is possible.(If you think about that for a while or if you look at the code, you will see that this is far from trivial!)
-
if ($vector->is_empty())Tests whether the given bit vector is empty, i.e., whether ALL of its bits are cleared (in the "off" state).
In "big integer" arithmetic, this is equivalent to testing whether the number stored in the bit vector is zero ("
0").Returns "true" ("
1") if the bit vector is empty and "false" ("0") otherwise.Note that this method also returns "true" ("
1") if the given bit vector has a length of zero, i.e., if it contains no bits at all. -
if ($vector->is_full())Tests whether the given bit vector is full, i.e., whether ALL of its bits are set (in the "on" state).
In "big integer" arithmetic, this is equivalent to testing whether the number stored in the bit vector is minus one ("-1").
Returns "true" ("
1") if the bit vector is full and "false" ("0") otherwise.If the given bit vector has a length of zero (i.e., if it contains no bits at all), this method returns "false" ("
0"). -
if ($vec1->equal($vec2))Tests the two given bit vectors for equality.
Returns "true" ("
1") if the two bit vectors are exact copies of one another and "false" ("0") otherwise. -
$cmp = $vec1->Lexicompare($vec2);Compares the two given bit vectors, which are regarded as UNSIGNED numbers in binary representation.
The method returns "
-1" if the first bit vector is smaller than the second bit vector, "0" if the two bit vectors are exact copies of one another and "1" if the first bit vector is greater than the second bit vector. -
$cmp = $vec1->Compare($vec2);Compares the two given bit vectors, which are regarded as SIGNED numbers in binary representation.
The method returns "
-1" if the first bit vector is smaller than the second bit vector, "0" if the two bit vectors are exact copies of one another and "1" if the first bit vector is greater than the second bit vector. -
$string = $vector->to_Hex();Returns a hexadecimal string representing the given bit vector.
Note that this representation is quite compact, in that it only needs at most twice the number of bytes needed to store the bit vector itself, internally.
Note also that since a hexadecimal digit is always worth four bits, the length of the resulting string is always a multiple of four bits, regardless of the true length (in bits) of the given bit vector.
Finally, note that the LEAST significant hexadecimal digit is located at the RIGHT end of the resulting string, and the MOST significant digit at the LEFT end.
-
$vector->from_Hex($string);Allows to read in the contents of a bit vector from a hexadecimal string, such as returned by the method "
to_Hex()" (see above).Remember that the least significant bits are always to the right of a hexadecimal string, and the most significant bits to the left. Therefore, the string is actually read in from right to left while the bit vector is filled accordingly, 4 bits at a time, starting with the least significant bits and going upward to the most significant bits.
If the given string contains less hexadecimal digits than are needed to completely fill the given bit vector, the remaining (most significant) bits are all cleared.
This also means that, even if the given string does not contain enough digits to completely fill the given bit vector, the previous contents of the bit vector are erased completely.
If the given string is longer than it needs to fill the given bit vector, the superfluous characters are simply ignored.
(In fact they are ignored completely - they are not even checked for proper syntax. See also below for more about that.)
This behaviour is intentional so that you may read in the string representing one bit vector into another bit vector of different size, i.e., as much of it as will fit.
If during the process of reading the given string any character is encountered which is not a hexadecimal digit, a fatal syntax error ensues ("input string syntax error").
-
$string = $vector->to_Bin();Returns a binary string representing the given bit vector.
Example:
$vector = Bit::Vector->new(8); $vector->Primes(); $string = $vector->to_Bin(); print "'$string'\n";
This prints:
'10101100'
(Bits #7, #5, #3 and #2 are set.)
Note that the LEAST significant bit is located at the RIGHT end of the resulting string, and the MOST significant bit at the LEFT end.
-
$vector->from_Bin($string);This method allows you to read in the contents of a bit vector from a binary string, such as returned by the method "
to_Bin()" (see above).Note that this method assumes that the LEAST significant bit is located at the RIGHT end of the binary string, and the MOST significant bit at the LEFT end. Therefore, the string is actually read in from right to left while the bit vector is filled accordingly, one bit at a time, starting with the least significant bit and going upward to the most significant bit.
If the given string contains less binary digits ("
0" and "1") than are needed to completely fill the given bit vector, the remaining (most significant) bits are all cleared.This also means that, even if the given string does not contain enough digits to completely fill the given bit vector, the previous contents of the bit vector are erased completely.
If the given string is longer than it needs to fill the given bit vector, the superfluous characters are simply ignored.
(In fact they are ignored completely - they are not even checked for proper syntax. See also below for more about that.)
This behaviour is intentional so that you may read in the string representing one bit vector into another bit vector of different size, i.e., as much of it as will fit.
If during the process of reading the given string any character is encountered which is not either "
0" or "1", a fatal syntax error ensues ("input string syntax error"). -
$string = $vector->to_Dec();This method returns a string representing the contents of the given bit vector converted to decimal (base
10).Note that this method assumes the given bit vector to be SIGNED (and to contain a number in two's complement binary representation).
Consequently, whenever the most significant bit of the given bit vector is set, the number stored in it is regarded as being NEGATIVE.
The resulting string can be fed into "
from_Dec()" (see below) in order to copy the contents of this bit vector to another one (or to restore the contents of this one). This is not advisable, though, since this would be very inefficient (there are much more efficient methods for storing and copying bit vectors in this module).Note that such conversion from binary to decimal is inherently slow since the bit vector has to be repeatedly divided by
10with remainder until the quotient becomes0(each remainder in turn represents a single decimal digit of the resulting string).This is also true for the implementation of this method in this module, even though a considerable effort has been made to speed it up: instead of repeatedly dividing by
10, the bit vector is repeatedly divided by the largest power of10that will fit into a machine word. The remainder is then repeatedly divided by10using only machine word arithmetics, which is much faster than dividing the whole bit vector ("divide and rule" principle).According to my own measurements, this resulted in an 8-fold speed increase over the straightforward approach.
Still, conversion to decimal should be used only where absolutely necessary.
Keep the resulting string stored in some variable if you need it again, instead of converting the bit vector all over again.
Beware that if you set the configuration for overloaded operators to "output=decimal", this method will be called for every bit vector enclosed in double quotes!
-
$vector->from_Dec($string);This method allows you to convert a given decimal number, which may be positive or negative, into two's complement binary representation, which is then stored in the given bit vector.
The decimal number should always be provided as a string, to avoid possible truncation (due to the limited precision of integers in Perl) or formatting (due to Perl's use of scientific notation for large numbers), which would lead to errors.
If the binary representation of the given decimal number is too big to fit into the given bit vector (if the given bit vector does not contain enough bits to hold it), a fatal "numeric overflow error" occurs.
If the input string contains other characters than decimal digits (
0-9) and an optional leading sign ("+" or "-"), a fatal "input string syntax error" occurs.Beware that large positive numbers which cause the most significant bit to be set (e.g. "255" in a bit vector with 8 bits) will be printed as negative numbers when converted back to decimal using the method "to_Dec()" (e.g. "-1", in our example), because numbers with the most significant bit set are considered to be negative in two's complement binary representation.
Note also that while it is possible to thusly enter negative numbers as large positive numbers (e.g. "255" for "-1" in a bit vector with 8 bits), the contrary isn't, i.e., you cannot enter "-255" for "+1", in our example. A fatal "numeric overflow error" will occur if you try to do so.
If possible program abortion is unwanted or intolerable, use "
eval", like this:eval { $vector->from_Dec("1152921504606846976"); }; if ($@) { # an error occurred }
There are four possible error messages:
if ($@ =~ /item is not a string/)
if ($@ =~ /input string syntax error/)
if ($@ =~ /numeric overflow error/)
if ($@ =~ /unable to allocate memory/)
Note that the conversion from decimal to binary is costly in terms of processing time, since a lot of multiplications have to be carried out (in principle, each decimal digit must be multiplied with the binary representation of the power of
10corresponding to its position in the decimal number, i.e., 1, 10, 100, 1000, 10000 and so on).This is not as time consuming as the opposite conversion, from binary to decimal (where successive divisions have to be carried out, which are even more expensive than multiplications), but still noticeable.
Again (as in the case of "
to_Dec()"), the implementation of this method in this module uses the principle of "divide and rule" in order to speed up the conversion, i.e., as many decimal digits as possible are first accumulated (converted) in a machine word and only then stored in the given bit vector.Even so, use this method only where absolutely necessary if speed is an important consideration in your application.
Beware that if you set the configuration for overloaded operators to "input=decimal", this method will be called for every scalar operand you use!
-
$string = $vector->to_Enum();Converts the given bit vector or set into an enumeration of single indices and ranges of indices (".newsrc" style), representing the bits that are set ("
1") in the bit vector.Example:
$vector = Bit::Vector->new(20); $vector->Bit_On(2); $vector->Bit_On(3); $vector->Bit_On(11); $vector->Interval_Fill(5,7); $vector->Interval_Fill(13,19); print "'", $vector->to_Enum(), "'\n";
which prints
'2,3,5-7,11,13-19'
If the given bit vector is empty, the resulting string will also be empty.
Note, by the way, that the above example can also be written a little handier, perhaps, as follows:
Bit::Vector->Configuration("out=enum"); $vector = Bit::Vector->new(20); $vector->Index_List_Store(2,3,5,6,7,11,13,14,15,16,17,18,19); print "'$vector'\n";
-
$vector->from_Enum($string);This method first empties the given bit vector and then tries to set the bits and ranges of bits specified in the given string.
The string "
$string" must only contain unsigned integers or ranges of integers (two unsigned integers separated by a dash "-"), separated by commas (",").All other characters are disallowed (including white space!) and will lead to a fatal "input string syntax error".
In each range, the first integer (the lower limit of the range) must always be less than or equal to the second integer (the upper limit), or a fatal "minimum > maximum index" error occurs.
All integers must lie in the permitted range for the given bit vector, i.e., they must lie between "
0" and "$vector->Size()-1".If this condition is not met, a fatal "index out of range" error occurs.
If possible program abortion is unwanted or intolerable, use "
eval", like this:eval { $vector->from_Enum("2,3,5-7,11,13-19"); }; if ($@) { # an error occurred }
There are four possible error messages:
if ($@ =~ /item is not a string/)
if ($@ =~ /input string syntax error/)
if ($@ =~ /index out of range/)
if ($@ =~ /minimum > maximum index/)
Note that the order of the indices and ranges is irrelevant, i.e.,
eval { $vector->from_Enum("11,5-7,3,13-19,2"); };
results in the same vector as in the example above.
Ranges and indices may also overlap.
This is because each (single) index in the string is passed to the method "
Bit_On()", internally, and each range to the method "Interval_Fill()".This means that the resulting bit vector is just the union of all the indices and ranges specified in the given string.
-
$vector->Bit_Off($index);Clears the bit with index "
$index" in the given vector. -
$vector->Bit_On($index);Sets the bit with index "
$index" in the given vector. -
$vector->bit_flip($index)Flips (i.e., complements) the bit with index "
$index" in the given vector.Moreover, this method returns the NEW state of the bit in question, i.e., it returns "
0" if the bit is cleared or "1" if the bit is set (AFTER flipping it). -
if ($vector->bit_test($index))if ($vector->contains($index))Returns the current state of the bit with index "
$index" in the given vector, i.e., returns "0" if it is cleared (in the "off" state) or "1" if it is set (in the "on" state). -
$vector->Bit_Copy($index,$bit);Sets the bit with index "
$index" in the given vector either to "0" or "1" depending on the boolean value "$bit". -
$vector->LSB($bit);Allows you to set the least significant bit in the given bit vector to the value given by the boolean parameter "
$bit".This is a (faster) shortcut for "
$vector->Bit_Copy(0,$bit);". -
$vector->MSB($bit);Allows you to set the most significant bit in the given bit vector to the value given by the boolean parameter "
$bit".This is a (faster) shortcut for "
$vector->Bit_Copy($vector->Size()-1,$bit);". -
$bit = $vector->lsb();Returns the least significant bit of the given bit vector.
This is a (faster) shortcut for "
$bit = $vector->bit_test(0);". -
$bit = $vector->msb();Returns the most significant bit of the given bit vector.
This is a (faster) shortcut for "
$bit = $vector->bit_test($vector->Size()-1);". -
$carry_out = $vector->rotate_left();carry MSB vector: LSB out: +---+ +---+---+---+--- ---+---+---+---+ | | <---+--- | | | | ... | | | | <---+ +---+ | +---+---+---+--- ---+---+---+---+ | | | +------------------------------------------------+The least significant bit (LSB) is the bit with index "
0", the most significant bit (MSB) is the bit with index "$vector->Size()-1". -
$carry_out = $vector->rotate_right();MSB vector: LSB carry out: +---+---+---+--- ---+---+---+---+ +---+ +---> | | | | ... | | | | ---+---> | | | +---+---+---+--- ---+---+---+---+ | +---+ | | +------------------------------------------------+The least significant bit (LSB) is the bit with index "
0", the most significant bit (MSB) is the bit with index "$vector->Size()-1". -
$carry_out = $vector->shift_left($carry_in);carry MSB vector: LSB carry out: in: +---+ +---+---+---+--- ---+---+---+---+ +---+ | | <--- | | | | ... | | | | <--- | | +---+ +---+---+---+--- ---+---+---+---+ +---+
The least significant bit (LSB) is the bit with index "
0", the most significant bit (MSB) is the bit with index "$vector->Size()-1". -
$carry_out = $vector->shift_right($carry_in);carry MSB vector: LSB carry in: out: +---+ +---+---+---+--- ---+---+---+---+ +---+ | | ---> | | | | ... | | | | ---> | | +---+ +---+---+---+--- ---+---+---+---+ +---+
The least significant bit (LSB) is the bit with index "
0", the most significant bit (MSB) is the bit with index "$vector->Size()-1". -
$vector->Move_Left($bits);Shifts the given bit vector left by "
$bits" bits, i.e., inserts "$bits" new bits at the lower end (least significant bit) of the bit vector, moving all other bits up by "$bits" places, thereby losing the "$bits" most significant bits.The inserted new bits are all cleared (set to the "off" state).
This method does nothing if "
$bits" is equal to zero.Beware that the whole bit vector is cleared WITHOUT WARNING if "
$bits" is greater than or equal to the size of the given bit vector!In fact this method is equivalent to
for ( $i = 0; $i < $bits; $i++ ) { $vector->shift_left(0); }
except that it is much more efficient (for "
$bits" greater than or equal to the number of bits in a machine word on your system) than this straightforward approach. -
$vector->Move_Right($bits);Shifts the given bit vector right by "
$bits" bits, i.e., deletes the "$bits" least significant bits of the bit vector, moving all other 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. -
$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. -
$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. -
$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.
-
$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.
-
$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. -
$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. -
$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:
# initializefor ( $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.
-
$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.,