4 Bit::Vector - Efficient bit vector, set of integers and "big int" math library
8 =head2 OVERLOADED OPERATORS
10 See L<Bit::Vector::Overload(3)>.
12 =head2 MORE STRING IMPORT/EXPORT
14 See L<Bit::Vector::String(3)>.
19 $version = Bit::Vector->Version();
22 $bits = Bit::Vector->Word_Bits(); # bits in a machine word
25 $bits = Bit::Vector->Long_Bits(); # bits in an unsigned long
28 $vector = Bit::Vector->new($bits); # bit vector constructor
30 @veclist = Bit::Vector->new($bits,$count);
33 $vector = Bit::Vector->new_Hex($bits,$string);
36 $vector = Bit::Vector->new_Bin($bits,$string);
39 $vector = Bit::Vector->new_Dec($bits,$string);
42 $vector = Bit::Vector->new_Enum($bits,$string);
45 $vector = Bit::Vector->Concat_List(@vectors);
50 $vec2 = $vec1->new($bits); # alternative call of constructor
52 @veclist = $vec->new($bits,$count);
55 $vec2 = $vec1->Shadow(); # new vector, same size but empty
58 $vec2 = $vec1->Clone(); # new vector, exact duplicate
61 $vector = $vec1->Concat($vec2);
64 $vector = $vec1->Concat_List($vec2,$vec3,...);
67 $bits = $vector->Size();
70 $vector->Resize($bits);
71 $vector->Resize($vector->Size()+5);
72 $vector->Resize($vector->Size()-5);
87 $vector->Primes(); # Sieve of Erathostenes
90 $vec2->Reverse($vec1);
93 $vector->Interval_Empty($min,$max);
96 $vector->Interval_Fill($min,$max);
99 $vector->Interval_Flip($min,$max);
102 $vector->Interval_Reverse($min,$max);
105 if (($min,$max) = $vector->Interval_Scan_inc($start))
108 if (($min,$max) = $vector->Interval_Scan_dec($start))
111 $vec2->Interval_Copy($vec1,$offset2,$offset1,$length);
114 $vec2->Interval_Substitute($vec1,$off2,$len2,$off1,$len1);
117 if ($vector->is_empty())
120 if ($vector->is_full())
123 if ($vec1->equal($vec2))
125 Lexicompare (unsigned)
126 if ($vec1->Lexicompare($vec2) == 0)
127 if ($vec1->Lexicompare($vec2) != 0)
128 if ($vec1->Lexicompare($vec2) < 0)
129 if ($vec1->Lexicompare($vec2) <= 0)
130 if ($vec1->Lexicompare($vec2) > 0)
131 if ($vec1->Lexicompare($vec2) >= 0)
134 if ($vec1->Compare($vec2) == 0)
135 if ($vec1->Compare($vec2) != 0)
136 if ($vec1->Compare($vec2) < 0)
137 if ($vec1->Compare($vec2) <= 0)
138 if ($vec1->Compare($vec2) > 0)
139 if ($vec1->Compare($vec2) >= 0)
142 $string = $vector->to_Hex();
145 $vector->from_Hex($string);
148 $string = $vector->to_Bin();
151 $vector->from_Bin($string);
154 $string = $vector->to_Dec();
157 $vector->from_Dec($string);
160 $string = $vector->to_Enum(); # e.g. "2,3,5-7,11,13-19"
163 $vector->from_Enum($string);
166 $vector->Bit_Off($index);
169 $vector->Bit_On($index);
172 $bit = $vector->bit_flip($index);
176 $bit = $vector->bit_test($index);
177 $bit = $vector->contains($index);
178 if ($vector->bit_test($index))
179 if ($vector->contains($index))
182 $vector->Bit_Copy($index,$bit);
184 LSB (least significant bit)
187 MSB (most significant bit)
190 lsb (least significant bit)
191 $bit = $vector->lsb();
193 msb (most significant bit)
194 $bit = $vector->msb();
197 $carry = $vector->rotate_left();
200 $carry = $vector->rotate_right();
203 $carry = $vector->shift_left($carry);
206 $carry = $vector->shift_right($carry);
209 $vector->Move_Left($bits); # shift left "$bits" positions
212 $vector->Move_Right($bits); # shift right "$bits" positions
215 $vector->Insert($offset,$bits);
218 $vector->Delete($offset,$bits);
221 $carry = $vector->increment();
224 $carry = $vector->decrement();
227 $overflow = $vec2->inc($vec1);
230 $overflow = $vec2->dec($vec1);
233 $carry = $vec3->add($vec1,$vec2,$carry);
234 ($carry,$overflow) = $vec3->add($vec1,$vec2,$carry);
237 $carry = $vec3->subtract($vec1,$vec2,$carry);
238 ($carry,$overflow) = $vec3->subtract($vec1,$vec2,$carry);
243 $vec2->Negate($vec1);
248 $vec2->Absolute($vec1);
251 if ($vector->Sign() == 0)
252 if ($vector->Sign() != 0)
253 if ($vector->Sign() < 0)
254 if ($vector->Sign() <= 0)
255 if ($vector->Sign() > 0)
256 if ($vector->Sign() >= 0)
259 $vec3->Multiply($vec1,$vec2);
262 $quot->Divide($vec1,$vec2,$rest);
264 GCD (Greatest Common Divisor)
265 $vecgcd->GCD($veca,$vecb);
266 $vecgcd->GCD($vecx,$vecy,$veca,$vecb);
269 $vec3->Power($vec1,$vec2);
272 $vector->Block_Store($buffer);
275 $buffer = $vector->Block_Read();
278 $size = $vector->Word_Size(); # number of words in "$vector"
281 $vector->Word_Store($offset,$word);
284 $word = $vector->Word_Read($offset);
287 $vector->Word_List_Store(@words);
290 @words = $vector->Word_List_Read();
293 $vector->Word_Insert($offset,$count);
296 $vector->Word_Delete($offset,$count);
299 $vector->Chunk_Store($chunksize,$offset,$chunk);
302 $chunk = $vector->Chunk_Read($chunksize,$offset);
305 $vector->Chunk_List_Store($chunksize,@chunks);
308 @chunks = $vector->Chunk_List_Read($chunksize);
311 $vector->Index_List_Remove(@indices);
314 $vector->Index_List_Store(@indices);
317 @indices = $vector->Index_List_Read();
321 $vec3->Or($vec1,$vec2);
322 $set3->Union($set1,$set2);
326 $vec3->And($vec1,$vec2);
327 $set3->Intersection($set1,$set2);
331 $vec3->AndNot($vec1,$vec2);
332 $set3->Difference($set1,$set2);
336 $vec3->Xor($vec1,$vec2);
337 $set3->ExclusiveOr($set1,$set2);
342 $set2->Complement($set1);
345 if ($set1->subset($set2)) # true if $set1 is subset of $set2
348 $norm = $set->Norm();
349 $norm = $set->Norm2();
350 $norm = $set->Norm3();
359 $matrix3->Multiplication($rows3,$cols3,
360 $matrix1,$rows1,$cols1,
361 $matrix2,$rows2,$cols2);
364 $matrix3->Product($rows3,$cols3,
365 $matrix1,$rows1,$cols1,
366 $matrix2,$rows2,$cols2);
369 $matrix->Closure($rows,$cols);
372 $matrix2->Transpose($rows2,$cols2,$matrix1,$rows1,$cols1);
374 =head1 IMPORTANT NOTES
380 Method naming conventions
382 Method names completely in lower case indicate a boolean return value.
384 (Except for the bit vector constructor method "C<new()>", of course.)
390 Boolean values in this module are always a numeric zero ("C<0>") for
391 "false" and a numeric one ("C<1>") for "true".
397 All numeric input parameters passed to any of the methods in this module
398 are regarded as being B<UNSIGNED> (as opposed to the contents of the
399 bit vectors themselves, which are usually considered to be B<SIGNED>).
401 As a consequence, whenever you pass a negative number as an argument to
402 some method of this module, it will be treated as a (usually very large)
403 positive number due to its internal two's complement binary representation,
404 usually resulting in an "index out of range" error message and program
411 Note that bit vectors are stored least order bit and least order word first
414 I.e., bit #0 of any given bit vector corresponds to bit #0 of word #0 in the
415 array of machine words representing the bit vector.
417 (Where word #0 comes first in memory, i.e., it is stored at the least memory
418 address in the allocated block of memory holding the given bit vector.)
420 Note however that machine words can be stored least order byte first or last,
421 depending on your system's implementation.
423 When you are exporting or importing a whole bit vector at once using the
424 methods "C<Block_Read()>" and "C<Block_Store()>" (the only time in this
425 module where this could make any difference), however, a conversion to and
426 from "least order byte first" order is automatically supplied.
428 In other words, what "C<Block_Read()>" provides and what "C<Block_Store()>"
429 expects is always in "least order byte first" order, regardless of the order
430 in which words are stored internally on your machine.
432 This is to make sure that what you export on one machine using "C<Block_Read()>"
433 can always be read in correctly with "C<Block_Store()>" on a different machine.
435 Note further that whenever bit vectors are converted to and from (binary or
436 hexadecimal) strings, the B<RIGHTMOST> bit is always the B<LEAST SIGNIFICANT>
437 one, and the B<LEFTMOST> bit is always the B<MOST SIGNIFICANT> bit.
439 This is because in our western culture, numbers are always represented in this
440 way (least significant to most significant digits go from right to left).
442 Of course this requires an internal reversion of order, which the corresponding
443 conversion methods perform automatically (without any additional overhead, it's
444 just a matter of starting the internal loop at the bottom or the top end).
448 "Word" related methods
450 Note that all methods whose names begin with "C<Word_>" are
451 B<MACHINE-DEPENDENT>!
453 They depend on the size (number of bits) of an "unsigned int" (C type) on
456 Therefore, you should only use these methods if you are B<ABSOLUTELY CERTAIN>
457 that portability of your code is not an issue!
459 Note that you can use arbitrarily large chunks (i.e., fragments of bit vectors)
460 of up to 32 bits B<IN A PORTABLE WAY> using the methods whose names begin with
467 Note that legal chunk sizes for all methods whose names begin with "C<Chunk_>"
468 range from "C<1>" to "C<Bit::Vector-E<gt>Long_Bits();>" bits ("C<0>" is B<NOT>
471 In order to make your programs portable, however, you shouldn't use chunk sizes
472 larger than 32 bits, since this is the minimum size of an "unsigned long"
473 (C type) on all systems, as prescribed by S<ANSI C>.
479 In general, for methods involving several bit vectors at the same time, all
480 bit vector arguments must have identical sizes (number of bits), or a fatal
481 "size mismatch" error will occur.
483 Exceptions from this rule are the methods "C<Concat()>", "C<Concat_List()>",
484 "C<Copy()>", "C<Interval_Copy()>" and "C<Interval_Substitute()>", where no
485 conditions at all are imposed on the size of their bit vector arguments.
487 In method "C<Multiply()>", all three bit vector arguments must in principle
488 obey the rule of matching sizes, but the bit vector in which the result of
489 the multiplication is to be stored may be larger than the two bit vector
490 arguments containing the factors for the multiplication.
492 In method "C<Power()>", the bit vector for the result must be the same
493 size or greater than the base of the exponentiation term. The exponent
500 All indices for any given bits must lie between "C<0>" and
501 "C<$vector-E<gt>Size()-1>", or a fatal "index out of range"
508 =head2 OVERLOADED OPERATORS
510 See L<Bit::Vector::Overload(3)>.
512 =head2 MORE STRING IMPORT/EXPORT
514 See L<Bit::Vector::String(3)>.
522 C<$version = Bit::Vector-E<gt>Version();>
524 Returns the current version number of this module.
528 C<$bits = Bit::Vector-E<gt>Word_Bits();>
530 Returns the number of bits of an "unsigned int" (C type)
533 (An "unsigned int" is also called a "machine word",
534 hence the name of this method.)
538 C<$bits = Bit::Vector-E<gt>Long_Bits();>
540 Returns the number of bits of an "unsigned long" (C type)
545 C<$vector = Bit::Vector-E<gt>new($bits);>
547 This is the bit vector constructor method.
549 Call this method to create a new bit vector containing "C<$bits>"
550 bits (with indices ranging from "C<0>" to "C<$bits-1>").
552 Note that - in contrast to previous versions - bit vectors
553 of length zero (i.e., with C<$bits = 0>) are permitted now.
555 The method returns a reference to the newly created bit vector.
557 A new bit vector is always initialized so that all bits are cleared
560 An exception will be raised if the method is unable to allocate the
563 Note that if you specify a negative number for "C<$bits>" it will be
564 interpreted as a large positive number due to its internal two's
565 complement binary representation.
567 In such a case, the bit vector constructor method will obediently attempt
568 to create a bit vector of that size, probably resulting in an exception,
573 C<@veclist = Bit::Vector-E<gt>new($bits,$count);>
575 You can also create more than one bit vector at a time if you specify the
576 optional second parameter "C<$count>".
578 The method returns a list of "C<$count>" bit vectors which all have the
579 same number of bits "C<$bits>" (and which are all initialized, i.e.,
580 all bits are cleared).
582 If "C<$count>" is zero, an empty list is returned.
584 If "C<$bits>" is zero, a list of null-sized bit vectors is returned.
586 Note again that if you specify a negative number for "C<$count>" it will
587 be interpreted as a large positive number due to its internal two's
588 complement binary representation.
590 In such a case, the bit vector constructor method will obediently attempt
591 to create that many bit vectors, probably resulting in an exception ("out
596 C<$vector = Bit::Vector-E<gt>new_Hex($bits,$string);>
598 This method is an alternative constructor which allows you to create
599 a new bit vector object (with "C<$bits>" bits) and to initialize it
602 The method internally first calls the bit vector constructor method
603 "C<new()>" and then passes the given string to the method "C<from_Hex()>".
605 However, this method is more efficient than performing these two steps
606 separately: First because in this method, the memory area occupied by
607 the new bit vector is not initialized to zeros (which is pointless in
608 this case), and second because it saves you from the associated overhead
609 of one additional method invocation.
611 An exception will be raised if the necessary memory cannot be allocated
612 (see the description of the method "C<new()>" immediately above for
613 possible causes) or if the given string cannot be converted successfully
614 (see the description of the method "C<from_Hex()>" further below for
617 In the latter case, the memory occupied by the new bit vector is
618 released first (i.e., "free"d) before the exception is actually
623 C<$vector = Bit::Vector-E<gt>new_Bin($bits,$string);>
625 This method is an alternative constructor which allows you to create
626 a new bit vector object (with "C<$bits>" bits) and to initialize it
629 The method internally first calls the bit vector constructor method
630 "C<new()>" and then passes the given string to the method "C<from_Bin()>".
632 However, this method is more efficient than performing these two steps
633 separately: First because in this method, the memory area occupied by
634 the new bit vector is not initialized to zeros (which is pointless in
635 this case), and second because it saves you from the associated overhead
636 of one additional method invocation.
638 An exception will be raised if the necessary memory cannot be allocated
639 (see the description of the method "C<new()>" above for possible causes)
640 or if the given string cannot be converted successfully (see the
641 description of the method "C<from_Bin()>" further below for details).
643 In the latter case, the memory occupied by the new bit vector is
644 released first (i.e., "free"d) before the exception is actually
649 C<$vector = Bit::Vector-E<gt>new_Dec($bits,$string);>
651 This method is an alternative constructor which allows you to create
652 a new bit vector object (with "C<$bits>" bits) and to initialize it
655 The method internally first calls the bit vector constructor method
656 "C<new()>" and then passes the given string to the method "C<from_Dec()>".
658 However, this method is more efficient than performing these two steps
659 separately: First because in this method, "C<new()>" does not initialize
660 the memory area occupied by the new bit vector with zeros (which is
661 pointless in this case, because "C<from_Dec()>" will do it anyway),
662 and second because it saves you from the associated overhead of one
663 additional method invocation.
665 An exception will be raised if the necessary memory cannot be allocated
666 (see the description of the method "C<new()>" above for possible causes)
667 or if the given string cannot be converted successfully (see the
668 description of the method "C<from_Dec()>" further below for details).
670 In the latter case, the memory occupied by the new bit vector is
671 released first (i.e., "free"d) before the exception is actually
676 C<$vector = Bit::Vector-E<gt>new_Enum($bits,$string);>
678 This method is an alternative constructor which allows you to create
679 a new bit vector object (with "C<$bits>" bits) and to initialize it
682 The method internally first calls the bit vector constructor method
683 "C<new()>" and then passes the given string to the method "C<from_Enum()>".
685 However, this method is more efficient than performing these two steps
686 separately: First because in this method, "C<new()>" does not initialize
687 the memory area occupied by the new bit vector with zeros (which is
688 pointless in this case, because "C<from_Enum()>" will do it anyway),
689 and second because it saves you from the associated overhead of one
690 additional method invocation.
692 An exception will be raised if the necessary memory cannot be allocated
693 (see the description of the method "C<new()>" above for possible causes)
694 or if the given string cannot be converted successfully (see the
695 description of the method "C<from_Enum()>" further below for details).
697 In the latter case, the memory occupied by the new bit vector is
698 released first (i.e., "free"d) before the exception is actually
703 C<$vector = Bit::Vector-E<gt>Concat_List(@vectors);>
705 This method creates a new vector containing all bit vectors from the
706 argument list in concatenated form.
708 The argument list may contain any number of arguments (including
709 zero); the only condition is that all arguments must be bit vectors.
711 There is no condition concerning the length (in number of bits) of
714 The vectors from the argument list are not changed in any way.
716 If the argument list is empty or if all arguments have length zero,
717 the resulting bit vector will also have length zero.
719 Note that the B<RIGHTMOST> bit vector from the argument list will
720 become the B<LEAST> significant part of the resulting bit vector,
721 and the B<LEFTMOST> bit vector from the argument list will
722 become the B<MOST> significant part of the resulting bit vector.
726 =head2 OBJECT METHODS
732 C<$vec2 = $vec1-E<gt>new($bits);>
734 C<@veclist = $vec-E<gt>new($bits);>
736 This is an alternative way of calling the bit vector constructor method.
738 Vector "C<$vec1>" (or "C<$vec>") is not affected by this, it just serves
739 as an anchor for the method invocation mechanism.
741 In fact B<ALL> class methods in this module can be called this way,
742 even though this is probably considered to be "politically incorrect"
743 by OO ("object-orientation") aficionados. ;-)
745 So even if you are too lazy to type "C<Bit::Vector-E<gt>>" instead of
746 "C<$vec1-E<gt>>" (and even though laziness is - allegedly - a programmer's
747 virtue C<:-)>), maybe it is better not to use this feature if you don't
748 want to get booed at. ;-)
752 C<$vec2 = $vec1-E<gt>Shadow();>
754 Creates a B<NEW> bit vector "C<$vec2>" of the B<SAME SIZE> as "C<$vec1>"
755 but which is B<EMPTY>.
757 Just like a shadow that has the same shape as the object it
758 originates from, but is flat and has no volume, i.e., contains
763 C<$vec2 = $vec1-E<gt>Clone();>
765 Creates a B<NEW> bit vector "C<$vec2>" of the B<SAME SIZE> as "C<$vec1>"
766 which is an B<EXACT COPY> of "C<$vec1>".
770 C<$vector = $vec1-E<gt>Concat($vec2);>
772 This method returns a new bit vector object which is the result of the
773 concatenation of the contents of "C<$vec1>" and "C<$vec2>".
775 Note that the contents of "C<$vec1>" become the B<MOST> significant part
776 of the resulting bit vector, and "C<$vec2>" the B<LEAST> significant part.
778 If both bit vector arguments have length zero, the resulting bit vector
779 will also have length zero.
783 C<$vector = $vec1-E<gt>Concat_List($vec2,$vec3,...);>
785 This is an alternative way of calling this (class) method as an
788 The method returns a new bit vector object which is the result of
789 the concatenation of the contents of C<$vec1 . $vec2 . $vec3 . ...>
791 See the section "class methods" above for a detailed description of
794 Note that the argument list may be empty and that all arguments
795 must be bit vectors if it isn't.
799 C<$bits = $vector-E<gt>Size();>
801 Returns the size (number of bits) the given vector was created with
802 (or "C<Resize()>"d to).
806 C<$vector-E<gt>Resize($bits);>
808 Changes the size of the given vector to the specified number of bits.
810 This method allows you to change the size of an existing bit vector,
811 preserving as many bits from the old vector as will fit into the
812 new one (i.e., all bits with indices smaller than the minimum of the
813 sizes of both vectors, old and new).
815 If the number of machine words needed to store the new vector is smaller
816 than or equal to the number of words needed to store the old vector, the
817 memory allocated for the old vector is reused for the new one, and only
818 the relevant book-keeping information is adjusted accordingly.
820 This means that even if the number of bits increases, new memory is not
821 necessarily being allocated (i.e., if the old and the new number of bits
822 fit into the same number of machine words).
824 If the number of machine words needed to store the new vector is greater
825 than the number of words needed to store the old vector, new memory is
826 allocated for the new vector, the old vector is copied to the new one,
827 the remaining bits in the new vector are cleared (turned off) and the old
828 vector is deleted, i.e., the memory that was allocated for it is released.
830 (An exception will be raised if the method is unable to allocate the
831 necessary memory for the new vector.)
833 As a consequence, if you decrease the size of a given vector so that
834 it will use fewer machine words, and increase it again later so that it
835 will use more words than immediately before but still less than the
836 original vector, new memory will be allocated anyway because the
837 information about the size of the original vector is lost whenever
840 Note also that if you specify a negative number for "C<$bits>" it will
841 be interpreted as a large positive number due to its internal two's
842 complement binary representation.
844 In such a case, "Resize()" will obediently attempt to create a bit
845 vector of that size, probably resulting in an exception, as explained
848 Finally, note that - in contrast to previous versions - resizing a bit
849 vector to a size of zero bits (length zero) is now permitted.
853 C<$vec2-E<gt>Copy($vec1);>
855 Copies the contents of bit vector "C<$vec1>" to bit vector "C<$vec2>".
857 The previous contents of bit vector "C<$vec2>" get overwritten, i.e.,
860 Both vectors must exist beforehand, i.e., this method does not B<CREATE>
861 any new bit vector object.
863 The two vectors may be of any size.
865 If the source bit vector is larger than the target, this method will copy
866 as much of the least significant bits of the source vector as will fit into
867 the target vector, thereby discarding any extraneous most significant bits.
869 BEWARE that this causes a brutal cutoff in the middle of your data, and it
870 will also leave you with an almost unpredictable sign if subsequently the
871 number in the target vector is going to be interpreted as a number! (You
874 If the target bit vector is larger than the source, this method fills up
875 the remaining most significant bits in the target bit vector with either
876 0's or 1's, depending on the sign (= the most significant bit) of the
877 source bit vector. This is also known as "sign extension".
879 This makes it possible to copy numbers from a smaller bit vector into
880 a larger one while preserving the number's absolute value as well as
881 its sign (due to the two's complement binary representation of numbers).
885 C<$vector-E<gt>Empty();>
887 Clears all bits in the given vector.
891 C<$vector-E<gt>Fill();>
893 Sets all bits in the given vector.
897 C<$vector-E<gt>Flip();>
899 Flips (i.e., complements) all bits in the given vector.
903 C<$vector-E<gt>Primes();>
905 Clears the given bit vector and sets all bits whose
906 indices are prime numbers.
908 This method uses the algorithm known as the "Sieve of
909 Erathostenes" internally.
913 C<$vec2-E<gt>Reverse($vec1);>
915 This method copies the given vector "C<$vec1>" to
916 the vector "C<$vec2>", thereby reversing the order
919 I.e., the least significant bit of "C<$vec1>" becomes the
920 most significant bit of "C<$vec2>", whereas the most
921 significant bit of "C<$vec1>" becomes the least
922 significant bit of "C<$vec2>", and so forth
923 for all bits in between.
925 Note that in-place processing is also possible, i.e.,
926 "C<$vec1>" and "C<$vec2>" may be identical.
928 (Internally, this is the same as
929 C<$vec1-E<gt>Interval_Reverse(0,$vec1-E<gt>Size()-1);>.)
933 C<$vector-E<gt>Interval_Empty($min,$max);>
935 Clears all bits in the interval C<[$min..$max]> (including both limits)
938 "C<$min>" and "C<$max>" may have the same value; this is the same
939 as clearing a single bit with "C<Bit_Off()>" (but less efficient).
941 Note that C<$vector-E<gt>Interval_Empty(0,$vector-E<gt>Size()-1);>
942 is the same as C<$vector-E<gt>Empty();> (but less efficient).
946 C<$vector-E<gt>Interval_Fill($min,$max);>
948 Sets all bits in the interval C<[$min..$max]> (including both limits)
951 "C<$min>" and "C<$max>" may have the same value; this is the same
952 as setting a single bit with "C<Bit_On()>" (but less efficient).
954 Note that C<$vector-E<gt>Interval_Fill(0,$vector-E<gt>Size()-1);>
955 is the same as C<$vector-E<gt>Fill();> (but less efficient).
959 C<$vector-E<gt>Interval_Flip($min,$max);>
961 Flips (i.e., complements) all bits in the interval C<[$min..$max]>
962 (including both limits) in the given vector.
964 "C<$min>" and "C<$max>" may have the same value; this is the same
965 as flipping a single bit with "C<bit_flip()>" (but less efficient).
967 Note that C<$vector-E<gt>Interval_Flip(0,$vector-E<gt>Size()-1);>
968 is the same as C<$vector-E<gt>Flip();> and
969 C<$vector-E<gt>Complement($vector);>
970 (but less efficient).
974 C<$vector-E<gt>Interval_Reverse($min,$max);>
976 Reverses the order of all bits in the interval C<[$min..$max]>
977 (including both limits) in the given vector.
979 I.e., bits "C<$min>" and "C<$max>" swap places, and so forth
980 for all bits in between.
982 "C<$min>" and "C<$max>" may have the same value; this has no
983 effect whatsoever, though.
987 C<if (($min,$max) = $vector-E<gt>Interval_Scan_inc($start))>
989 Returns the minimum and maximum indices of the next contiguous block
990 of set bits (i.e., bits in the "on" state).
992 The search starts at index "C<$start>" (i.e., C<"$min" E<gt>= "$start">)
993 and proceeds upwards (i.e., C<"$max" E<gt>= "$min">), thus repeatedly
994 increments the search pointer "C<$start>" (internally).
996 Note though that the contents of the variable (or scalar literal value)
997 "C<$start>" is B<NOT> altered. I.e., you have to set it to the desired
998 value yourself prior to each call to "C<Interval_Scan_inc()>" (see also
999 the example given below).
1001 Actually, the bit vector is not searched bit by bit, but one machine
1002 word at a time, in order to speed up execution (which means that this
1003 method is quite efficient).
1005 An empty list is returned if no such block can be found.
1007 Note that a single set bit (surrounded by cleared bits) is a valid
1008 block by this definition. In that case the return values for "C<$min>"
1009 and "C<$max>" are the same.
1014 while (($start < $vector->Size()) &&
1015 (($min,$max) = $vector->Interval_Scan_inc($start)))
1019 # do something with $min and $max
1024 C<if (($min,$max) = $vector-E<gt>Interval_Scan_dec($start))>
1026 Returns the minimum and maximum indices of the next contiguous block
1027 of set bits (i.e., bits in the "on" state).
1029 The search starts at index "C<$start>" (i.e., C<"$max" E<lt>= "$start">)
1030 and proceeds downwards (i.e., C<"$min" E<lt>= "$max">), thus repeatedly
1031 decrements the search pointer "C<$start>" (internally).
1033 Note though that the contents of the variable (or scalar literal value)
1034 "C<$start>" is B<NOT> altered. I.e., you have to set it to the desired
1035 value yourself prior to each call to "C<Interval_Scan_dec()>" (see also
1036 the example given below).
1038 Actually, the bit vector is not searched bit by bit, but one machine
1039 word at a time, in order to speed up execution (which means that this
1040 method is quite efficient).
1042 An empty list is returned if no such block can be found.
1044 Note that a single set bit (surrounded by cleared bits) is a valid
1045 block by this definition. In that case the return values for "C<$min>"
1046 and "C<$max>" are the same.
1050 $start = $vector->Size() - 1;
1051 while (($start >= 0) &&
1052 (($min,$max) = $vector->Interval_Scan_dec($start)))
1056 # do something with $min and $max
1061 C<$vec2-E<gt>Interval_Copy($vec1,$offset2,$offset1,$length);>
1063 This method allows you to copy a stretch of contiguous bits (starting
1064 at any position "C<$offset1>" you choose, with a length of "C<$length>"
1065 bits) from a given "source" bit vector "C<$vec1>" to another position
1066 "C<$offset2>" in a "target" bit vector "C<$vec2>".
1068 Note that the two bit vectors "C<$vec1>" and "C<$vec2>" do B<NOT>
1069 need to have the same (matching) size!
1071 Consequently, any of the two terms "C<$offset1 + $length>" and
1072 "C<$offset2 + $length>" (or both) may exceed the actual length
1073 of its corresponding bit vector ("C<$vec1-E<gt>Size()>" and
1074 "C<$vec2-E<gt>Size()>", respectively).
1076 In such a case, the "C<$length>" parameter is automatically reduced
1077 internally so that both terms above are bounded by the number of bits
1078 of their corresponding bit vector.
1080 This may even result in a length of zero, in which case nothing is
1083 (Of course the value of the "C<$length>" parameter, supplied by you
1084 in the initial method call, may also be zero right from the start!)
1086 Note also that "C<$offset1>" and "C<$offset2>" must lie within the
1087 range "C<0>" and, respectively, "C<$vec1-E<gt>Size()-1>" or
1088 "C<$vec2-E<gt>Size()-1>", or a fatal "offset out of range" error
1091 Note further that "C<$vec1>" and "C<$vec2>" may be identical, i.e.,
1092 you may copy a stretch of contiguous bits from one part of a given
1093 bit vector to another part.
1095 The source and the target interval may even overlap, in which case
1096 the copying is automatically performed in ascending or descending
1097 order (depending on the direction of the copy - downwards or upwards
1098 in the bit vector, respectively) to handle this situation correctly,
1099 i.e., so that no bits are being overwritten before they have been
1104 C<$vec2-E<gt>Interval_Substitute($vec1,$off2,$len2,$off1,$len1);>
1106 This method is (roughly) the same for bit vectors (i.e., arrays
1107 of booleans) as what the "splice" function in Perl is for lists
1108 (i.e., arrays of scalars).
1110 (See L<perlfunc/splice> for more details about this function.)
1112 The method allows you to substitute a stretch of contiguous bits
1113 (defined by a position (offset) "C<$off1>" and a length of "C<$len1>"
1114 bits) from a given "source" bit vector "C<$vec1>" for a different
1115 stretch of contiguous bits (defined by a position (offset) "C<$off2>"
1116 and a length of "C<$len2>" bits) in another, "target" bit vector
1119 Note that the two bit vectors "C<$vec1>" and "C<$vec2>" do B<NOT>
1120 need to have the same (matching) size!
1122 Note further that "C<$off1>" and "C<$off2>" must lie within the
1123 range "C<0>" and, respectively, "C<$vec1-E<gt>Size()>" or
1124 "C<$vec2-E<gt>Size()>", or a fatal "offset out of range" error
1127 Alert readers will have noticed that these upper limits are B<NOT>
1128 "C<$vec1-E<gt>Size()-1>" and "C<$vec2-E<gt>Size()-1>", as they would
1129 be for any other method in this module, but that these offsets may
1130 actually point to one position B<PAST THE END> of the corresponding
1133 This is necessary in order to make it possible to B<APPEND> a given
1134 stretch of bits to the target bit vector instead of B<REPLACING>
1137 For reasons of symmetry and generality, the same applies to the offset
1138 in the source bit vector, even though such an offset (one position past
1139 the end of the bit vector) does not serve any practical purpose there
1140 (but does not cause any harm either).
1142 (Actually this saves you from the need of testing for this special case,
1143 in certain circumstances.)
1145 Note that whenever the term "C<$off1 + $len1>" exceeds the size
1146 "C<$vec1-E<gt>Size()>" of bit vector "C<$vec1>" (or if "C<$off2 + $len2>"
1147 exceeds "C<$vec2-E<gt>Size()>"), the corresponding length ("C<$len1>"
1148 or "C<$len2>", respectively) is automatically reduced internally
1149 so that "C<$off1 + $len1 E<lt>= $vec1-E<gt>Size()>" (and
1150 "C<$off2 + $len2 E<lt>= $vec2-E<gt>Size()>") holds.
1152 (Note that this does B<NOT> alter the intended result, even though
1153 this may seem counter-intuitive at first!)
1155 This may even result in a length ("C<$len1>" or "C<$len2>") of zero.
1157 A length of zero for the interval in the B<SOURCE> bit vector
1158 ("C<$len1 == 0>") means that the indicated stretch of bits in
1159 the target bit vector (starting at position "C<$off2>") is to
1160 be replaced by B<NOTHING>, i.e., is to be B<DELETED>.
1162 A length of zero for the interval in the B<TARGET> bit vector
1163 ("C<$len2> == 0") means that B<NOTHING> is replaced, and that the
1164 stretch of bits from the source bit vector is simply B<INSERTED>
1165 into the target bit vector at the indicated position ("C<$off2>").
1167 If both length parameters are zero, nothing is done at all.
1169 Note that in contrast to any other method in this module (especially
1170 "C<Interval_Copy()>", "C<Insert()>" and "C<Delete()>"), this method
1171 B<IMPLICITLY> and B<AUTOMATICALLY> adapts the length of the resulting
1172 bit vector as needed, as given by
1174 $size = $vec2->Size(); # before
1175 $size += $len1 - $len2; # after
1177 (The only other method in this module that changes the size of a bit
1178 vector is the method "C<Resize()>".)
1180 In other words, replacing a given interval of bits in the target bit
1181 vector with a longer or shorter stretch of bits from the source bit
1182 vector, or simply inserting ("C<$len2 == 0>") a stretch of bits into
1183 or deleting ("C<$len1 == 0>") an interval of bits from the target bit
1184 vector will automatically increase or decrease, respectively, the size
1185 of the target bit vector accordingly.
1187 For the sake of generality, this may even result in a bit vector with
1188 a size of zero (containing no bits at all).
1190 This is also the reason why bit vectors of length zero are permitted
1191 in this module in the first place, starting with version 5.0.
1193 Finally, note that "C<$vec1>" and "C<$vec2>" may be identical, i.e.,
1194 in-place processing is possible.
1196 (If you think about that for a while or if you look at the code,
1197 you will see that this is far from trivial!)
1201 C<if ($vector-E<gt>is_empty())>
1203 Tests whether the given bit vector is empty, i.e., whether B<ALL> of
1204 its bits are cleared (in the "off" state).
1206 In "big integer" arithmetic, this is equivalent to testing whether
1207 the number stored in the bit vector is zero ("C<0>").
1209 Returns "true" ("C<1>") if the bit vector is empty and "false" ("C<0>")
1212 Note that this method also returns "true" ("C<1>") if the given bit
1213 vector has a length of zero, i.e., if it contains no bits at all.
1217 C<if ($vector-E<gt>is_full())>
1219 Tests whether the given bit vector is full, i.e., whether B<ALL> of
1220 its bits are set (in the "on" state).
1222 In "big integer" arithmetic, this is equivalent to testing whether
1223 the number stored in the bit vector is minus one ("-1").
1225 Returns "true" ("C<1>") if the bit vector is full and "false" ("C<0>")
1228 If the given bit vector has a length of zero (i.e., if it contains
1229 no bits at all), this method returns "false" ("C<0>").
1233 C<if ($vec1-E<gt>equal($vec2))>
1235 Tests the two given bit vectors for equality.
1237 Returns "true" ("C<1>") if the two bit vectors are exact
1238 copies of one another and "false" ("C<0>") otherwise.
1242 C<$cmp = $vec1-E<gt>Lexicompare($vec2);>
1244 Compares the two given bit vectors, which are
1245 regarded as B<UNSIGNED> numbers in binary representation.
1247 The method returns "C<-1>" if the first bit vector is smaller
1248 than the second bit vector, "C<0>" if the two bit vectors are
1249 exact copies of one another and "C<1>" if the first bit vector
1250 is greater than the second bit vector.
1254 C<$cmp = $vec1-E<gt>Compare($vec2);>
1256 Compares the two given bit vectors, which are
1257 regarded as B<SIGNED> numbers in binary representation.
1259 The method returns "C<-1>" if the first bit vector is smaller
1260 than the second bit vector, "C<0>" if the two bit vectors are
1261 exact copies of one another and "C<1>" if the first bit vector
1262 is greater than the second bit vector.
1266 C<$string = $vector-E<gt>to_Hex();>
1268 Returns a hexadecimal string representing the given bit vector.
1270 Note that this representation is quite compact, in that it only
1271 needs at most twice the number of bytes needed to store the bit
1272 vector itself, internally.
1274 Note also that since a hexadecimal digit is always worth four bits,
1275 the length of the resulting string is always a multiple of four bits,
1276 regardless of the true length (in bits) of the given bit vector.
1278 Finally, note that the B<LEAST> significant hexadecimal digit is
1279 located at the B<RIGHT> end of the resulting string, and the B<MOST>
1280 significant digit at the B<LEFT> end.
1284 C<$vector-E<gt>from_Hex($string);>
1286 Allows to read in the contents of a bit vector from a hexadecimal
1287 string, such as returned by the method "C<to_Hex()>" (see above).
1289 Remember that the least significant bits are always to the right of a
1290 hexadecimal string, and the most significant bits to the left. Therefore,
1291 the string is actually read in from right to left while the bit vector
1292 is filled accordingly, 4 bits at a time, starting with the least significant
1293 bits and going upward to the most significant bits.
1295 If the given string contains less hexadecimal digits than are needed
1296 to completely fill the given bit vector, the remaining (most significant)
1297 bits are all cleared.
1299 This also means that, even if the given string does not contain enough digits
1300 to completely fill the given bit vector, the previous contents of the
1301 bit vector are erased completely.
1303 If the given string is longer than it needs to fill the given bit vector,
1304 the superfluous characters are simply ignored.
1306 (In fact they are ignored completely - they are not even checked for
1307 proper syntax. See also below for more about that.)
1309 This behaviour is intentional so that you may read in the string
1310 representing one bit vector into another bit vector of different
1311 size, i.e., as much of it as will fit.
1313 If during the process of reading the given string any character is
1314 encountered which is not a hexadecimal digit, a fatal syntax error
1315 ensues ("input string syntax error").
1319 C<$string = $vector-E<gt>to_Bin();>
1321 Returns a binary string representing the given bit vector.
1325 $vector = Bit::Vector->new(8);
1327 $string = $vector->to_Bin();
1328 print "'$string'\n";
1334 (Bits #7, #5, #3 and #2 are set.)
1336 Note that the B<LEAST> significant bit is located at the B<RIGHT>
1337 end of the resulting string, and the B<MOST> significant bit at
1342 C<$vector-E<gt>from_Bin($string);>
1344 This method allows you to read in the contents of a bit vector from a
1345 binary string, such as returned by the method "C<to_Bin()>" (see above).
1347 Note that this method assumes that the B<LEAST> significant bit is located at
1348 the B<RIGHT> end of the binary string, and the B<MOST> significant bit at the
1349 B<LEFT> end. Therefore, the string is actually read in from right to left
1350 while the bit vector is filled accordingly, one bit at a time, starting with
1351 the least significant bit and going upward to the most significant bit.
1353 If the given string contains less binary digits ("C<0>" and "C<1>") than are
1354 needed to completely fill the given bit vector, the remaining (most significant)
1355 bits are all cleared.
1357 This also means that, even if the given string does not contain enough digits
1358 to completely fill the given bit vector, the previous contents of the
1359 bit vector are erased completely.
1361 If the given string is longer than it needs to fill the given bit vector,
1362 the superfluous characters are simply ignored.
1364 (In fact they are ignored completely - they are not even checked for
1365 proper syntax. See also below for more about that.)
1367 This behaviour is intentional so that you may read in the string
1368 representing one bit vector into another bit vector of different
1369 size, i.e., as much of it as will fit.
1371 If during the process of reading the given string any character is
1372 encountered which is not either "C<0>" or "C<1>", a fatal syntax error
1373 ensues ("input string syntax error").
1377 C<$string = $vector-E<gt>to_Dec();>
1379 This method returns a string representing the contents of the given bit
1380 vector converted to decimal (base C<10>).
1382 Note that this method assumes the given bit vector to be B<SIGNED> (and
1383 to contain a number in two's complement binary representation).
1385 Consequently, whenever the most significant bit of the given bit vector
1386 is set, the number stored in it is regarded as being B<NEGATIVE>.
1388 The resulting string can be fed into "C<from_Dec()>" (see below) in order
1389 to copy the contents of this bit vector to another one (or to restore the
1390 contents of this one). This is not advisable, though, since this would be
1391 very inefficient (there are much more efficient methods for storing and
1392 copying bit vectors in this module).
1394 Note that such conversion from binary to decimal is inherently slow
1395 since the bit vector has to be repeatedly divided by C<10> with remainder
1396 until the quotient becomes C<0> (each remainder in turn represents a single
1397 decimal digit of the resulting string).
1399 This is also true for the implementation of this method in this module,
1400 even though a considerable effort has been made to speed it up: instead of
1401 repeatedly dividing by C<10>, the bit vector is repeatedly divided by the
1402 largest power of C<10> that will fit into a machine word. The remainder is
1403 then repeatedly divided by C<10> using only machine word arithmetics, which
1404 is much faster than dividing the whole bit vector ("divide and rule" principle).
1406 According to my own measurements, this resulted in an 8-fold speed increase
1407 over the straightforward approach.
1409 Still, conversion to decimal should be used only where absolutely necessary.
1411 Keep the resulting string stored in some variable if you need it again,
1412 instead of converting the bit vector all over again.
1414 Beware that if you set the configuration for overloaded operators to
1415 "output=decimal", this method will be called for every bit vector
1416 enclosed in double quotes!
1420 C<$vector-E<gt>from_Dec($string);>
1422 This method allows you to convert a given decimal number, which may be
1423 positive or negative, into two's complement binary representation, which
1424 is then stored in the given bit vector.
1426 The decimal number should always be provided as a string, to avoid possible
1427 truncation (due to the limited precision of integers in Perl) or formatting
1428 (due to Perl's use of scientific notation for large numbers), which would
1431 If the binary representation of the given decimal number is too big to fit
1432 into the given bit vector (if the given bit vector does not contain enough
1433 bits to hold it), a fatal "numeric overflow error" occurs.
1435 If the input string contains other characters than decimal digits (C<0-9>)
1436 and an optional leading sign ("C<+>" or "C<->"), a fatal "input string
1437 syntax error" occurs.
1439 Beware that large positive numbers which cause the most significant bit to
1440 be set (e.g. "255" in a bit vector with 8 bits) will be printed as negative
1441 numbers when converted back to decimal using the method "to_Dec()" (e.g.
1442 "-1", in our example), because numbers with the most significant bit set
1443 are considered to be negative in two's complement binary representation.
1445 Note also that while it is possible to thusly enter negative numbers as
1446 large positive numbers (e.g. "255" for "-1" in a bit vector with 8 bits),
1447 the contrary isn't, i.e., you cannot enter "-255" for "+1", in our example.
1448 A fatal "numeric overflow error" will occur if you try to do so.
1450 If possible program abortion is unwanted or intolerable, use
1451 "C<eval>", like this:
1453 eval { $vector->from_Dec("1152921504606846976"); };
1459 There are four possible error messages:
1461 if ($@ =~ /item is not a string/)
1463 if ($@ =~ /input string syntax error/)
1465 if ($@ =~ /numeric overflow error/)
1467 if ($@ =~ /unable to allocate memory/)
1469 Note that the conversion from decimal to binary is costly in terms of
1470 processing time, since a lot of multiplications have to be carried out
1471 (in principle, each decimal digit must be multiplied with the binary
1472 representation of the power of C<10> corresponding to its position in
1473 the decimal number, i.e., 1, 10, 100, 1000, 10000 and so on).
1475 This is not as time consuming as the opposite conversion, from binary
1476 to decimal (where successive divisions have to be carried out, which
1477 are even more expensive than multiplications), but still noticeable.
1479 Again (as in the case of "C<to_Dec()>"), the implementation of this
1480 method in this module uses the principle of "divide and rule" in order
1481 to speed up the conversion, i.e., as many decimal digits as possible
1482 are first accumulated (converted) in a machine word and only then
1483 stored in the given bit vector.
1485 Even so, use this method only where absolutely necessary if speed is
1486 an important consideration in your application.
1488 Beware that if you set the configuration for overloaded operators to
1489 "input=decimal", this method will be called for every scalar operand
1494 C<$string = $vector-E<gt>to_Enum();>
1496 Converts the given bit vector or set into an enumeration of single
1497 indices and ranges of indices (".newsrc" style), representing the
1498 bits that are set ("C<1>") in the bit vector.
1502 $vector = Bit::Vector->new(20);
1505 $vector->Bit_On(11);
1506 $vector->Interval_Fill(5,7);
1507 $vector->Interval_Fill(13,19);
1508 print "'", $vector->to_Enum(), "'\n";
1514 If the given bit vector is empty, the resulting string will
1517 Note, by the way, that the above example can also be written
1518 a little handier, perhaps, as follows:
1520 Bit::Vector->Configuration("out=enum");
1521 $vector = Bit::Vector->new(20);
1522 $vector->Index_List_Store(2,3,5,6,7,11,13,14,15,16,17,18,19);
1523 print "'$vector'\n";
1527 C<$vector-E<gt>from_Enum($string);>
1529 This method first empties the given bit vector and then tries to
1530 set the bits and ranges of bits specified in the given string.
1532 The string "C<$string>" must only contain unsigned integers
1533 or ranges of integers (two unsigned integers separated by a
1534 dash "-"), separated by commas (",").
1536 All other characters are disallowed (including white space!)
1537 and will lead to a fatal "input string syntax error".
1539 In each range, the first integer (the lower limit of the range)
1540 must always be less than or equal to the second integer (the
1541 upper limit), or a fatal "minimum > maximum index" error occurs.
1543 All integers must lie in the permitted range for the given
1544 bit vector, i.e., they must lie between "C<0>" and
1545 "C<$vector-E<gt>Size()-1>".
1547 If this condition is not met, a fatal "index out of range"
1550 If possible program abortion is unwanted or intolerable, use
1551 "C<eval>", like this:
1553 eval { $vector->from_Enum("2,3,5-7,11,13-19"); };
1559 There are four possible error messages:
1561 if ($@ =~ /item is not a string/)
1563 if ($@ =~ /input string syntax error/)
1565 if ($@ =~ /index out of range/)
1567 if ($@ =~ /minimum > maximum index/)
1569 Note that the order of the indices and ranges is irrelevant,
1572 eval { $vector->from_Enum("11,5-7,3,13-19,2"); };
1574 results in the same vector as in the example above.
1576 Ranges and indices may also overlap.
1578 This is because each (single) index in the string is passed
1579 to the method "C<Bit_On()>", internally, and each range to
1580 the method "C<Interval_Fill()>".
1582 This means that the resulting bit vector is just the union
1583 of all the indices and ranges specified in the given string.
1587 C<$vector-E<gt>Bit_Off($index);>
1589 Clears the bit with index "C<$index>" in the given vector.
1593 C<$vector-E<gt>Bit_On($index);>
1595 Sets the bit with index "C<$index>" in the given vector.
1599 C<$vector-E<gt>bit_flip($index)>
1601 Flips (i.e., complements) the bit with index "C<$index>"
1602 in the given vector.
1604 Moreover, this method returns the B<NEW> state of the
1605 bit in question, i.e., it returns "C<0>" if the bit is
1606 cleared or "C<1>" if the bit is set (B<AFTER> flipping it).
1610 C<if ($vector-E<gt>bit_test($index))>
1612 C<if ($vector-E<gt>contains($index))>
1614 Returns the current state of the bit with index "C<$index>"
1615 in the given vector, i.e., returns "C<0>" if it is cleared
1616 (in the "off" state) or "C<1>" if it is set (in the "on" state).
1620 C<$vector-E<gt>Bit_Copy($index,$bit);>
1622 Sets the bit with index "C<$index>" in the given vector either
1623 to "C<0>" or "C<1>" depending on the boolean value "C<$bit>".
1627 C<$vector-E<gt>LSB($bit);>
1629 Allows you to set the least significant bit in the given bit
1630 vector to the value given by the boolean parameter "C<$bit>".
1632 This is a (faster) shortcut for "C<$vector-E<gt>Bit_Copy(0,$bit);>".
1636 C<$vector-E<gt>MSB($bit);>
1638 Allows you to set the most significant bit in the given bit
1639 vector to the value given by the boolean parameter "C<$bit>".
1641 This is a (faster) shortcut for
1642 "C<$vector-E<gt>Bit_Copy($vector-E<gt>Size()-1,$bit);>".
1646 C<$bit = $vector-E<gt>lsb();>
1648 Returns the least significant bit of the given bit vector.
1650 This is a (faster) shortcut for "C<$bit = $vector-E<gt>bit_test(0);>".
1654 C<$bit = $vector-E<gt>msb();>
1656 Returns the most significant bit of the given bit vector.
1658 This is a (faster) shortcut for
1659 "C<$bit = $vector-E<gt>bit_test($vector-E<gt>Size()-1);>".
1663 C<$carry_out = $vector-E<gt>rotate_left();>
1665 carry MSB vector: LSB
1667 +---+ +---+---+---+--- ---+---+---+---+
1668 | | <---+--- | | | | ... | | | | <---+
1669 +---+ | +---+---+---+--- ---+---+---+---+ |
1671 +------------------------------------------------+
1673 The least significant bit (LSB) is the bit with index "C<0>", the most
1674 significant bit (MSB) is the bit with index "C<$vector-E<gt>Size()-1>".
1678 C<$carry_out = $vector-E<gt>rotate_right();>
1680 MSB vector: LSB carry
1682 +---+---+---+--- ---+---+---+---+ +---+
1683 +---> | | | | ... | | | | ---+---> | |
1684 | +---+---+---+--- ---+---+---+---+ | +---+
1686 +------------------------------------------------+
1688 The least significant bit (LSB) is the bit with index "C<0>", the most
1689 significant bit (MSB) is the bit with index "C<$vector-E<gt>Size()-1>".
1693 C<$carry_out = $vector-E<gt>shift_left($carry_in);>
1695 carry MSB vector: LSB carry
1697 +---+ +---+---+---+--- ---+---+---+---+ +---+
1698 | | <--- | | | | ... | | | | <--- | |
1699 +---+ +---+---+---+--- ---+---+---+---+ +---+
1701 The least significant bit (LSB) is the bit with index "C<0>", the most
1702 significant bit (MSB) is the bit with index "C<$vector-E<gt>Size()-1>".
1706 C<$carry_out = $vector-E<gt>shift_right($carry_in);>
1708 carry MSB vector: LSB carry
1710 +---+ +---+---+---+--- ---+---+---+---+ +---+
1711 | | ---> | | | | ... | | | | ---> | |
1712 +---+ +---+---+---+--- ---+---+---+---+ +---+
1714 The least significant bit (LSB) is the bit with index "C<0>", the most
1715 significant bit (MSB) is the bit with index "C<$vector-E<gt>Size()-1>".
1719 C<$vector-E<gt>Move_Left($bits);>
1721 Shifts the given bit vector left by "C<$bits>" bits, i.e., inserts "C<$bits>"
1722 new bits at the lower end (least significant bit) of the bit vector, moving
1723 all other bits up by "C<$bits>" places, thereby losing the "C<$bits>" most
1726 The inserted new bits are all cleared (set to the "off" state).
1728 This method does nothing if "C<$bits>" is equal to zero.
1730 Beware that the whole bit vector is cleared B<WITHOUT WARNING> if
1731 "C<$bits>" is greater than or equal to the size of the given bit vector!
1733 In fact this method is equivalent to
1735 for ( $i = 0; $i < $bits; $i++ ) { $vector->shift_left(0); }
1737 except that it is much more efficient (for "C<$bits>" greater than or
1738 equal to the number of bits in a machine word on your system) than
1739 this straightforward approach.
1743 C<$vector-E<gt>Move_Right($bits);>
1745 Shifts the given bit vector right by "C<$bits>" bits, i.e., deletes the
1746 "C<$bits>" least significant bits of the bit vector, moving all other bits
1747 down by "C<$bits>" places, thereby creating "C<$bits>" new bits at the upper
1748 end (most significant bit) of the bit vector.
1750 These new bits are all cleared (set to the "off" state).
1752 This method does nothing if "C<$bits>" is equal to zero.
1754 Beware that the whole bit vector is cleared B<WITHOUT WARNING> if
1755 "C<$bits>" is greater than or equal to the size of the given bit vector!
1757 In fact this method is equivalent to
1759 for ( $i = 0; $i < $bits; $i++ ) { $vector->shift_right(0); }
1761 except that it is much more efficient (for "C<$bits>" greater than or
1762 equal to the number of bits in a machine word on your system) than
1763 this straightforward approach.
1767 C<$vector-E<gt>Insert($offset,$bits);>
1769 This method inserts "C<$bits>" fresh new bits at position "C<$offset>"
1770 in the given bit vector.
1772 The "C<$bits>" most significant bits are lost, and all bits starting
1773 with bit number "C<$offset>" up to and including bit number
1774 "C<$vector-E<gt>Size()-$bits-1>" are moved up by "C<$bits>" places.
1776 The now vacant "C<$bits>" bits starting at bit number "C<$offset>"
1777 (up to and including bit number "C<$offset+$bits-1>") are then set
1780 Note that this method does B<NOT> increase the size of the given bit
1781 vector, i.e., the bit vector is B<NOT> extended at its upper end to
1782 "rescue" the "C<$bits>" uppermost (most significant) bits - instead,
1783 these bits are lost forever.
1785 If you don't want this to happen, you have to increase the size of the
1786 given bit vector B<EXPLICITLY> and B<BEFORE> you perform the "Insert"
1787 operation, with a statement such as the following:
1789 $vector->Resize($vector->Size() + $bits);
1791 Or use the method "C<Interval_Substitute()>" instead of "C<Insert()>",
1792 which performs automatic growing and shrinking of its target bit vector.
1794 Note also that "C<$offset>" must lie in the permitted range between
1795 "C<0>" and "C<$vector-E<gt>Size()-1>", or a fatal "offset out of range"
1798 If the term "C<$offset + $bits>" exceeds "C<$vector-E<gt>Size()-1>",
1799 all the bits starting with bit number "C<$offset>" up to bit number
1800 "C<$vector-E<gt>Size()-1>" are simply cleared.
1804 C<$vector-E<gt>Delete($offset,$bits);>
1806 This method deletes, i.e., removes the bits starting at position
1807 "C<$offset>" up to and including bit number "C<$offset+$bits-1>"
1808 from the given bit vector.
1810 The remaining uppermost bits (starting at position "C<$offset+$bits>"
1811 up to and including bit number "C<$vector-E<gt>Size()-1>") are moved
1812 down by "C<$bits>" places.
1814 The now vacant uppermost (most significant) "C<$bits>" bits are then
1815 set to zero (cleared).
1817 Note that this method does B<NOT> decrease the size of the given bit
1818 vector, i.e., the bit vector is B<NOT> clipped at its upper end to
1819 "get rid of" the vacant "C<$bits>" uppermost bits.
1821 If you don't want this, i.e., if you want the bit vector to shrink
1822 accordingly, you have to do so B<EXPLICITLY> and B<AFTER> the "Delete"
1823 operation, with a couple of statements such as these:
1825 $size = $vector->Size();
1826 if ($bits > $size) { $bits = $size; }
1827 $vector->Resize($size - $bits);
1829 Or use the method "C<Interval_Substitute()>" instead of "C<Delete()>",
1830 which performs automatic growing and shrinking of its target bit vector.
1832 Note also that "C<$offset>" must lie in the permitted range between
1833 "C<0>" and "C<$vector-E<gt>Size()-1>", or a fatal "offset out of range"
1836 If the term "C<$offset + $bits>" exceeds "C<$vector-E<gt>Size()-1>",
1837 all the bits starting with bit number "C<$offset>" up to bit number
1838 "C<$vector-E<gt>Size()-1>" are simply cleared.
1842 C<$carry = $vector-E<gt>increment();>
1844 This method increments the given bit vector.
1846 Note that this method regards bit vectors as being unsigned,
1847 i.e., the largest possible positive number is directly
1848 followed by the smallest possible (or greatest possible,
1849 speaking in absolute terms) negative number:
1851 before: 2 ^ (b-1) - 1 (= "0111...1111")
1852 after: 2 ^ (b-1) (= "1000...0000")
1854 where "C<b>" is the number of bits of the given bit vector.
1856 The method returns "false" ("C<0>") in all cases except when a
1857 carry over occurs (in which case it returns "true", i.e., "C<1>"),
1858 which happens when the number "1111...1111" is incremented,
1859 which gives "0000...0000" plus a carry over to the next higher
1862 This can be used for the terminating condition of a "while" loop,
1863 for instance, in order to cycle through all possible values the
1864 bit vector can assume.
1868 C<$carry = $vector-E<gt>decrement();>
1870 This method decrements the given bit vector.
1872 Note that this method regards bit vectors as being unsigned,
1873 i.e., the smallest possible (or greatest possible, speaking
1874 in absolute terms) negative number is directly followed by
1875 the largest possible positive number:
1877 before: 2 ^ (b-1) (= "1000...0000")
1878 after: 2 ^ (b-1) - 1 (= "0111...1111")
1880 where "C<b>" is the number of bits of the given bit vector.
1882 The method returns "false" ("C<0>") in all cases except when a
1883 carry over occurs (in which case it returns "true", i.e., "C<1>"),
1884 which happens when the number "0000...0000" is decremented,
1885 which gives "1111...1111" minus a carry over to the next higher
1888 This can be used for the terminating condition of a "while" loop,
1889 for instance, in order to cycle through all possible values the
1890 bit vector can assume.
1894 C<$overflow = $vec2-E<gt>inc($vec1);>
1896 This method copies the contents of bit vector "C<$vec1>" to bit
1897 vector "C<$vec2>" and increments the copy (not the original).
1899 If by incrementing the number its sign becomes invalid, the return
1900 value ("overflow" flag) will be true ("C<1>"), or false ("C<0>")
1901 if not. (See the description of the method "add()" below for
1902 a more in-depth explanation of what "overflow" means).
1904 Note that in-place operation is also possible, i.e., "C<$vec1>"
1905 and "C<$vec2>" may be identical.
1909 C<$overflow = $vec2-E<gt>dec($vec1);>
1911 This method copies the contents of bit vector "C<$vec1>" to bit
1912 vector "C<$vec2>" and decrements the copy (not the original).
1914 If by decrementing the number its sign becomes invalid, the return
1915 value ("overflow" flag) will be true ("C<1>"), or false ("C<0>")
1916 if not. (See the description of the method "subtract()" below
1917 for a more in-depth explanation of what "overflow" means).
1919 Note that in-place operation is also possible, i.e., "C<$vec1>"
1920 and "C<$vec2>" may be identical.
1924 C<$carry = $vec3-E<gt>add($vec1,$vec2,$carry);>
1926 C<($carry,$overflow) = $vec3-E<gt>add($vec1,$vec2,$carry);>
1928 This method adds the two numbers contained in bit vector "C<$vec1>"
1929 and "C<$vec2>" with carry "C<$carry>" and stores the result in
1930 bit vector "C<$vec3>".
1933 $vec3 = $vec1 + $vec2 + $carry
1935 Note that the "C<$carry>" parameter is a boolean value, i.e.,
1936 only its least significant bit is taken into account. (Think of
1937 it as though "C<$carry &= 1;>" was always executed internally.)
1939 In scalar context, the method returns a boolean value which
1940 indicates if a carry over (to the next higher bit position)
1941 has occured. In list context, the method returns the carry
1942 and the overflow flag (in this order).
1944 The overflow flag is true ("C<1>") if the sign (i.e., the most
1945 significant bit) of the result is wrong. This can happen when
1946 adding two very large positive numbers or when adding two (by
1947 their absolute value) very large negative numbers. See also
1950 The carry in- and output is needed mainly for cascading, i.e.,
1951 to add numbers that are fragmented into several pieces.
1957 for ( $i = 0; $i < $n; $i++ )
1959 $a[$i] = Bit::Vector->new($bits);
1960 $b[$i] = Bit::Vector->new($bits);
1961 $c[$i] = Bit::Vector->new($bits);
1966 # $a[ 0 ] is low order part,
1967 # $a[$n-1] is high order part,
1973 for ( $i = 0; $i < $n; $i++ )
1975 $carry = $c[$i]->add($a[$i],$b[$i],$carry);
1978 Note that it makes no difference to this method whether the numbers
1979 in "C<$vec1>" and "C<$vec2>" are unsigned or signed (i.e., in two's
1980 complement binary representation).
1982 Note however that the return value (carry flag) is not meaningful
1983 when the numbers are B<SIGNED>.
1985 Moreover, when the numbers are signed, a special type of error can
1986 occur which is commonly called an "overflow error".
1988 An overflow error occurs when the sign of the result (its most
1989 significant bit) is flipped (i.e., falsified) by a carry over
1990 from the next-lower bit position ("MSB-1").
1992 In fact matters are a bit more complicated than that: the overflow
1993 flag is set to "true" whenever there is a carry over from bit
1994 position MSB-1 to the most significant bit (MSB) but no carry
1995 over from the MSB to the output carry flag, or vice-versa, i.e.,
1996 when there is no carry over from bit position MSB-1 to the most
1997 significant bit (MSB) but a carry over to the output carry flag.
1999 Thus the overflow flag is the result of an exclusive-or operation
2000 between incoming and outgoing carry over at the most significant
2005 C<$carry = $vec3-E<gt>subtract($vec1,$vec2,$carry);>
2007 C<($carry,$overflow) = $vec3-E<gt>subtract($vec1,$vec2,$carry);>
2009 This method subtracts the two numbers contained in bit vector
2010 "C<$vec1>" and "C<$vec2>" with carry "C<$carry>" and stores the
2011 result in bit vector "C<$vec3>".
2014 $vec3 = $vec1 - $vec2 - $carry
2016 Note that the "C<$carry>" parameter is a boolean value, i.e.,
2017 only its least significant bit is taken into account. (Think of
2018 it as though "C<$carry &= 1;>" was always executed internally.)
2020 In scalar context, the method returns a boolean value which
2021 indicates if a carry over (to the next higher bit position)
2022 has occured. In list context, the method returns the carry
2023 and the overflow flag (in this order).
2025 The overflow flag is true ("C<1>") if the sign (i.e., the most
2026 significant bit) of the result is wrong. This can happen when
2027 subtracting a very large negative number from a very large
2028 positive number or vice-versa. See also further below.
2030 The carry in- and output is needed mainly for cascading, i.e.,
2031 to subtract numbers that are fragmented into several pieces.
2037 for ( $i = 0; $i < $n; $i++ )
2039 $a[$i] = Bit::Vector->new($bits);
2040 $b[$i] = Bit::Vector->new($bits);
2041 $c[$i] = Bit::Vector->new($bits);
2046 # $a[ 0 ] is low order part,
2047 # $a[$n-1] is high order part,
2053 for ( $i = 0; $i < $n; $i++ )
2055 $carry = $c[$i]->subtract($a[$i],$b[$i],$carry);
2058 Note that it makes no difference to this method whether the numbers
2059 in "C<$vec1>" and "C<$vec2>" are unsigned or signed (i.e., in two's
2060 complement binary representation).
2062 Note however that the return value (carry flag) is not meaningful
2063 when the numbers are B<SIGNED>.
2065 Moreover, when the numbers are signed, a special type of error can
2066 occur which is commonly called an "overflow error".
2068 An overflow error occurs when the sign of the result (its most
2069 significant bit) is flipped (i.e., falsified) by a carry over
2070 from the next-lower bit position ("MSB-1").
2072 In fact matters are a bit more complicated than that: the overflow
2073 flag is set to "true" whenever there is a carry over from bit
2074 position MSB-1 to the most significant bit (MSB) but no carry
2075 over from the MSB to the output carry flag, or vice-versa, i.e.,
2076 when there is no carry over from bit position MSB-1 to the most
2077 significant bit (MSB) but a carry over to the output carry flag.
2079 Thus the overflow flag is the result of an exclusive-or operation
2080 between incoming and outgoing carry over at the most significant
2085 C<$vec2-E<gt>Neg($vec1);>
2087 C<$vec2-E<gt>Negate($vec1);>
2089 This method calculates the two's complement of the number in bit
2090 vector "C<$vec1>" and stores the result in bit vector "C<$vec2>".
2092 Calculating the two's complement of a given number in binary representation
2093 consists of inverting all bits and incrementing the result by one.
2095 This is the same as changing the sign of the given number from "C<+>" to
2096 "C<->" or vice-versa. In other words, applying this method twice on a given
2097 number yields the original number again.
2099 Note that in-place processing is also possible, i.e., "C<$vec1>" and
2100 "C<$vec2>" may be identical.
2102 Most importantly, beware that this method produces a counter-intuitive
2103 result if the number contained in bit vector "C<$vec1>" is C<2 ^ (n-1)>
2104 (i.e., "1000...0000"), where "C<n>" is the number of bits the given bit
2105 vector contains: The negated value of this number is the number itself!
2109 C<$vec2-E<gt>Abs($vec1);>
2111 C<$vec2-E<gt>Absolute($vec1);>
2113 Depending on the sign (i.e., the most significant bit) of the number in
2114 bit vector "C<$vec1>", the contents of bit vector "C<$vec1>" are copied
2115 to bit vector "C<$vec2>" either with the method "C<Copy()>" (if the number
2116 in bit vector "C<$vec1>" is positive), or with "C<Negate()>" (if the number
2117 in bit vector "C<$vec1>" is negative).
2119 In other words, this method calculates the absolute value of the number
2120 in bit vector "C<$vec1>" and stores the result in bit vector "C<$vec2>".
2122 Note that in-place processing is also possible, i.e., "C<$vec1>" and
2123 "C<$vec2>" may be identical.
2125 Most importantly, beware that this method produces a counter-intuitive
2126 result if the number contained in bit vector "C<$vec1>" is C<2 ^ (n-1)>
2127 (i.e., "1000...0000"), where "C<n>" is the number of bits the given bit
2128 vector contains: The absolute value of this number is the number itself,
2129 even though this number is still negative by definition (the most
2130 significant bit is still set)!
2134 C<$sign = $vector-E<gt>Sign();>
2136 This method returns "C<0>" if all bits in the given bit vector are cleared,
2137 i.e., if the given bit vector contains the number "C<0>", or if the given
2138 bit vector has a length of zero (contains no bits at all).
2140 If not all bits are cleared, this method returns "C<-1>" if the most
2141 significant bit is set (i.e., if the bit vector contains a negative
2142 number), or "C<1>" otherwise (i.e., if the bit vector contains a
2147 C<$vec3-E<gt>Multiply($vec1,$vec2);>
2149 This method multiplies the two numbers contained in bit vector "C<$vec1>"
2150 and "C<$vec2>" and stores the result in bit vector "C<$vec3>".
2152 Note that this method regards its arguments as B<SIGNED>.
2154 If you want to make sure that a large number can never be treated as being
2155 negative by mistake, make your bit vectors at least one bit longer than the
2156 largest number you wish to represent, right from the start, or proceed as
2159 $msb1 = $vec1->msb();
2160 $msb2 = $vec2->msb();
2161 $vec1->Resize($vec1->Size()+1);
2162 $vec2->Resize($vec2->Size()+1);
2163 $vec3->Resize($vec3->Size()+1);
2166 $vec3->Multiply($vec1,$vec2);
2168 Note also that all three bit vector arguments must in principle obey the
2169 rule of matching sizes, but that the bit vector "C<$vec3>" may be larger
2170 than the two factors "C<$vec1>" and "C<$vec2>".
2172 In fact multiplying two binary numbers with "C<n>" bits may yield a result
2173 which is at most "C<2n>" bits long.
2175 Therefore, it is usually a good idea to let bit vector "C<$vec3>" have
2176 twice the size of bit vector "C<$vec1>" and "C<$vec2>", unless you are
2177 absolutely sure that the result will fit into a bit vector of the same
2178 size as the two factors.
2180 If you are wrong, a fatal "numeric overflow error" will occur.
2182 Finally, note that in-place processing is possible, i.e., "C<$vec3>"
2183 may be identical with "C<$vec1>" or "C<$vec2>", or both.
2187 C<$quot-E<gt>Divide($vec1,$vec2,$rest);>
2189 This method divides the two numbers contained in bit vector "C<$vec1>"
2190 and "C<$vec2>" and stores the quotient in bit vector "C<$quot>" and
2191 the remainder in bit vector "C<$rest>".
2194 $quot = $vec1 / $vec2; # div
2195 $rest = $vec1 % $vec2; # mod
2197 Therefore, "C<$quot>" and "C<$rest>" must be two B<DISTINCT> bit vectors,
2198 or a fatal "result vector(s) must be distinct" error will occur.
2200 Note also that a fatal "division by zero error" will occur if "C<$vec2>"
2203 Note further that this method regards its arguments as B<SIGNED>.
2205 If you want to make sure that a large number can never be treated as being
2206 negative by mistake, make your bit vectors at least one bit longer than the
2207 largest number you wish to represent, right from the start, or proceed as
2210 $msb1 = $vec1->msb();
2211 $msb2 = $vec2->msb();
2212 $vec1->Resize($vec1->Size()+1);
2213 $vec2->Resize($vec2->Size()+1);
2214 $quot->Resize($quot->Size()+1);
2215 $rest->Resize($rest->Size()+1);
2218 $quot->Divide($vec1,$vec2,$rest);
2220 Finally, note that in-place processing is possible, i.e., "C<$quot>"
2221 may be identical with "C<$vec1>" or "C<$vec2>" or both, and "C<$rest>"
2222 may also be identical with "C<$vec1>" or "C<$vec2>" or both, as long
2223 as "C<$quot>" and "C<$rest>" are distinct. (!)
2227 C<$vecgcd-E<gt>GCD($veca,$vecb);>
2229 This method calculates the "Greatest Common Divisor" of the two numbers
2230 contained in bit vector "C<$veca>" and "C<$vecb>" and stores the result
2231 in bit vector "C<$vecgcd>".
2233 The method uses Euklid's algorithm internally:
2235 int GCD(int a, int b)
2241 t = a % b; /* = remainder of (a div b) */
2248 Note that C<GCD(z,0) == GCD(0,z) == z>.
2252 C<$vecgcd-E<gt>GCD($vecx,$vecy,$veca,$vecb);>
2254 This variant of the "GCD" method calculates the "Greatest Common Divisor"
2255 of the two numbers contained in bit vector "C<$veca>" and "C<$vecb>" and
2256 stores the result in bit vector "C<$vecgcd>".
2258 Moreover, it determines the two factors which are necessary in order to
2259 represent the greatest common divisor as a linear combination of its two
2260 arguments, i.e., the two factors C<"x"> and C<"y"> so that
2261 C<GCD(a,b) == x * a + y * b>, and stores them in bit vector "C<$vecx>"
2262 and "C<$vecy>", respectively.
2269 GCD( 2322, 654 ) == 6
2274 20 * 2322 - 71 * 654 == 6
2276 Please see http://www.cut-the-knot.org/blue/extension.shtml
2277 for an explanation of how this extension of Euklid's algorithm works.
2281 C<$vec3-E<gt>Power($vec1,$vec2);>
2283 This method calculates the exponentiation of base "C<$vec1>" elevated to
2284 the "C<$vec2>" power, i.e., "C<$vec1 ** $vec2>", and stores the result
2285 in bit vector "C<$vec3>".
2287 The method uses an efficient divide-and-conquer algorithm:
2289 Suppose the exponent is (decimal) 13, for example. The binary
2290 representation of this exponent is "1101".
2292 This means we want to calculate
2294 $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 *
2295 $vec1 * $vec1 * $vec1 * $vec1 *
2298 That is, "C<$vec1>" multiplied with itself 13 times. The grouping
2299 into lines above is no coincidence. The first line comprises 8
2300 factors, the second contains 4, and the last line just one. This
2301 just happens to be the binary representation of 13. C<;-)>
2303 We then calculate a series of squares (of squares of squares...) of
2307 $power[1] = $vec1 * $vec1;
2308 $power[2] = $power[1] * $power[1];
2309 $power[3] = $power[2] * $power[2];
2312 To calculate the power of our example, we simply initialize our result
2313 with 1 and consecutively multiply it with the items of the series of
2314 powers we just calculated, if the corresponding bit of the binary
2315 representation of the exponent is set:
2318 $result *= $power[0] if ($vec2 & 1);
2319 $result *= $power[1] if ($vec2 & 2);
2320 $result *= $power[2] if ($vec2 & 4);
2321 $result *= $power[3] if ($vec2 & 8);
2324 The bit vector "C<$vec3>" must be of the same size as the base
2325 "C<$vec1>" or greater. "C<$vec3>" and "C<$vec1>" may be the same
2326 vector (i.e., in-place calculation as in "C<$vec1 **= $vec2;>" is
2327 possible), but "C<$vec3>" and "C<$vec2>" must be distinct. Finally,
2328 the exponent "C<$vec2>" must be positive. A fatal error occurs if
2329 any of these conditions is not met.
2333 C<$vector-E<gt>Block_Store($buffer);>
2335 This method allows you to load the contents of a given bit vector in
2338 This is useful when you store the contents of a bit vector in a file,
2339 for instance (using method "C<Block_Read()>"), and when you want to
2340 restore the previously saved bit vector.
2342 For this, "C<$buffer>" B<MUST> be a string (B<NO> automatic conversion
2343 from numeric to string is provided here as would normally in Perl!)
2344 containing the bit vector in "low order byte first" order.
2346 If the given string is shorter than what is needed to completely fill
2347 the given bit vector, the remaining (most significant) bytes of the
2348 bit vector are filled with zeros, i.e., the previous contents of the
2349 bit vector are always erased completely.
2351 If the given string is longer than what is needed to completely fill
2352 the given bit vector, the superfluous bytes are simply ignored.
2354 See L<perlfunc/sysread> for how to read in the contents of "C<$buffer>"
2355 from a file prior to passing it to this method.
2359 C<$buffer = $vector-E<gt>Block_Read();>
2361 This method allows you to export the contents of a given bit vector in
2364 This is useful when you want to save the contents of a bit vector for
2365 later, for instance in a file.
2367 The advantage of this method is that it allows you to do so in the
2368 compactest possible format, in binary.
2370 The method returns a Perl string which contains an exact copy of the
2371 contents of the given bit vector in "low order byte first" order.
2373 See L<perlfunc/syswrite> for how to write the data from this string
2378 C<$size = $vector-E<gt>Word_Size();>
2380 Each bit vector is internally organized as an array of machine words.
2382 The methods whose names begin with "Word_" allow you to access this
2383 internal array of machine words.
2385 Note that because the size of a machine word may vary from system to
2386 system, these methods are inherently B<MACHINE-DEPENDENT>!
2388 Therefore, B<DO NOT USE> these methods unless you are absolutely certain
2389 that portability of your code is not an issue!
2391 You have been warned!
2393 To be machine-independent, use the methods whose names begin with "C<Chunk_>"
2394 instead, with chunk sizes no greater than 32 bits.
2396 The method "C<Word_Size()>" returns the number of machine words that the
2397 internal array of words of the given bit vector contains.
2399 This is similar in function to the term "C<scalar(@array)>" for a Perl array.
2403 C<$vector-E<gt>Word_Store($offset,$word);>
2405 This method allows you to store a given value "C<$word>" at a given
2406 position "C<$offset>" in the internal array of words of the given
2409 Note that "C<$offset>" must lie in the permitted range between "C<0>"
2410 and "C<$vector-E<gt>Word_Size()-1>", or a fatal "offset out of range"
2413 This method is similar in function to the expression
2414 "C<$array[$offset] = $word;>" for a Perl array.
2418 C<$word = $vector-E<gt>Word_Read($offset);>
2420 This method allows you to access the value of a given machine word
2421 at position "C<$offset>" in the internal array of words of the given
2424 Note that "C<$offset>" must lie in the permitted range between "C<0>"
2425 and "C<$vector-E<gt>Word_Size()-1>", or a fatal "offset out of range"
2428 This method is similar in function to the expression
2429 "C<$word = $array[$offset];>" for a Perl array.
2433 C<$vector-E<gt>Word_List_Store(@words);>
2435 This method allows you to store a list of values "C<@words>" in the
2436 internal array of machine words of the given bit vector.
2438 Thereby the B<LEFTMOST> value in the list ("C<$words[0]>") is stored
2439 in the B<LEAST> significant word of the internal array of words (the
2440 one with offset "C<0>"), the next value from the list ("C<$words[1]>")
2441 is stored in the word with offset "C<1>", and so on, as intuitively
2444 If the list "C<@words>" contains fewer elements than the internal
2445 array of words of the given bit vector contains machine words,
2446 the remaining (most significant) words are filled with zeros.
2448 If the list "C<@words>" contains more elements than the internal
2449 array of words of the given bit vector contains machine words,
2450 the superfluous values are simply ignored.
2452 This method is comparable in function to the expression
2453 "C<@array = @words;>" for a Perl array.
2457 C<@words = $vector-E<gt>Word_List_Read();>
2459 This method allows you to retrieve the internal array of machine
2460 words of the given bit vector all at once.
2462 Thereby the B<LEFTMOST> value in the returned list ("C<$words[0]>")
2463 is the B<LEAST> significant word from the given bit vector, and the
2464 B<RIGHTMOST> value in the returned list ("C<$words[$#words]>") is
2465 the B<MOST> significant word of the given bit vector.
2467 This method is similar in function to the expression
2468 "C<@words = @array;>" for a Perl array.
2472 C<$vector-E<gt>Word_Insert($offset,$count);>
2474 This method inserts "C<$count>" empty new machine words at position
2475 "C<$offset>" in the internal array of words of the given bit vector.
2477 The "C<$count>" most significant words are lost, and all words starting
2478 with word number "C<$offset>" up to and including word number
2479 "C<$vector-E<gt>Word_Size()-$count-1>" are moved up by "C<$count>" places.
2481 The now vacant "C<$count>" words starting at word number "C<$offset>"
2482 (up to and including word number "C<$offset+$count-1>") are then set
2485 Note that this method does B<NOT> increase the size of the given bit
2486 vector, i.e., the bit vector is B<NOT> extended at its upper end to
2487 "rescue" the "C<$count>" uppermost (most significant) words - instead,
2488 these words are lost forever.
2490 If you don't want this to happen, you have to increase the size of the
2491 given bit vector B<EXPLICITLY> and B<BEFORE> you perform the "Insert"
2492 operation, with a statement such as the following:
2494 $vector->Resize($vector->Size() + $count * Bit::Vector->Word_Bits());
2496 Note also that "C<$offset>" must lie in the permitted range between
2497 "C<0>" and "C<$vector-E<gt>Word_Size()-1>", or a fatal "offset out
2498 of range" error will occur.
2500 If the term "C<$offset + $count>" exceeds "C<$vector-E<gt>Word_Size()-1>",
2501 all the words starting with word number "C<$offset>" up to word number
2502 "C<$vector-E<gt>Word_Size()-1>" are simply cleared.
2506 C<$vector-E<gt>Word_Delete($offset,$count);>
2508 This method deletes, i.e., removes the words starting at position
2509 "C<$offset>" up to and including word number "C<$offset+$count-1>"
2510 from the internal array of machine words of the given bit vector.
2512 The remaining uppermost words (starting at position "C<$offset+$count>"
2513 up to and including word number "C<$vector-E<gt>Word_Size()-1>") are
2514 moved down by "C<$count>" places.
2516 The now vacant uppermost (most significant) "C<$count>" words are then
2517 set to zero (cleared).
2519 Note that this method does B<NOT> decrease the size of the given bit
2520 vector, i.e., the bit vector is B<NOT> clipped at its upper end to
2521 "get rid of" the vacant "C<$count>" uppermost words.
2523 If you don't want this, i.e., if you want the bit vector to shrink
2524 accordingly, you have to do so B<EXPLICITLY> and B<AFTER> the "Delete"
2525 operation, with a couple of statements such as these:
2527 $bits = $vector->Size();
2528 $count *= Bit::Vector->Word_Bits();
2529 if ($count > $bits) { $count = $bits; }
2530 $vector->Resize($bits - $count);
2532 Note also that "C<$offset>" must lie in the permitted range between
2533 "C<0>" and "C<$vector-E<gt>Word_Size()-1>", or a fatal "offset out
2534 of range" error will occur.
2536 If the term "C<$offset + $count>" exceeds "C<$vector-E<gt>Word_Size()-1>",
2537 all the words starting with word number "C<$offset>" up to word number
2538 "C<$vector-E<gt>Word_Size()-1>" are simply cleared.
2542 C<$vector-E<gt>Chunk_Store($chunksize,$offset,$chunk);>
2544 This method allows you to set more than one bit at a time with
2547 You can access chunks (i.e., ranges of contiguous bits) between
2548 one and at most "C<Bit::Vector-E<gt>Long_Bits()>" bits wide.
2550 In order to be portable, though, you should never use chunk sizes
2551 larger than 32 bits.
2553 If the given "C<$chunksize>" does not lie between "C<1>" and
2554 "C<Bit::Vector-E<gt>Long_Bits()>", a fatal "chunk size out of range"
2557 The method copies the "C<$chunksize>" least significant bits
2558 from the value "C<$chunk>" to the given bit vector, starting at
2559 bit position "C<$offset>" and proceeding upwards until bit number
2560 "C<$offset+$chunksize-1>".
2562 (I.e., bit number "C<0>" of "C<$chunk>" becomes bit number "C<$offset>"
2563 in the given bit vector, and bit number "C<$chunksize-1>" becomes
2564 bit number "C<$offset+$chunksize-1>".)
2566 If the term "C<$offset+$chunksize-1>" exceeds "C<$vector-E<gt>Size()-1>",
2567 the corresponding superfluous (most significant) bits from "C<$chunk>"
2570 Note that "C<$offset>" itself must lie in the permitted range between
2571 "C<0>" and "C<$vector-E<gt>Size()-1>", or a fatal "offset out of range"
2574 This method (as well as the other "C<Chunk_>" methods) is useful, for
2575 example, when you are reading in data in chunks of, say, 8 bits, which
2576 you need to access later, say, using 16 bits at a time (like audio CD
2577 wave files, for instance).
2581 C<$chunk = $vector-E<gt>Chunk_Read($chunksize,$offset);>
2583 This method allows you to read the values of more than one bit at
2586 You can read chunks (i.e., ranges of contiguous bits) between
2587 one and at most "C<Bit::Vector-E<gt>Long_Bits()>" bits wide.
2589 In order to be portable, though, you should never use chunk sizes
2590 larger than 32 bits.
2592 If the given "C<$chunksize>" does not lie between "C<1>" and
2593 "C<Bit::Vector-E<gt>Long_Bits()>", a fatal "chunk size out of range"
2596 The method returns the "C<$chunksize>" bits from the given bit vector
2597 starting at bit position "C<$offset>" and proceeding upwards until
2598 bit number "C<$offset+$chunksize-1>".
2600 (I.e., bit number "C<$offset>" of the given bit vector becomes bit number
2601 "C<0>" of the returned value, and bit number "C<$offset+$chunksize-1>"
2602 becomes bit number "C<$chunksize-1>".)
2604 If the term "C<$offset+$chunksize-1>" exceeds "C<$vector-E<gt>Size()-1>",
2605 the non-existent bits are simply not returned.
2607 Note that "C<$offset>" itself must lie in the permitted range between
2608 "C<0>" and "C<$vector-E<gt>Size()-1>", or a fatal "offset out of range"
2613 C<$vector-E<gt>Chunk_List_Store($chunksize,@chunks);>
2615 This method allows you to fill the given bit vector with a list of
2616 data packets ("chunks") of any size ("C<$chunksize>") you like
2617 (within certain limits).
2619 In fact the given "C<$chunksize>" must lie in the range between "C<1>"
2620 and "C<Bit::Vector-E<gt>Long_Bits()>", or a fatal "chunk size out of
2621 range" error will occur.
2623 In order to be portable, though, you should never use chunk sizes
2624 larger than 32 bits.
2626 The given bit vector is thereby filled in ascending order: The first
2627 chunk from the list (i.e., "C<$chunks[0]>") fills the "C<$chunksize>"
2628 least significant bits, the next chunk from the list ("C<$chunks[1]>")
2629 fills the bits number "C<$chunksize>" to number "C<2*$chunksize-1>",
2630 the third chunk ("C<$chunks[2]>") fills the bits number "C<2*$chunksize>",
2631 to number "C<3*$chunksize-1>", and so on.
2633 If there a less chunks in the list than are needed to fill the entire
2634 bit vector, the remaining (most significant) bits are cleared, i.e.,
2635 the previous contents of the given bit vector are always erased completely.
2637 If there are more chunks in the list than are needed to fill the entire
2638 bit vector, and/or if a chunk extends beyond "C<$vector-E<gt>Size()-1>"
2639 (which happens whenever "C<$vector-E<gt>Size()>" is not a multiple of
2640 "C<$chunksize>"), the superfluous chunks and/or bits are simply ignored.
2642 The method is useful, for example (and among many other applications),
2643 for the conversion of packet sizes in a data stream.
2645 This method can also be used to store an octal string in a given
2648 $vector->Chunk_List_Store(3, split(//, reverse $string));
2650 Note however that unlike the conversion methods "C<from_Hex()>",
2651 "C<from_Bin()>", "C<from_Dec()>" and "C<from_Enum()>",
2652 this statement does not include any syntax checking, i.e.,
2653 it may fail silently, without warning.
2655 To perform syntax checking, add the following statements:
2657 if ($string =~ /^[0-7]+$/)
2659 # okay, go ahead with conversion as shown above
2663 # error, string contains other than octal characters
2666 Another application is to store a repetitive pattern in a given
2669 $pattern = 0xDEADBEEF;
2670 $length = 32; # = length of $pattern in bits
2671 $size = $vector->Size();
2672 $factor = int($size / $length);
2673 if ($size % $length) { $factor++; }
2674 $vector->Chunk_List_Store($length, ($pattern) x $factor);
2678 C<@chunks = $vector-E<gt>Chunk_List_Read($chunksize);>
2680 This method allows you to access the contents of the given bit vector in
2681 form of a list of data packets ("chunks") of a size ("C<$chunksize>")
2682 of your choosing (within certain limits).
2684 In fact the given "C<$chunksize>" must lie in the range between "C<1>"
2685 and "C<Bit::Vector-E<gt>Long_Bits()>", or a fatal "chunk size out of
2686 range" error will occur.
2688 In order to be portable, though, you should never use chunk sizes
2689 larger than 32 bits.
2691 The given bit vector is thereby read in ascending order: The
2692 "C<$chunksize>" least significant bits (bits number "C<0>" to
2693 "C<$chunksize-1>") become the first chunk in the returned list
2694 (i.e., "C<$chunks[0]>"). The bits number "C<$chunksize>" to
2695 "C<2*$chunksize-1>" become the next chunk in the list
2696 ("C<$chunks[1]>"), and so on.
2698 If "C<$vector-E<gt>Size()>" is not a multiple of "C<$chunksize>",
2699 the last chunk in the list will contain fewer bits than "C<$chunksize>".
2701 B<BEWARE> that for large bit vectors and/or small values of "C<$chunksize>",
2702 the number of returned list elements can be extremely large! B<BE CAREFUL!>
2704 You could blow up your application with lack of memory (each list element
2705 is a full-grown Perl scalar, internally, with an associated memory overhead
2706 for its administration!) or at least cause a noticeable, more or less
2707 long-lasting "freeze" of your application!
2709 Possible applications:
2711 The method is especially useful in the conversion of packet sizes in
2714 This method can also be used to convert a given bit vector to a string
2717 $string = reverse join('', $vector->Chunk_List_Read(3));
2721 C<$vector-E<gt>Index_List_Remove(@indices);>
2723 This method allows you to specify a list of indices of bits which
2724 should be turned off in the given bit vector.
2726 In fact this method is a shortcut for
2728 foreach $index (@indices)
2730 $vector->Bit_Off($index);
2733 In contrast to all other import methods in this module, this method
2734 does B<NOT> clear the given bit vector before processing its list
2737 Instead, this method allows you to accumulate the results of various
2740 (The same holds for the method "C<Index_List_Store()>". As a
2741 consequence, you can "wipe out" what you did using the method
2742 "C<Index_List_Remove()>" by passing the identical argument list
2743 to the method "C<Index_List_Store()>".)
2747 C<$vector-E<gt>Index_List_Store(@indices);>
2749 This method allows you to specify a list of indices of bits which
2750 should be turned on in the given bit vector.
2752 In fact this method is a shortcut for
2754 foreach $index (@indices)
2756 $vector->Bit_On($index);
2759 In contrast to all other import methods in this module, this method
2760 does B<NOT> clear the given bit vector before processing its list
2763 Instead, this method allows you to accumulate the results of various
2766 (The same holds for the method "C<Index_List_Remove()>". As a
2767 consequence, you can "wipe out" what you did using the method
2768 "C<Index_List_Store()>" by passing the identical argument list
2769 to the method "C<Index_List_Remove()>".)
2773 C<@indices = $vector-E<gt>Index_List_Read();>
2775 This method returns a list of Perl scalars.
2777 The list contains one scalar for each set bit in the given
2780 B<BEWARE> that for large bit vectors, this can result in a literally
2781 overwhelming number of list elements! B<BE CAREFUL!> You could run
2782 out of memory or slow down your application considerably!
2784 Each scalar contains the number of the index corresponding to
2785 the bit in question.
2787 These indices are always returned in ascending order.
2789 If the given bit vector is empty (contains only cleared bits)
2790 or if it has a length of zero (if it contains no bits at all),
2791 the method returns an empty list.
2793 This method can be useful, for instance, to obtain a list of
2796 $limit = 1000; # or whatever
2797 $vector = Bit::Vector->new($limit+1);
2799 @primes = $vector->Index_List_Read();
2803 C<$vec3-E<gt>Or($vec1,$vec2);>
2805 C<$set3-E<gt>Union($set1,$set2);>
2807 This method calculates the union of "C<$set1>" and "C<$set2>" and stores
2808 the result in "C<$set3>".
2810 This is usually written as "C<$set3 = $set1 u $set2>" in set theory
2811 (where "u" is the "cup" operator).
2813 (On systems where the "cup" character is unavailable this operator
2814 is often denoted by a plus sign "+".)
2816 In-place calculation is also possible, i.e., "C<$set3>" may be identical
2817 with "C<$set1>" or "C<$set2>" or both.
2821 C<$vec3-E<gt>And($vec1,$vec2);>
2823 C<$set3-E<gt>Intersection($set1,$set2);>
2825 This method calculates the intersection of "C<$set1>" and "C<$set2>" and
2826 stores the result in "C<$set3>".
2828 This is usually written as "C<$set3 = $set1 n $set2>" in set theory
2829 (where "n" is the "cap" operator).
2831 (On systems where the "cap" character is unavailable this operator
2832 is often denoted by an asterisk "*".)
2834 In-place calculation is also possible, i.e., "C<$set3>" may be identical
2835 with "C<$set1>" or "C<$set2>" or both.
2839 C<$vec3-E<gt>AndNot($vec1,$vec2);>
2841 C<$set3-E<gt>Difference($set1,$set2);>
2843 This method calculates the difference of "C<$set1>" less "C<$set2>" and
2844 stores the result in "C<$set3>".
2846 This is usually written as "C<$set3 = $set1 \ $set2>" in set theory
2847 (where "\" is the "less" operator).
2849 In-place calculation is also possible, i.e., "C<$set3>" may be identical
2850 with "C<$set1>" or "C<$set2>" or both.
2854 C<$vec3-E<gt>Xor($vec1,$vec2);>
2856 C<$set3-E<gt>ExclusiveOr($set1,$set2);>
2858 This method calculates the symmetric difference of "C<$set1>" and "C<$set2>"
2859 and stores the result in "C<$set3>".
2861 This can be written as "C<$set3 = ($set1 u $set2) \ ($set1 n $set2)>" in set
2862 theory (the union of the two sets less their intersection).
2864 When sets are implemented as bit vectors then the above formula is
2865 equivalent to the exclusive-or between corresponding bits of the two
2866 bit vectors (hence the name of this method).
2868 Note that this method is also much more efficient than evaluating the
2869 above formula explicitly since it uses a built-in machine language
2870 instruction internally.
2872 In-place calculation is also possible, i.e., "C<$set3>" may be identical
2873 with "C<$set1>" or "C<$set2>" or both.
2877 C<$vec2-E<gt>Not($vec1);>
2879 C<$set2-E<gt>Complement($set1);>
2881 This method calculates the complement of "C<$set1>" and stores the result
2884 In "big integer" arithmetic, this is equivalent to calculating the one's
2885 complement of the number stored in the bit vector "C<$set1>" in binary
2888 In-place calculation is also possible, i.e., "C<$set2>" may be identical
2893 C<if ($set1-E<gt>subset($set2))>
2895 Returns "true" ("C<1>") if "C<$set1>" is a subset of "C<$set2>"
2896 (i.e., completely contained in "C<$set2>") and "false" ("C<0>")
2899 This means that any bit which is set ("C<1>") in "C<$set1>" must
2900 also be set in "C<$set2>", but "C<$set2>" may contain set bits
2901 which are not set in "C<$set1>", in order for the condition
2902 of subset relationship to be true between these two sets.
2904 Note that by definition, if two sets are identical, they are
2905 also subsets (and also supersets) of each other.
2909 C<$norm = $set-E<gt>Norm();>
2911 Returns the norm (number of bits which are set) of the given vector.
2913 This is equivalent to the number of elements contained in the given
2916 Uses a byte lookup table for calculating the number of set bits
2917 per byte, and thus needs a time for evaluation (and a number of
2918 loops) linearly proportional to the length of the given bit vector
2921 This should be the fastest algorithm on average.
2925 C<$norm = $set-E<gt>Norm2();>
2927 Returns the norm (number of bits which are set) of the given vector.
2929 This is equivalent to the number of elements contained in the given
2932 This does the same as the method "C<Norm()>" above, only with a
2933 different algorithm:
2935 This method counts the number of set and cleared bits at the same
2936 time and will stop when either of them has been exhausted, thus
2937 needing at most half as many loops per machine word as the total
2938 number of bits in a machine word - in fact it will need a number
2939 of loops equal to the minimum of the number of set bits and the
2940 number of cleared bits.
2942 This might be a faster algorithm than of the method "C<Norm()>"
2943 above on some systems, depending on the system's architecture
2944 and the compiler and optimisation used, for bit vectors with
2945 sparse set bits and for bit vectors with sparse cleared bits
2946 (i.e., predominantly set bits).
2950 C<$norm = $set-E<gt>Norm3();>
2952 Returns the norm (number of bits which are set) of the given vector.
2954 This is equivalent to the number of elements contained in the given
2957 This does the same as the two methods "C<Norm()>" and "C<Norm2()>"
2958 above, however with a different algorithm.
2960 In fact this is the implementation of the method "C<Norm()>" used
2961 in previous versions of this module.
2963 The method needs a number of loops per machine word equal to the
2964 number of set bits in that machine word.
2966 Only for bit vectors with sparse set bits will this method be
2967 fast; it will depend on a system's architecture and compiler
2968 whether the method will be faster than any of the two methods
2969 above in such cases.
2971 On average however, this is probably the slowest method of the
2976 C<$min = $set-E<gt>Min();>
2978 Returns the minimum of the given set, i.e., the minimum of all
2979 indices of all set bits in the given bit vector "C<$set>".
2981 If the set is empty (no set bits), plus infinity (represented
2982 by the constant "MAX_LONG" on your system) is returned.
2984 (This constant is usually S<2 ^ (n-1) - 1>, where "C<n>" is the
2985 number of bits of an unsigned long on your machine.)
2989 C<$max = $set-E<gt>Max();>
2991 Returns the maximum of the given set, i.e., the maximum of all
2992 indices of all set bits in the given bit vector "C<$set>".
2994 If the set is empty (no set bits), minus infinity (represented
2995 by the constant "MIN_LONG" on your system) is returned.
2997 (This constant is usually S<-(2 ^ (n-1) - 1)> or S<-(2 ^ (n-1))>,
2998 where "C<n>" is the number of bits of an unsigned long on your machine.)
3002 C<$m3-E<gt>Multiplication($r3,$c3,$m1,$r1,$c1,$m2,$r2,$c2);>
3004 This method multiplies two boolean matrices (stored as bit vectors)
3005 "C<$m1>" and "C<$m2>" and stores the result in matrix "C<$m3>".
3007 The method uses the binary "xor" operation ("C<^>") as the boolean
3008 addition operator ("C<+>").
3010 An exception is raised if the product of the number of rows and
3011 columns of any of the three matrices differs from the actual size
3012 of their underlying bit vector.
3014 An exception is also raised if the numbers of rows and columns
3015 of the three matrices do not harmonize in the required manner:
3021 This method is used by the module "Math::MatrixBool".
3023 See L<Math::MatrixBool(3)> for details.
3027 C<$m3-E<gt>Product($r3,$c3,$m1,$r1,$c1,$m2,$r2,$c2);>
3029 This method multiplies two boolean matrices (stored as bit vectors)
3030 "C<$m1>" and "C<$m2>" and stores the result in matrix "C<$m3>".
3032 This special method uses the binary "or" operation ("C<|>") as the
3033 boolean addition operator ("C<+>").
3035 An exception is raised if the product of the number of rows and
3036 columns of any of the three matrices differs from the actual size
3037 of their underlying bit vector.
3039 An exception is also raised if the numbers of rows and columns
3040 of the three matrices do not harmonize in the required manner:
3046 This method is used by the module "Math::MatrixBool".
3048 See L<Math::MatrixBool(3)> for details.
3052 C<$matrix-E<gt>Closure($rows,$cols);>
3054 This method calculates the reflexive transitive closure of the
3055 given boolean matrix (stored as a bit vector) using Kleene's
3058 (See L<Math::Kleene(3)> for a brief introduction into the
3059 theory behind Kleene's algorithm.)
3061 The reflexive transitive closure answers the question whether
3062 a path exists between any two vertices of a graph whose edges
3063 are given as a matrix:
3065 If a (directed) edge exists going from vertex "i" to vertex "j",
3066 then the element in the matrix with coordinates (i,j) is set to
3067 "C<1>" (otherwise it remains set to "C<0>").
3069 If the edges are undirected, the resulting matrix is symmetric,
3070 i.e., elements (i,j) and (j,i) always contain the same value.
3072 The matrix representing the edges of the graph only answers the
3073 question whether an B<EDGE> exists between any two vertices of
3074 the graph or not, whereas the reflexive transitive closure
3075 answers the question whether a B<PATH> (a series of adjacent
3076 edges) exists between any two vertices of the graph!
3078 Note that the contents of the given matrix are modified by
3079 this method, so make a copy of the initial matrix in time
3080 if you are going to need it again later.
3082 An exception is raised if the given matrix is not quadratic,
3083 i.e., if the number of rows and columns of the given matrix
3086 An exception is also raised if the product of the number of
3087 rows and columns of the given matrix differs from the actual
3088 size of its underlying bit vector.
3090 This method is used by the module "Math::MatrixBool".
3092 See L<Math::MatrixBool(3)> for details.
3096 C<$matrix2-E<gt>Transpose($rows2,$cols2,$matrix1,$rows1,$cols1);>
3098 This method calculates the transpose of a boolean matrix "C<$matrix1>"
3099 (stored as a bit vector) and stores the result in matrix "C<$matrix2>".
3101 The transpose of a boolean matrix, representing the edges of a graph,
3102 can be used for finding the strongly connected components of that graph.
3104 An exception is raised if the product of the number of rows and
3105 columns of any of the two matrices differs from the actual size
3106 of its underlying bit vector.
3108 An exception is also raised if the following conditions are not
3114 Note that in-place processing ("C<$matrix1>" and "C<$matrix2>" are
3115 identical) is only possible if the matrix is quadratic. Otherwise,
3116 a fatal "matrix is not quadratic" error will occur.
3118 This method is used by the module "Math::MatrixBool".
3120 See L<Math::MatrixBool(3)> for details.
3126 Bit::Vector::Overload(3),
3127 Bit::Vector::String(3).
3130 Math::MatrixBool(3),
3131 Math::MatrixReal(3),
3138 This man page documents "Bit::Vector" version 6.4.
3143 mailto:sb@engelschall.com
3144 http://www.engelschall.com/u/sb/download/
3148 Copyright (c) 1995 - 2004 by Steffen Beyer. All rights reserved.
3152 This package is free software; you can redistribute it and/or
3153 modify it under the same terms as Perl itself, i.e., under the
3154 terms of the "Artistic License" or the "GNU General Public License".
3156 The C library at the core of this Perl module can additionally
3157 be redistributed and/or modified under the terms of the "GNU
3158 Library General Public License".
3160 Please refer to the files "Artistic.txt", "GNU_GPL.txt" and
3161 "GNU_LGPL.txt" in this distribution for details!
3165 This package is distributed in the hope that it will be useful,
3166 but WITHOUT ANY WARRANTY; without even the implied warranty of
3167 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
3169 See the "GNU General Public License" for more details.