1Vector(3) User Contributed Perl Documentation Vector(3)
2
6 Bit::Vector - Efficient bit vector, set of integers and "big int" math
7 library
8
10 OVERLOADED OPERATORS
11 See Bit::Vector::Overload(3).
12 MORE STRING IMPORT/EXPORT
14 See Bit::Vector::String(3).
15 CLASS METHODS
17 Version
18 $version = Bit::Vector->Version();
19 Word_Bits
21 $bits = Bit::Vector->Word_Bits(); # bits in a machine word
22 Long_Bits
24 $bits = Bit::Vector->Long_Bits(); # bits in an unsigned long
25 new
27 $vector = Bit::Vector->new($bits); # bit vector constructor
28 @veclist = Bit::Vector->new($bits,$count);
30 new_Hex
32 $vector = Bit::Vector->new_Hex($bits,$string);
33 new_Bin
35 $vector = Bit::Vector->new_Bin($bits,$string);
36 new_Dec
38 $vector = Bit::Vector->new_Dec($bits,$string);
39 new_Enum
41 $vector = Bit::Vector->new_Enum($bits,$string);
42 Concat_List
44 $vector = Bit::Vector->Concat_List(@vectors);
45 OBJECT METHODS
47 new
48 $vec2 = $vec1->new($bits); # alternative call of constructor
49 @veclist = $vec->new($bits,$count);
51 Shadow
53 $vec2 = $vec1->Shadow(); # new vector, same size but empty
54 Clone
56 $vec2 = $vec1->Clone(); # new vector, exact duplicate
57 Concat
59 $vector = $vec1->Concat($vec2);
60 Concat_List
62 $vector = $vec1->Concat_List($vec2,$vec3,...);
63 Size
65 $bits = $vector->Size();
66 Resize
68 $vector->Resize($bits);
69 $vector->Resize($vector->Size()+5);
70 $vector->Resize($vector->Size()-5);
71 Copy
73 $vec2->Copy($vec1);
74 Empty
76 $vector->Empty();
77 Fill
79 $vector->Fill();
80 Flip
82 $vector->Flip();
83 Primes
85 $vector->Primes(); # Sieve of Erathostenes
86 Reverse
88 $vec2->Reverse($vec1);
89 Interval_Empty
91 $vector->Interval_Empty($min,$max);
92 Interval_Fill
94 $vector->Interval_Fill($min,$max);
95 Interval_Flip
97 $vector->Interval_Flip($min,$max);
98 Interval_Reverse
100 $vector->Interval_Reverse($min,$max);
101 Interval_Scan_inc
103 if (($min,$max) = $vector->Interval_Scan_inc($start))
104 Interval_Scan_dec
106 if (($min,$max) = $vector->Interval_Scan_dec($start))
107 Interval_Copy
109 $vec2->Interval_Copy($vec1,$offset2,$offset1,$length);
110 Interval_Substitute
112 $vec2->Interval_Substitute($vec1,$off2,$len2,$off1,$len1);
113 is_empty
115 if ($vector->is_empty())
116 is_full
118 if ($vector->is_full())
119 equal
121 if ($vec1->equal($vec2))
122 Lexicompare (unsigned)
124 if ($vec1->Lexicompare($vec2) == 0)
125 if ($vec1->Lexicompare($vec2) != 0)
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 Compare (signed)
132 if ($vec1->Compare($vec2) == 0)
133 if ($vec1->Compare($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 to_Hex
140 $string = $vector->to_Hex();
141 from_Hex
143 $vector->from_Hex($string);
144 to_Bin
146 $string = $vector->to_Bin();
147 from_Bin
149 $vector->from_Bin($string);
150 to_Dec
152 $string = $vector->to_Dec();
153 from_Dec
155 $vector->from_Dec($string);
156 to_Enum
158 $string = $vector->to_Enum(); # e.g. "2,3,5-7,11,13-19"
159 from_Enum
161 $vector->from_Enum($string);
162 Bit_Off
164 $vector->Bit_Off($index);
165 Bit_On
167 $vector->Bit_On($index);
168 bit_flip
170 $bit = $vector->bit_flip($index);
171 bit_test
173 contains
174 $bit = $vector->bit_test($index);
175 $bit = $vector->contains($index);
176 if ($vector->bit_test($index))
177 if ($vector->contains($index))
178 Bit_Copy
180 $vector->Bit_Copy($index,$bit);
181 LSB (least significant bit)
183 $vector->LSB($bit);
184 MSB (most significant bit)
186 $vector->MSB($bit);
187 lsb (least significant bit)
189 $bit = $vector->lsb();
190 msb (most significant bit)
192 $bit = $vector->msb();
193 rotate_left
195 $carry = $vector->rotate_left();
196 rotate_right
198 $carry = $vector->rotate_right();
199 shift_left
201 $carry = $vector->shift_left($carry);
202 shift_right
204 $carry = $vector->shift_right($carry);
205 Move_Left
207 $vector->Move_Left($bits); # shift left "$bits" positions
208 Move_Right
210 $vector->Move_Right($bits); # shift right "$bits" positions
211 Insert
213 $vector->Insert($offset,$bits);
214 Delete
216 $vector->Delete($offset,$bits);
217 increment
219 $carry = $vector->increment();
220 decrement
222 $carry = $vector->decrement();
223 inc
225 $overflow = $vec2->inc($vec1);
226 dec
228 $overflow = $vec2->dec($vec1);
229 add
231 $carry = $vec3->add($vec1,$vec2,$carry);
232 ($carry,$overflow) = $vec3->add($vec1,$vec2,$carry);
233 subtract
235 $carry = $vec3->subtract($vec1,$vec2,$carry);
236 ($carry,$overflow) = $vec3->subtract($vec1,$vec2,$carry);
237 Neg
239 Negate
240 $vec2->Neg($vec1);
241 $vec2->Negate($vec1);
242 Abs
244 Absolute
245 $vec2->Abs($vec1);
246 $vec2->Absolute($vec1);
247 Sign
249 if ($vector->Sign() == 0)
250 if ($vector->Sign() != 0)
251 if ($vector->Sign() < 0)
252 if ($vector->Sign() <= 0)
253 if ($vector->Sign() > 0)
254 if ($vector->Sign() >= 0)
255 Multiply
257 $vec3->Multiply($vec1,$vec2);
258 Divide
260 $quot->Divide($vec1,$vec2,$rest);
261 GCD (Greatest Common Divisor)
263 $vecgcd->GCD($veca,$vecb);
264 $vecgcd->GCD($vecx,$vecy,$veca,$vecb);
265 Power
267 $vec3->Power($vec1,$vec2);
268 Block_Store
270 $vector->Block_Store($buffer);
271 Block_Read
273 $buffer = $vector->Block_Read();
274 Word_Size
276 $size = $vector->Word_Size(); # number of words in "$vector"
277 Word_Store
279 $vector->Word_Store($offset,$word);
280 Word_Read
282 $word = $vector->Word_Read($offset);
283 Word_List_Store
285 $vector->Word_List_Store(@words);
286 Word_List_Read
288 @words = $vector->Word_List_Read();
289 Word_Insert
291 $vector->Word_Insert($offset,$count);
292 Word_Delete
294 $vector->Word_Delete($offset,$count);
295 Chunk_Store
297 $vector->Chunk_Store($chunksize,$offset,$chunk);
298 Chunk_Read
300 $chunk = $vector->Chunk_Read($chunksize,$offset);
301 Chunk_List_Store
303 $vector->Chunk_List_Store($chunksize,@chunks);
304 Chunk_List_Read
306 @chunks = $vector->Chunk_List_Read($chunksize);
307 Index_List_Remove
309 $vector->Index_List_Remove(@indices);
310 Index_List_Store
312 $vector->Index_List_Store(@indices);
313 Index_List_Read
315 @indices = $vector->Index_List_Read();
316 Or
318 Union
319 $vec3->Or($vec1,$vec2);
320 $set3->Union($set1,$set2);
321 And
323 Intersection
324 $vec3->And($vec1,$vec2);
325 $set3->Intersection($set1,$set2);
326 AndNot
328 Difference
329 $vec3->AndNot($vec1,$vec2);
330 $set3->Difference($set1,$set2);
331 Xor
333 ExclusiveOr
334 $vec3->Xor($vec1,$vec2);
335 $set3->ExclusiveOr($set1,$set2);
336 Not
338 Complement
339 $vec2->Not($vec1);
340 $set2->Complement($set1);
341 subset
343 if ($set1->subset($set2)) # true if $set1 is subset of $set2
344 Norm
346 $norm = $set->Norm();
347 $norm = $set->Norm2();
348 $norm = $set->Norm3();
349 Min
351 $min = $set->Min();
352 Max
354 $max = $set->Max();
355 Multiplication
357 $matrix3->Multiplication($rows3,$cols3,
358 $matrix1,$rows1,$cols1,
359 $matrix2,$rows2,$cols2);
360 Product
362 $matrix3->Product($rows3,$cols3,
363 $matrix1,$rows1,$cols1,
364 $matrix2,$rows2,$cols2);
365 Closure
367 $matrix->Closure($rows,$cols);
368 Transpose
370 $matrix2->Transpose($rows2,$cols2,$matrix1,$rows1,$cols1);
371
373 • Method naming conventions
374 Method names completely in lower case indicate a boolean return
376 value.
377 (Except for the bit vector constructor method ""new()"", of course.)
379 • Boolean values
381 Boolean values in this module are always a numeric zero ("0") for
383 "false" and a numeric one ("1") for "true".
384 • Negative numbers
386 All numeric input parameters passed to any of the methods in this
388 module are regarded as being UNSIGNED (as opposed to the contents of
389 the bit vectors themselves, which are usually considered to be
390 SIGNED).
391 As a consequence, whenever you pass a negative number as an argument
393 to some method of this module, it will be treated as a (usually very
394 large) positive number due to its internal two's complement binary
395 representation, usually resulting in an "index out of range" error
396 message and program abortion.
397 • Bit order
399 Note that bit vectors are stored least order bit and least order word
401 first internally.
402 I.e., bit #0 of any given bit vector corresponds to bit #0 of word #0
404 in the array of machine words representing the bit vector.
405 (Where word #0 comes first in memory, i.e., it is stored at the least
407 memory address in the allocated block of memory holding the given bit
408 vector.)
409 Note however that machine words can be stored least order byte first
411 or last, depending on your system's implementation.
412 When you are exporting or importing a whole bit vector at once using
414 the methods ""Block_Read()"" and ""Block_Store()"" (the only time in
415 this module where this could make any difference), however, a
416 conversion to and from "least order byte first" order is
417 automatically supplied.
418 In other words, what ""Block_Read()"" provides and what
420 ""Block_Store()"" expects is always in "least order byte first"
421 order, regardless of the order in which words are stored internally
422 on your machine.
423 This is to make sure that what you export on one machine using
425 ""Block_Read()"" can always be read in correctly with
426 ""Block_Store()"" on a different machine.
427 Note further that whenever bit vectors are converted to and from
429 (binary or hexadecimal) strings, the RIGHTMOST bit is always the
430 LEAST SIGNIFICANT one, and the LEFTMOST bit is always the MOST
431 SIGNIFICANT bit.
432 This is because in our western culture, numbers are always
434 represented in this way (least significant to most significant digits
435 go from right to left).
436 Of course this requires an internal reversion of order, which the
438 corresponding conversion methods perform automatically (without any
439 additional overhead, it's just a matter of starting the internal loop
440 at the bottom or the top end).
441 • "Word" related methods
443 Note that all methods whose names begin with ""Word_"" are MACHINE-
445 DEPENDENT!
446 They depend on the size (number of bits) of an "unsigned int" (C
448 type) on your machine.
449 Therefore, you should only use these methods if you are ABSOLUTELY
451 CERTAIN that portability of your code is not an issue!
452 Note that you can use arbitrarily large chunks (i.e., fragments of
454 bit vectors) of up to 32 bits IN A PORTABLE WAY using the methods
455 whose names begin with ""Chunk_"".
456 • Chunk sizes
458 Note that legal chunk sizes for all methods whose names begin with
460 ""Chunk_"" range from "1" to ""Bit::Vector->Long_Bits();"" bits ("0"
461 is NOT allowed!).
462 In order to make your programs portable, however, you shouldn't use
464 chunk sizes larger than 32 bits, since this is the minimum size of an
465 "unsigned long" (C type) on all systems, as prescribed by ANSI C.
466 • Matching sizes
468 In general, for methods involving several bit vectors at the same
470 time, all bit vector arguments must have identical sizes (number of
471 bits), or a fatal "size mismatch" error will occur.
472 Exceptions from this rule are the methods ""Concat()"",
474 ""Concat_List()"", ""Copy()"", ""Interval_Copy()"" and
475 ""Interval_Substitute()"", where no conditions at all are imposed on
476 the size of their bit vector arguments.
477 In method ""Multiply()"", all three bit vector arguments must in
479 principle obey the rule of matching sizes, but the bit vector in
480 which the result of the multiplication is to be stored may be larger
481 than the two bit vector arguments containing the factors for the
482 multiplication.
483 In method ""Power()"", the bit vector for the result must be the same
485 size or greater than the base of the exponentiation term. The
486 exponent can be any size.
487 • Index ranges
489 All indices for any given bits must lie between "0" and
491 ""$vector->Size()-1"", or a fatal "index out of range" error will
492 occur.
493 • Object persistence
495 Since version 6.5, "Bit::Vector" objects can be serialized and de-
497 serialized automatically with "Storable", out-of-the-box, without
498 requiring any further user action for this to work.
499 This is also true for nested data structures (since version 6.8).
501 See the Storable(3) documentation for more details.
503
505 OVERLOADED OPERATORS
506 See Bit::Vector::Overload(3).
507 MORE STRING IMPORT/EXPORT
509 See Bit::Vector::String(3).
510 CLASS METHODS
512 • "$version = Bit::Vector->Version();"
513 Returns the current version number of this module.
515 • "$bits = Bit::Vector->Word_Bits();"
517 Returns the number of bits of an "unsigned int" (C type) on your
519 machine.
520 (An "unsigned int" is also called a "machine word", hence the name of
522 this method.)
523 • "$bits = Bit::Vector->Long_Bits();"
525 Returns the number of bits of an "unsigned long" (C type) on your
527 machine.
528 • "$vector = Bit::Vector->new($bits);"
530 This is the bit vector constructor method.
532 Call this method to create a new bit vector containing "$bits" bits
534 (with indices ranging from "0" to ""$bits-1"").
535 Note that - in contrast to previous versions - bit vectors of length
537 zero (i.e., with "$bits = 0") are permitted now.
538 The method returns a reference to the newly created bit vector.
540 A new bit vector is always initialized so that all bits are cleared
542 (turned off).
543 An exception will be raised if the method is unable to allocate the
545 necessary memory.
546 Note that if you specify a negative number for "$bits" it will be
548 interpreted as a large positive number due to its internal two's
549 complement binary representation.
550 In such a case, the bit vector constructor method will obediently
552 attempt to create a bit vector of that size, probably resulting in an
553 exception, as explained above.
554 • "@veclist = Bit::Vector->new($bits,$count);"
556 You can also create more than one bit vector at a time if you specify
558 the optional second parameter "$count".
559 The method returns a list of "$count" bit vectors which all have the
561 same number of bits "$bits" (and which are all initialized, i.e., all
562 bits are cleared).
563 If "$count" is zero, an empty list is returned.
565 If "$bits" is zero, a list of null-sized bit vectors is returned.
567 Note again that if you specify a negative number for "$count" it will
569 be interpreted as a large positive number due to its internal two's
570 complement binary representation.
571 In such a case, the bit vector constructor method will obediently
573 attempt to create that many bit vectors, probably resulting in an
574 exception ("out of memory").
575 • "$vector = Bit::Vector->new_Hex($bits,$string);"
577 This method is an alternative constructor which allows you to create
579 a new bit vector object (with "$bits" bits) and to initialize it all
580 in one go.
581 The method internally first calls the bit vector constructor method
583 ""new()"" and then passes the given string to the method
584 ""from_Hex()"".
585 However, this method is more efficient than performing these two
587 steps separately: First because in this method, the memory area
588 occupied by the new bit vector is not initialized to zeros (which is
589 pointless in this case), and second because it saves you from the
590 associated overhead of one additional method invocation.
591 An exception will be raised if the necessary memory cannot be
593 allocated (see the description of the method ""new()"" immediately
594 above for possible causes) or if the given string cannot be converted
595 successfully (see the description of the method ""from_Hex()""
596 further below for details).
597 In the latter case, the memory occupied by the new bit vector is
599 released first (i.e., "free"d) before the exception is actually
600 raised.
601 • "$vector = Bit::Vector->new_Bin($bits,$string);"
603 This method is an alternative constructor which allows you to create
605 a new bit vector object (with "$bits" bits) and to initialize it all
606 in one go.
607 The method internally first calls the bit vector constructor method
609 ""new()"" and then passes the given string to the method
610 ""from_Bin()"".
611 However, this method is more efficient than performing these two
613 steps separately: First because in this method, the memory area
614 occupied by the new bit vector is not initialized to zeros (which is
615 pointless in this case), and second because it saves you from the
616 associated overhead of one additional method invocation.
617 An exception will be raised if the necessary memory cannot be
619 allocated (see the description of the method ""new()"" above for
620 possible causes) or if the given string cannot be converted
621 successfully (see the description of the method ""from_Bin()""
622 further below for details).
623 In the latter case, the memory occupied by the new bit vector is
625 released first (i.e., "free"d) before the exception is actually
626 raised.
627 • "$vector = Bit::Vector->new_Dec($bits,$string);"
629 This method is an alternative constructor which allows you to create
631 a new bit vector object (with "$bits" bits) and to initialize it all
632 in one go.
633 The method internally first calls the bit vector constructor method
635 ""new()"" and then passes the given string to the method
636 ""from_Dec()"".
637 However, this method is more efficient than performing these two
639 steps separately: First because in this method, ""new()"" does not
640 initialize the memory area occupied by the new bit vector with zeros
641 (which is pointless in this case, because ""from_Dec()"" will do it
642 anyway), and second because it saves you from the associated overhead
643 of one additional method invocation.
644 An exception will be raised if the necessary memory cannot be
646 allocated (see the description of the method ""new()"" above for
647 possible causes) or if the given string cannot be converted
648 successfully (see the description of the method ""from_Dec()""
649 further below for details).
650 In the latter case, the memory occupied by the new bit vector is
652 released first (i.e., "free"d) before the exception is actually
653 raised.
654 • "$vector = Bit::Vector->new_Enum($bits,$string);"
656 This method is an alternative constructor which allows you to create
658 a new bit vector object (with "$bits" bits) and to initialize it all
659 in one go.
660 The method internally first calls the bit vector constructor method
662 ""new()"" and then passes the given string to the method
663 ""from_Enum()"".
664 However, this method is more efficient than performing these two
666 steps separately: First because in this method, ""new()"" does not
667 initialize the memory area occupied by the new bit vector with zeros
668 (which is pointless in this case, because ""from_Enum()"" will do it
669 anyway), and second because it saves you from the associated overhead
670 of one additional method invocation.
671 An exception will be raised if the necessary memory cannot be
673 allocated (see the description of the method ""new()"" above for
674 possible causes) or if the given string cannot be converted
675 successfully (see the description of the method ""from_Enum()""
676 further below for details).
677 In the latter case, the memory occupied by the new bit vector is
679 released first (i.e., "free"d) before the exception is actually
680 raised.
681 • "$vector = Bit::Vector->Concat_List(@vectors);"
683 This method creates a new vector containing all bit vectors from the
685 argument list in concatenated form.
686 The argument list may contain any number of arguments (including
688 zero); the only condition is that all arguments must be bit vectors.
689 There is no condition concerning the length (in number of bits) of
691 these arguments.
692 The vectors from the argument list are not changed in any way.
694 If the argument list is empty or if all arguments have length zero,
696 the resulting bit vector will also have length zero.
697 Note that the RIGHTMOST bit vector from the argument list will become
699 the LEAST significant part of the resulting bit vector, and the
700 LEFTMOST bit vector from the argument list will become the MOST
701 significant part of the resulting bit vector.
702 OBJECT METHODS
704 • "$vec2 = $vec1->new($bits);"
705 "@veclist = $vec->new($bits);"
707 This is an alternative way of calling the bit vector constructor
709 method.
710 Vector "$vec1" (or "$vec") is not affected by this, it just serves as
712 an anchor for the method invocation mechanism.
713 In fact ALL class methods in this module can be called this way, even
715 though this is probably considered to be "politically incorrect" by
716 OO ("object-orientation") aficionados. ;-)
717 So even if you are too lazy to type ""Bit::Vector->"" instead of
719 ""$vec1->"" (and even though laziness is - allegedly - a programmer's
720 virtue ":-)"), maybe it is better not to use this feature if you
721 don't want to get booed at. ;-)
722 • "$vec2 = $vec1->Shadow();"
724 Creates a NEW bit vector "$vec2" of the SAME SIZE as "$vec1" but
726 which is EMPTY.
727 Just like a shadow that has the same shape as the object it
729 originates from, but is flat and has no volume, i.e., contains
730 nothing.
731 • "$vec2 = $vec1->Clone();"
733 Creates a NEW bit vector "$vec2" of the SAME SIZE as "$vec1" which is
735 an EXACT COPY of "$vec1".
736 • "$vector = $vec1->Concat($vec2);"
738 This method returns a new bit vector object which is the result of
740 the concatenation of the contents of "$vec1" and "$vec2".
741 Note that the contents of "$vec1" become the MOST significant part of
743 the resulting bit vector, and "$vec2" the LEAST significant part.
744 If both bit vector arguments have length zero, the resulting bit
746 vector will also have length zero.
747 • "$vector = $vec1->Concat_List($vec2,$vec3,...);"
749 This is an alternative way of calling this (class) method as an
751 object method.
752 The method returns a new bit vector object which is the result of the
754 concatenation of the contents of "$vec1 . $vec2 . $vec3 . ..."
755 See the section "class methods" above for a detailed description of
757 this method.
758 Note that the argument list may be empty and that all arguments must
760 be bit vectors if it isn't.
761 • "$bits = $vector->Size();"
763 Returns the size (number of bits) the given vector was created with
765 (or ""Resize()""d to).
766 • "$vector->Resize($bits);"
768 Changes the size of the given vector to the specified number of bits.
770 This method allows you to change the size of an existing bit vector,
772 preserving as many bits from the old vector as will fit into the new
773 one (i.e., all bits with indices smaller than the minimum of the
774 sizes of both vectors, old and new).
775 If the number of machine words needed to store the new vector is
777 smaller than or equal to the number of words needed to store the old
778 vector, the memory allocated for the old vector is reused for the new
779 one, and only the relevant book-keeping information is adjusted
780 accordingly.
781 This means that even if the number of bits increases, new memory is
783 not necessarily being allocated (i.e., if the old and the new number
784 of bits fit into the same number of machine words).
785 If the number of machine words needed to store the new vector is
787 greater than the number of words needed to store the old vector, new
788 memory is allocated for the new vector, the old vector is copied to
789 the new one, the remaining bits in the new vector are cleared (turned
790 off) and the old vector is deleted, i.e., the memory that was
791 allocated for it is released.
792 (An exception will be raised if the method is unable to allocate the
794 necessary memory for the new vector.)
795 As a consequence, if you decrease the size of a given vector so that
797 it will use fewer machine words, and increase it again later so that
798 it will use more words than immediately before but still less than
799 the original vector, new memory will be allocated anyway because the
800 information about the size of the original vector is lost whenever
801 you resize it.
802 Note also that if you specify a negative number for "$bits" it will
804 be interpreted as a large positive number due to its internal two's
805 complement binary representation.
806 In such a case, "Resize()" will obediently attempt to create a bit
808 vector of that size, probably resulting in an exception, as explained
809 above.
810 Finally, note that - in contrast to previous versions - resizing a
812 bit vector to a size of zero bits (length zero) is now permitted.
813 • "$vec2->Copy($vec1);"
815 Copies the contents of bit vector "$vec1" to bit vector "$vec2".
817 The previous contents of bit vector "$vec2" get overwritten, i.e.,
819 are lost.
820 Both vectors must exist beforehand, i.e., this method does not CREATE
822 any new bit vector object.
823 The two vectors may be of any size.
825 If the source bit vector is larger than the target, this method will
827 copy as much of the least significant bits of the source vector as
828 will fit into the target vector, thereby discarding any extraneous
829 most significant bits.
830 BEWARE that this causes a brutal cutoff in the middle of your data,
832 and it will also leave you with an almost unpredictable sign if
833 subsequently the number in the target vector is going to be
834 interpreted as a number! (You have been warned!)
835 If the target bit vector is larger than the source, this method fills
837 up the remaining most significant bits in the target bit vector with
838 either 0's or 1's, depending on the sign (= the most significant bit)
839 of the source bit vector. This is also known as "sign extension".
840 This makes it possible to copy numbers from a smaller bit vector into
842 a larger one while preserving the number's absolute value as well as
843 its sign (due to the two's complement binary representation of
844 numbers).
845 • "$vector->Empty();"
847 Clears all bits in the given vector.
849 • "$vector->Fill();"
851 Sets all bits in the given vector.
853 • "$vector->Flip();"
855 Flips (i.e., complements) all bits in the given vector.
857 • "$vector->Primes();"
859 Clears the given bit vector and sets all bits whose indices are prime
861 numbers.
862 This method uses the algorithm known as the "Sieve of Erathostenes"
864 internally.
865 • "$vec2->Reverse($vec1);"
867 This method copies the given vector "$vec1" to the vector "$vec2",
869 thereby reversing the order of all bits.
870 I.e., the least significant bit of "$vec1" becomes the most
872 significant bit of "$vec2", whereas the most significant bit of
873 "$vec1" becomes the least significant bit of "$vec2", and so forth
874 for all bits in between.
875 Note that in-place processing is also possible, i.e., "$vec1" and
877 "$vec2" may be identical.
878 (Internally, this is the same as
880 "$vec1->Interval_Reverse(0,$vec1->Size()-1);".)
881 • "$vector->Interval_Empty($min,$max);"
883 Clears all bits in the interval "[$min..$max]" (including both
885 limits) in the given vector.
886 "$min" and "$max" may have the same value; this is the same as
888 clearing a single bit with ""Bit_Off()"" (but less efficient).
889 Note that "$vector->Interval_Empty(0,$vector->Size()-1);" is the same
891 as "$vector->Empty();" (but less efficient).
892 • "$vector->Interval_Fill($min,$max);"
894 Sets all bits in the interval "[$min..$max]" (including both limits)
896 in the given vector.
897 "$min" and "$max" may have the same value; this is the same as
899 setting a single bit with ""Bit_On()"" (but less efficient).
900 Note that "$vector->Interval_Fill(0,$vector->Size()-1);" is the same
902 as "$vector->Fill();" (but less efficient).
903 • "$vector->Interval_Flip($min,$max);"
905 Flips (i.e., complements) all bits in the interval "[$min..$max]"
907 (including both limits) in the given vector.
908 "$min" and "$max" may have the same value; this is the same as
910 flipping a single bit with ""bit_flip()"" (but less efficient).
911 Note that "$vector->Interval_Flip(0,$vector->Size()-1);" is the same
913 as "$vector->Flip();" and "$vector->Complement($vector);" (but less
914 efficient).
915 • "$vector->Interval_Reverse($min,$max);"
917 Reverses the order of all bits in the interval "[$min..$max]"
919 (including both limits) in the given vector.
920 I.e., bits "$min" and "$max" swap places, and so forth for all bits
922 in between.
923 "$min" and "$max" may have the same value; this has no effect
925 whatsoever, though.
926 • "if (($min,$max) = $vector->Interval_Scan_inc($start))"
928 Returns the minimum and maximum indices of the next contiguous block
930 of set bits (i.e., bits in the "on" state).
931 The search starts at index "$start" (i.e., "$min" >= "$start") and
933 proceeds upwards (i.e., "$max" >= "$min"), thus repeatedly increments
934 the search pointer "$start" (internally).
935 Note though that the contents of the variable (or scalar literal
937 value) "$start" is NOT altered. I.e., you have to set it to the
938 desired value yourself prior to each call to ""Interval_Scan_inc()""
939 (see also the example given below).
940 Actually, the bit vector is not searched bit by bit, but one machine
942 word at a time, in order to speed up execution (which means that this
943 method is quite efficient).
944 An empty list is returned if no such block can be found.
946 Note that a single set bit (surrounded by cleared bits) is a valid
948 block by this definition. In that case the return values for "$min"
949 and "$max" are the same.
950 Typical use:
952 $start = 0;
954 while (($start < $vector->Size()) &&
955 (($min,$max) = $vector->Interval_Scan_inc($start)))
956 {
957 $start = $max + 2;
958 # do something with $min and $max
960 }
961 • "if (($min,$max) = $vector->Interval_Scan_dec($start))"
963 Returns the minimum and maximum indices of the next contiguous block
965 of set bits (i.e., bits in the "on" state).
966 The search starts at index "$start" (i.e., "$max" <= "$start") and
968 proceeds downwards (i.e., "$min" <= "$max"), thus repeatedly
969 decrements the search pointer "$start" (internally).
970 Note though that the contents of the variable (or scalar literal
972 value) "$start" is NOT altered. I.e., you have to set it to the
973 desired value yourself prior to each call to ""Interval_Scan_dec()""
974 (see also the example given below).
975 Actually, the bit vector is not searched bit by bit, but one machine
977 word at a time, in order to speed up execution (which means that this
978 method is quite efficient).
979 An empty list is returned if no such block can be found.
981 Note that a single set bit (surrounded by cleared bits) is a valid
983 block by this definition. In that case the return values for "$min"
984 and "$max" are the same.
985 Typical use:
987 $start = $vector->Size() - 1;
989 while (($start >= 0) &&
990 (($min,$max) = $vector->Interval_Scan_dec($start)))
991 {
992 $start = $min - 2;
993 # do something with $min and $max
995 }
996 • "$vec2->Interval_Copy($vec1,$offset2,$offset1,$length);"
998 This method allows you to copy a stretch of contiguous bits (starting
1000 at any position "$offset1" you choose, with a length of "$length"
1001 bits) from a given "source" bit vector "$vec1" to another position
1002 "$offset2" in a "target" bit vector "$vec2".
1003 Note that the two bit vectors "$vec1" and "$vec2" do NOT need to have
1005 the same (matching) size!
1006 Consequently, any of the two terms ""$offset1 + $length"" and
1008 ""$offset2 + $length"" (or both) may exceed the actual length of its
1009 corresponding bit vector (""$vec1->Size()"" and ""$vec2->Size()"",
1010 respectively).
1011 In such a case, the "$length" parameter is automatically reduced
1013 internally so that both terms above are bounded by the number of bits
1014 of their corresponding bit vector.
1015 This may even result in a length of zero, in which case nothing is
1017 copied at all.
1018 (Of course the value of the "$length" parameter, supplied by you in
1020 the initial method call, may also be zero right from the start!)
1021 Note also that "$offset1" and "$offset2" must lie within the range
1023 "0" and, respectively, ""$vec1->Size()-1"" or ""$vec2->Size()-1"", or
1024 a fatal "offset out of range" error will occur.
1025 Note further that "$vec1" and "$vec2" may be identical, i.e., you may
1027 copy a stretch of contiguous bits from one part of a given bit vector
1028 to another part.
1029 The source and the target interval may even overlap, in which case
1031 the copying is automatically performed in ascending or descending
1032 order (depending on the direction of the copy - downwards or upwards
1033 in the bit vector, respectively) to handle this situation correctly,
1034 i.e., so that no bits are being overwritten before they have been
1035 copied themselves.
1036 • "$vec2->Interval_Substitute($vec1,$off2,$len2,$off1,$len1);"
1038 This method is (roughly) the same for bit vectors (i.e., arrays of
1040 booleans) as what the "splice" function in Perl is for lists (i.e.,
1041 arrays of scalars).
1042 (See "splice" in perlfunc for more details about this function.)
1044 The method allows you to substitute a stretch of contiguous bits
1046 (defined by a position (offset) "$off1" and a length of "$len1" bits)
1047 from a given "source" bit vector "$vec1" for a different stretch of
1048 contiguous bits (defined by a position (offset) "$off2" and a length
1049 of "$len2" bits) in another, "target" bit vector "$vec2".
1050 Note that the two bit vectors "$vec1" and "$vec2" do NOT need to have
1052 the same (matching) size!
1053 Note further that "$off1" and "$off2" must lie within the range "0"
1055 and, respectively, ""$vec1->Size()"" or ""$vec2->Size()"", or a fatal
1056 "offset out of range" error will occur.
1057 Alert readers will have noticed that these upper limits are NOT
1059 ""$vec1->Size()-1"" and ""$vec2->Size()-1"", as they would be for any
1060 other method in this module, but that these offsets may actually
1061 point to one position PAST THE END of the corresponding bit vector.
1062 This is necessary in order to make it possible to APPEND a given
1064 stretch of bits to the target bit vector instead of REPLACING
1065 something in it.
1066 For reasons of symmetry and generality, the same applies to the
1068 offset in the source bit vector, even though such an offset (one
1069 position past the end of the bit vector) does not serve any practical
1070 purpose there (but does not cause any harm either).
1071 (Actually this saves you from the need of testing for this special
1073 case, in certain circumstances.)
1074 Note that whenever the term ""$off1 + $len1"" exceeds the size
1076 ""$vec1->Size()"" of bit vector "$vec1" (or if ""$off2 + $len2""
1077 exceeds ""$vec2->Size()""), the corresponding length ("$len1" or
1078 "$len2", respectively) is automatically reduced internally so that
1079 ""$off1 + $len1 <= $vec1->Size()"" (and ""$off2 + $len2 <=
1080 $vec2->Size()"") holds.
1081 (Note that this does NOT alter the intended result, even though this
1083 may seem counter-intuitive at first!)
1084 This may even result in a length ("$len1" or "$len2") of zero.
1086 A length of zero for the interval in the SOURCE bit vector (""$len1
1088 == 0"") means that the indicated stretch of bits in the target bit
1089 vector (starting at position "$off2") is to be replaced by NOTHING,
1090 i.e., is to be DELETED.
1091 A length of zero for the interval in the TARGET bit vector ("$len2 ==
1093 0") means that NOTHING is replaced, and that the stretch of bits from
1094 the source bit vector is simply INSERTED into the target bit vector
1095 at the indicated position ("$off2").
1096 If both length parameters are zero, nothing is done at all.
1098 Note that in contrast to any other method in this module (especially
1100 ""Interval_Copy()"", ""Insert()"" and ""Delete()""), this method
1101 IMPLICITLY and AUTOMATICALLY adapts the length of the resulting bit
1102 vector as needed, as given by
1103 $size = $vec2->Size(); # before
1105 $size += $len1 - $len2; # after
1106 (The only other method in this module that changes the size of a bit
1108 vector is the method ""Resize()"".)
1109 In other words, replacing a given interval of bits in the target bit
1111 vector with a longer or shorter stretch of bits from the source bit
1112 vector, or simply inserting (""$len2 == 0"") a stretch of bits into
1113 or deleting (""$len1 == 0"") an interval of bits from the target bit
1114 vector will automatically increase or decrease, respectively, the
1115 size of the target bit vector accordingly.
1116 For the sake of generality, this may even result in a bit vector with
1118 a size of zero (containing no bits at all).
1119 This is also the reason why bit vectors of length zero are permitted
1121 in this module in the first place, starting with version 5.0.
1122 Finally, note that "$vec1" and "$vec2" may be identical, i.e., in-
1124 place processing is possible.
1125 (If you think about that for a while or if you look at the code, you
1127 will see that this is far from trivial!)
1128 • "if ($vector->is_empty())"
1130 Tests whether the given bit vector is empty, i.e., whether ALL of its
1132 bits are cleared (in the "off" state).
1133 In "big integer" arithmetic, this is equivalent to testing whether
1135 the number stored in the bit vector is zero ("0").
1136 Returns "true" ("1") if the bit vector is empty and "false" ("0")
1138 otherwise.
1139 Note that this method also returns "true" ("1") if the given bit
1141 vector has a length of zero, i.e., if it contains no bits at all.
1142 • "if ($vector->is_full())"
1144 Tests whether the given bit vector is full, i.e., whether ALL of its
1146 bits are set (in the "on" state).
1147 In "big integer" arithmetic, this is equivalent to testing whether
1149 the number stored in the bit vector is minus one ("-1").
1150 Returns "true" ("1") if the bit vector is full and "false" ("0")
1152 otherwise.
1153 If the given bit vector has a length of zero (i.e., if it contains no
1155 bits at all), this method returns "false" ("0").
1156 • "if ($vec1->equal($vec2))"
1158 Tests the two given bit vectors for equality.
1160 Returns "true" ("1") if the two bit vectors are exact copies of one
1162 another and "false" ("0") otherwise.
1163 • "$cmp = $vec1->Lexicompare($vec2);"
1165 Compares the two given bit vectors, which are regarded as UNSIGNED
1167 numbers in binary representation.
1168 The method returns ""-1"" if the first bit vector is smaller than the
1170 second bit vector, "0" if the two bit vectors are exact copies of one
1171 another and "1" if the first bit vector is greater than the second
1172 bit vector.
1173 • "$cmp = $vec1->Compare($vec2);"
1175 Compares the two given bit vectors, which are regarded as SIGNED
1177 numbers in binary representation.
1178 The method returns ""-1"" if the first bit vector is smaller than the
1180 second bit vector, "0" if the two bit vectors are exact copies of one
1181 another and "1" if the first bit vector is greater than the second
1182 bit vector.
1183 • "$string = $vector->to_Hex();"
1185 Returns a hexadecimal string representing the given bit vector.
1187 Note that this representation is quite compact, in that it only needs
1189 at most twice the number of bytes needed to store the bit vector
1190 itself, internally.
1191 Note also that since a hexadecimal digit is always worth four bits,
1193 the length of the resulting string is always a multiple of four bits,
1194 regardless of the true length (in bits) of the given bit vector.
1195 Finally, note that the LEAST significant hexadecimal digit is located
1197 at the RIGHT end of the resulting string, and the MOST significant
1198 digit at the LEFT end.
1199 • "$vector->from_Hex($string);"
1201 Allows to read in the contents of a bit vector from a hexadecimal
1203 string, such as returned by the method ""to_Hex()"" (see above).
1204 Remember that the least significant bits are always to the right of a
1206 hexadecimal string, and the most significant bits to the left.
1207 Therefore, the string is actually read in from right to left while
1208 the bit vector is filled accordingly, 4 bits at a time, starting with
1209 the least significant bits and going upward to the most significant
1210 bits.
1211 If the given string contains less hexadecimal digits than are needed
1213 to completely fill the given bit vector, the remaining (most
1214 significant) bits are all cleared.
1215 This also means that, even if the given string does not contain
1217 enough digits to completely fill the given bit vector, the previous
1218 contents of the bit vector are erased completely.
1219 If the given string is longer than it needs to fill the given bit
1221 vector, the superfluous characters are simply ignored.
1222 (In fact they are ignored completely - they are not even checked for
1224 proper syntax. See also below for more about that.)
1225 This behaviour is intentional so that you may read in the string
1227 representing one bit vector into another bit vector of different
1228 size, i.e., as much of it as will fit.
1229 If during the process of reading the given string any character is
1231 encountered which is not a hexadecimal digit, a fatal syntax error
1232 ensues ("input string syntax error").
1233 • "$string = $vector->to_Bin();"
1235 Returns a binary string representing the given bit vector.
1237 Example:
1239 $vector = Bit::Vector->new(8);
1241 $vector->Primes();
1242 $string = $vector->to_Bin();
1243 print "'$string'\n";
1244 This prints:
1246 '10101100'
1248 (Bits #7, #5, #3 and #2 are set.)
1250 Note that the LEAST significant bit is located at the RIGHT end of
1252 the resulting string, and the MOST significant bit at the LEFT end.
1253 • "$vector->from_Bin($string);"
1255 This method allows you to read in the contents of a bit vector from a
1257 binary string, such as returned by the method ""to_Bin()"" (see
1258 above).
1259 Note that this method assumes that the LEAST significant bit is
1261 located at the RIGHT end of the binary string, and the MOST
1262 significant bit at the LEFT end. Therefore, the string is actually
1263 read in from right to left while the bit vector is filled
1264 accordingly, one bit at a time, starting with the least significant
1265 bit and going upward to the most significant bit.
1266 If the given string contains less binary digits ("0" and "1") than
1268 are needed to completely fill the given bit vector, the remaining
1269 (most significant) bits are all cleared.
1270 This also means that, even if the given string does not contain
1272 enough digits to completely fill the given bit vector, the previous
1273 contents of the bit vector are erased completely.
1274 If the given string is longer than it needs to fill the given bit
1276 vector, the superfluous characters are simply ignored.
1277 (In fact they are ignored completely - they are not even checked for
1279 proper syntax. See also below for more about that.)
1280 This behaviour is intentional so that you may read in the string
1282 representing one bit vector into another bit vector of different
1283 size, i.e., as much of it as will fit.
1284 If during the process of reading the given string any character is
1286 encountered which is not either "0" or "1", a fatal syntax error
1287 ensues ("input string syntax error").
1288 • "$string = $vector->to_Dec();"
1290 This method returns a string representing the contents of the given
1292 bit vector converted to decimal (base 10).
1293 Note that this method assumes the given bit vector to be SIGNED (and
1295 to contain a number in two's complement binary representation).
1296 Consequently, whenever the most significant bit of the given bit
1298 vector is set, the number stored in it is regarded as being NEGATIVE.
1299 The resulting string can be fed into ""from_Dec()"" (see below) in
1301 order to copy the contents of this bit vector to another one (or to
1302 restore the contents of this one). This is not advisable, though,
1303 since this would be very inefficient (there are much more efficient
1304 methods for storing and copying bit vectors in this module).
1305 Note that such conversion from binary to decimal is inherently slow
1307 since the bit vector has to be repeatedly divided by 10 with
1308 remainder until the quotient becomes 0 (each remainder in turn
1309 represents a single decimal digit of the resulting string).
1310 This is also true for the implementation of this method in this
1312 module, even though a considerable effort has been made to speed it
1313 up: instead of repeatedly dividing by 10, the bit vector is
1314 repeatedly divided by the largest power of 10 that will fit into a
1315 machine word. The remainder is then repeatedly divided by 10 using
1316 only machine word arithmetics, which is much faster than dividing the
1317 whole bit vector ("divide and rule" principle).
1318 According to my own measurements, this resulted in an 8-fold speed
1320 increase over the straightforward approach.
1321 Still, conversion to decimal should be used only where absolutely
1323 necessary.
1324 Keep the resulting string stored in some variable if you need it
1326 again, instead of converting the bit vector all over again.
1327 Beware that if you set the configuration for overloaded operators to
1329 "output=decimal", this method will be called for every bit vector
1330 enclosed in double quotes!
1331 • "$vector->from_Dec($string);"
1333 This method allows you to convert a given decimal number, which may
1335 be positive or negative, into two's complement binary representation,
1336 which is then stored in the given bit vector.
1337 The decimal number should always be provided as a string, to avoid
1339 possible truncation (due to the limited precision of integers in
1340 Perl) or formatting (due to Perl's use of scientific notation for
1341 large numbers), which would lead to errors.
1342 If the binary representation of the given decimal number is too big
1344 to fit into the given bit vector (if the given bit vector does not
1345 contain enough bits to hold it), a fatal "numeric overflow error"
1346 occurs.
1347 If the input string contains other characters than decimal digits
1349 ("0-9") and an optional leading sign (""+"" or ""-""), a fatal "input
1350 string syntax error" occurs.
1351 Beware that large positive numbers which cause the most significant
1353 bit to be set (e.g. "255" in a bit vector with 8 bits) will be
1354 printed as negative numbers when converted back to decimal using the
1355 method "to_Dec()" (e.g. "-1", in our example), because numbers with
1356 the most significant bit set are considered to be negative in two's
1357 complement binary representation.
1358 Note also that while it is possible to thusly enter negative numbers
1360 as large positive numbers (e.g. "255" for "-1" in a bit vector with 8
1361 bits), the contrary isn't, i.e., you cannot enter "-255" for "+1", in
1362 our example. A fatal "numeric overflow error" will occur if you try
1363 to do so.
1364 If possible program abortion is unwanted or intolerable, use
1366 ""eval"", like this:
1367 eval { $vector->from_Dec("1152921504606846976"); };
1369 if ($@)
1370 {
1371 # an error occurred
1372 }
1373 There are four possible error messages:
1375 if ($@ =~ /item is not a string/)
1377 if ($@ =~ /input string syntax error/)
1379 if ($@ =~ /numeric overflow error/)
1381 if ($@ =~ /unable to allocate memory/)
1383 Note that the conversion from decimal to binary is costly in terms of
1385 processing time, since a lot of multiplications have to be carried
1386 out (in principle, each decimal digit must be multiplied with the
1387 binary representation of the power of 10 corresponding to its
1388 position in the decimal number, i.e., 1, 10, 100, 1000, 10000 and so
1389 on).
1390 This is not as time consuming as the opposite conversion, from binary
1392 to decimal (where successive divisions have to be carried out, which
1393 are even more expensive than multiplications), but still noticeable.
1394 Again (as in the case of ""to_Dec()""), the implementation of this
1396 method in this module uses the principle of "divide and rule" in
1397 order to speed up the conversion, i.e., as many decimal digits as
1398 possible are first accumulated (converted) in a machine word and only
1399 then stored in the given bit vector.
1400 Even so, use this method only where absolutely necessary if speed is
1402 an important consideration in your application.
1403 Beware that if you set the configuration for overloaded operators to
1405 "input=decimal", this method will be called for every scalar operand
1406 you use!
1407 • "$string = $vector->to_Enum();"
1409 Converts the given bit vector or set into an enumeration of single
1411 indices and ranges of indices (".newsrc" style), representing the
1412 bits that are set ("1") in the bit vector.
1413 Example:
1415 $vector = Bit::Vector->new(20);
1417 $vector->Bit_On(2);
1418 $vector->Bit_On(3);
1419 $vector->Bit_On(11);
1420 $vector->Interval_Fill(5,7);
1421 $vector->Interval_Fill(13,19);
1422 print "'", $vector->to_Enum(), "'\n";
1423 which prints
1425 '2,3,5-7,11,13-19'
1427 If the given bit vector is empty, the resulting string will also be
1429 empty.
1430 Note, by the way, that the above example can also be written a little
1432 handier, perhaps, as follows:
1433 Bit::Vector->Configuration("out=enum");
1435 $vector = Bit::Vector->new(20);
1436 $vector->Index_List_Store(2,3,5,6,7,11,13,14,15,16,17,18,19);
1437 print "'$vector'\n";
1438 • "$vector->from_Enum($string);"
1440 This method first empties the given bit vector and then tries to set
1442 the bits and ranges of bits specified in the given string.
1443 The string "$string" must only contain unsigned integers or ranges of
1445 integers (two unsigned integers separated by a dash "-"), separated
1446 by commas (",").
1447 All other characters are disallowed (including white space!) and
1449 will lead to a fatal "input string syntax error".
1450 In each range, the first integer (the lower limit of the range) must
1452 always be less than or equal to the second integer (the upper limit),
1453 or a fatal "minimum > maximum index" error occurs.
1454 All integers must lie in the permitted range for the given bit
1456 vector, i.e., they must lie between "0" and ""$vector->Size()-1"".
1457 If this condition is not met, a fatal "index out of range" error
1459 occurs.
1460 If possible program abortion is unwanted or intolerable, use
1462 ""eval"", like this:
1463 eval { $vector->from_Enum("2,3,5-7,11,13-19"); };
1465 if ($@)
1466 {
1467 # an error occurred
1468 }
1469 There are four possible error messages:
1471 if ($@ =~ /item is not a string/)
1473 if ($@ =~ /input string syntax error/)
1475 if ($@ =~ /index out of range/)
1477 if ($@ =~ /minimum > maximum index/)
1479 Note that the order of the indices and ranges is irrelevant, i.e.,
1481 eval { $vector->from_Enum("11,5-7,3,13-19,2"); };
1483 results in the same vector as in the example above.
1485 Ranges and indices may also overlap.
1487 This is because each (single) index in the string is passed to the
1489 method ""Bit_On()"", internally, and each range to the method
1490 ""Interval_Fill()"".
1491 This means that the resulting bit vector is just the union of all the
1493 indices and ranges specified in the given string.
1494 • "$vector->Bit_Off($index);"
1496 Clears the bit with index "$index" in the given vector.
1498 • "$vector->Bit_On($index);"
1500 Sets the bit with index "$index" in the given vector.
1502 • "$vector->bit_flip($index)"
1504 Flips (i.e., complements) the bit with index "$index" in the given
1506 vector.
1507 Moreover, this method returns the NEW state of the bit in question,
1509 i.e., it returns "0" if the bit is cleared or "1" if the bit is set
1510 (AFTER flipping it).
1511 • "if ($vector->bit_test($index))"
1513 "if ($vector->contains($index))"
1515 Returns the current state of the bit with index "$index" in the given
1517 vector, i.e., returns "0" if it is cleared (in the "off" state) or
1518 "1" if it is set (in the "on" state).
1519 • "$vector->Bit_Copy($index,$bit);"
1521 Sets the bit with index "$index" in the given vector either to "0" or
1523 "1" depending on the boolean value "$bit".
1524 • "$vector->LSB($bit);"
1526 Allows you to set the least significant bit in the given bit vector
1528 to the value given by the boolean parameter "$bit".
1529 This is a (faster) shortcut for ""$vector->Bit_Copy(0,$bit);"".
1531 • "$vector->MSB($bit);"
1533 Allows you to set the most significant bit in the given bit vector to
1535 the value given by the boolean parameter "$bit".
1536 This is a (faster) shortcut for
1538 ""$vector->Bit_Copy($vector->Size()-1,$bit);"".
1539 • "$bit = $vector->lsb();"
1541 Returns the least significant bit of the given bit vector.
1543 This is a (faster) shortcut for ""$bit = $vector->bit_test(0);"".
1545 • "$bit = $vector->msb();"
1547 Returns the most significant bit of the given bit vector.
1549 This is a (faster) shortcut for ""$bit =
1551 $vector->bit_test($vector->Size()-1);"".
1552 • "$carry_out = $vector->rotate_left();"
1554 carry MSB vector: LSB
1556 out:
1557 +---+ +---+---+---+--- ---+---+---+---+
1558 | | <---+--- | | | | ... | | | | <---+
1559 +---+ | +---+---+---+--- ---+---+---+---+ |
1560 | |
1561 +------------------------------------------------+
1562 The least significant bit (LSB) is the bit with index "0", the most
1564 significant bit (MSB) is the bit with index ""$vector->Size()-1"".
1565 • "$carry_out = $vector->rotate_right();"
1567 MSB vector: LSB carry
1569 out:
1570 +---+---+---+--- ---+---+---+---+ +---+
1571 +---> | | | | ... | | | | ---+---> | |
1572 | +---+---+---+--- ---+---+---+---+ | +---+
1573 | |
1574 +------------------------------------------------+
1575 The least significant bit (LSB) is the bit with index "0", the most
1577 significant bit (MSB) is the bit with index ""$vector->Size()-1"".
1578 • "$carry_out = $vector->shift_left($carry_in);"
1580 carry MSB vector: LSB carry
1582 out: in:
1583 +---+ +---+---+---+--- ---+---+---+---+ +---+
1584 | | <--- | | | | ... | | | | <--- | |
1585 +---+ +---+---+---+--- ---+---+---+---+ +---+
1586 The least significant bit (LSB) is the bit with index "0", the most
1588 significant bit (MSB) is the bit with index ""$vector->Size()-1"".
1589 • "$carry_out = $vector->shift_right($carry_in);"
1591 carry MSB vector: LSB carry
1593 in: out:
1594 +---+ +---+---+---+--- ---+---+---+---+ +---+
1595 | | ---> | | | | ... | | | | ---> | |
1596 +---+ +---+---+---+--- ---+---+---+---+ +---+
1597 The least significant bit (LSB) is the bit with index "0", the most
1599 significant bit (MSB) is the bit with index ""$vector->Size()-1"".
1600 • "$vector->Move_Left($bits);"
1602 Shifts the given bit vector left by "$bits" bits, i.e., inserts
1604 "$bits" new bits at the lower end (least significant bit) of the bit
1605 vector, moving all other bits up by "$bits" places, thereby losing
1606 the "$bits" most significant bits.
1607 The inserted new bits are all cleared (set to the "off" state).
1609 This method does nothing if "$bits" is equal to zero.
1611 Beware that the whole bit vector is cleared WITHOUT WARNING if
1613 "$bits" is greater than or equal to the size of the given bit vector!
1614 In fact this method is equivalent to
1616 for ( $i = 0; $i < $bits; $i++ ) { $vector->shift_left(0); }
1618 except that it is much more efficient (for "$bits" greater than or
1620 equal to the number of bits in a machine word on your system) than
1621 this straightforward approach.
1622 • "$vector->Move_Right($bits);"
1624 Shifts the given bit vector right by "$bits" bits, i.e., deletes the
1626 "$bits" least significant bits of the bit vector, moving all other
1627 bits down by "$bits" places, thereby creating "$bits" new bits at the
1628 upper end (most significant bit) of the bit vector.
1629 These new bits are all cleared (set to the "off" state).
1631 This method does nothing if "$bits" is equal to zero.
1633 Beware that the whole bit vector is cleared WITHOUT WARNING if
1635 "$bits" is greater than or equal to the size of the given bit vector!
1636 In fact this method is equivalent to
1638 for ( $i = 0; $i < $bits; $i++ ) { $vector->shift_right(0); }
1640 except that it is much more efficient (for "$bits" greater than or
1642 equal to the number of bits in a machine word on your system) than
1643 this straightforward approach.
1644 • "$vector->Insert($offset,$bits);"
1646 This method inserts "$bits" fresh new bits at position "$offset" in
1648 the given bit vector.
1649 The "$bits" most significant bits are lost, and all bits starting
1651 with bit number "$offset" up to and including bit number
1652 ""$vector->Size()-$bits-1"" are moved up by "$bits" places.
1653 The now vacant "$bits" bits starting at bit number "$offset" (up to
1655 and including bit number ""$offset+$bits-1"") are then set to zero
1656 (cleared).
1657 Note that this method does NOT increase the size of the given bit
1659 vector, i.e., the bit vector is NOT extended at its upper end to
1660 "rescue" the "$bits" uppermost (most significant) bits - instead,
1661 these bits are lost forever.
1662 If you don't want this to happen, you have to increase the size of
1664 the given bit vector EXPLICITLY and BEFORE you perform the "Insert"
1665 operation, with a statement such as the following:
1666 $vector->Resize($vector->Size() + $bits);
1668 Or use the method ""Interval_Substitute()"" instead of ""Insert()"",
1670 which performs automatic growing and shrinking of its target bit
1671 vector.
1672 Note also that "$offset" must lie in the permitted range between "0"
1674 and ""$vector->Size()-1"", or a fatal "offset out of range" error
1675 will occur.
1676 If the term ""$offset + $bits"" exceeds ""$vector->Size()-1"", all
1678 the bits starting with bit number "$offset" up to bit number
1679 ""$vector->Size()-1"" are simply cleared.
1680 • "$vector->Delete($offset,$bits);"
1682 This method deletes, i.e., removes the bits starting at position
1684 "$offset" up to and including bit number ""$offset+$bits-1"" from the
1685 given bit vector.
1686 The remaining uppermost bits (starting at position ""$offset+$bits""
1688 up to and including bit number ""$vector->Size()-1"") are moved down
1689 by "$bits" places.
1690 The now vacant uppermost (most significant) "$bits" bits are then set
1692 to zero (cleared).
1693 Note that this method does NOT decrease the size of the given bit
1695 vector, i.e., the bit vector is NOT clipped at its upper end to "get
1696 rid of" the vacant "$bits" uppermost bits.
1697 If you don't want this, i.e., if you want the bit vector to shrink
1699 accordingly, you have to do so EXPLICITLY and AFTER the "Delete"
1700 operation, with a couple of statements such as these:
1701 $size = $vector->Size();
1703 if ($bits > $size) { $bits = $size; }
1704 $vector->Resize($size - $bits);
1705 Or use the method ""Interval_Substitute()"" instead of ""Delete()"",
1707 which performs automatic growing and shrinking of its target bit
1708 vector.
1709 Note also that "$offset" must lie in the permitted range between "0"
1711 and ""$vector->Size()-1"", or a fatal "offset out of range" error
1712 will occur.
1713 If the term ""$offset + $bits"" exceeds ""$vector->Size()-1"", all
1715 the bits starting with bit number "$offset" up to bit number
1716 ""$vector->Size()-1"" are simply cleared.
1717 • "$carry = $vector->increment();"
1719 This method increments the given bit vector.
1721 Note that this method regards bit vectors as being unsigned, i.e.,
1723 the largest possible positive number is directly followed by the
1724 smallest possible (or greatest possible, speaking in absolute terms)
1725 negative number:
1726 before: 2 ^ (b-1) - 1 (= "0111...1111")
1728 after: 2 ^ (b-1) (= "1000...0000")
1729 where ""b"" is the number of bits of the given bit vector.
1731 The method returns "false" ("0") in all cases except when a carry
1733 over occurs (in which case it returns "true", i.e., "1"), which
1734 happens when the number "1111...1111" is incremented, which gives
1735 "0000...0000" plus a carry over to the next higher (binary) digit.
1736 This can be used for the terminating condition of a "while" loop, for
1738 instance, in order to cycle through all possible values the bit
1739 vector can assume.
1740 • "$carry = $vector->decrement();"
1742 This method decrements the given bit vector.
1744 Note that this method regards bit vectors as being unsigned, i.e.,
1746 the smallest possible (or greatest possible, speaking in absolute
1747 terms) negative number is directly followed by the largest possible
1748 positive number:
1749 before: 2 ^ (b-1) (= "1000...0000")
1751 after: 2 ^ (b-1) - 1 (= "0111...1111")
1752 where ""b"" is the number of bits of the given bit vector.
1754 The method returns "false" ("0") in all cases except when a carry
1756 over occurs (in which case it returns "true", i.e., "1"), which
1757 happens when the number "0000...0000" is decremented, which gives
1758 "1111...1111" minus a carry over to the next higher (binary) digit.
1759 This can be used for the terminating condition of a "while" loop, for
1761 instance, in order to cycle through all possible values the bit
1762 vector can assume.
1763 • "$overflow = $vec2->inc($vec1);"
1765 This method copies the contents of bit vector "$vec1" to bit vector
1767 "$vec2" and increments the copy (not the original).
1768 If by incrementing the number its sign becomes invalid, the return
1770 value ("overflow" flag) will be true ("1"), or false ("0") if not.
1771 (See the description of the method "add()" below for a more in-depth
1772 explanation of what "overflow" means).
1773 Note that in-place operation is also possible, i.e., "$vec1" and
1775 "$vec2" may be identical.
1776 • "$overflow = $vec2->dec($vec1);"
1778 This method copies the contents of bit vector "$vec1" to bit vector
1780 "$vec2" and decrements the copy (not the original).
1781 If by decrementing the number its sign becomes invalid, the return
1783 value ("overflow" flag) will be true ("1"), or false ("0") if not.
1784 (See the description of the method "subtract()" below for a more in-
1785 depth explanation of what "overflow" means).
1786 Note that in-place operation is also possible, i.e., "$vec1" and
1788 "$vec2" may be identical.
1789 • "$carry = $vec3->add($vec1,$vec2,$carry);"
1791 "($carry,$overflow) = $vec3->add($vec1,$vec2,$carry);"
1793 This method adds the two numbers contained in bit vector "$vec1" and
1795 "$vec2" with carry "$carry" and stores the result in bit vector
1796 "$vec3".
1797 I.e.,
1799 $vec3 = $vec1 + $vec2 + $carry
1800 Note that the "$carry" parameter is a boolean value, i.e., only its
1802 least significant bit is taken into account. (Think of it as though
1803 ""$carry &= 1;"" was always executed internally.)
1804 In scalar context, the method returns a boolean value which indicates
1806 if a carry over (to the next higher bit position) has occured. In
1807 list context, the method returns the carry and the overflow flag (in
1808 this order).
1809 The overflow flag is true ("1") if the sign (i.e., the most
1811 significant bit) of the result is wrong. This can happen when adding
1812 two very large positive numbers or when adding two (by their absolute
1813 value) very large negative numbers. See also further below.
1814 The carry in- and output is needed mainly for cascading, i.e., to add
1816 numbers that are fragmented into several pieces.
1817 Example:
1819 # initialize
1821 for ( $i = 0; $i < $n; $i++ )
1823 {
1824 $a[$i] = Bit::Vector->new($bits);
1825 $b[$i] = Bit::Vector->new($bits);
1826 $c[$i] = Bit::Vector->new($bits);
1827 }
1828 # fill @a and @b
1830 # $a[ 0 ] is low order part,
1832 # $a[$n-1] is high order part,
1833 # and same for @b
1834 # add
1836 $carry = 0;
1838 for ( $i = 0; $i < $n; $i++ )
1839 {
1840 $carry = $c[$i]->add($a[$i],$b[$i],$carry);
1841 }
1842 Note that it makes no difference to this method whether the numbers
1844 in "$vec1" and "$vec2" are unsigned or signed (i.e., in two's
1845 complement binary representation).
1846 Note however that the return value (carry flag) is not meaningful
1848 when the numbers are SIGNED.
1849 Moreover, when the numbers are signed, a special type of error can
1851 occur which is commonly called an "overflow error".
1852 An overflow error occurs when the sign of the result (its most
1854 significant bit) is flipped (i.e., falsified) by a carry over from
1855 the next-lower bit position ("MSB-1").
1856 In fact matters are a bit more complicated than that: the overflow
1858 flag is set to "true" whenever there is a carry over from bit
1859 position MSB-1 to the most significant bit (MSB) but no carry over
1860 from the MSB to the output carry flag, or vice-versa, i.e., when
1861 there is no carry over from bit position MSB-1 to the most
1862 significant bit (MSB) but a carry over to the output carry flag.
1863 Thus the overflow flag is the result of an exclusive-or operation
1865 between incoming and outgoing carry over at the most significant bit
1866 position.
1867 • "$carry = $vec3->subtract($vec1,$vec2,$carry);"
1869 "($carry,$overflow) = $vec3->subtract($vec1,$vec2,$carry);"
1871 This method subtracts the two numbers contained in bit vector "$vec1"
1873 and "$vec2" with carry "$carry" and stores the result in bit vector
1874 "$vec3".
1875 I.e.,
1877 $vec3 = $vec1 - $vec2 - $carry
1878 Note that the "$carry" parameter is a boolean value, i.e., only its
1880 least significant bit is taken into account. (Think of it as though
1881 ""$carry &= 1;"" was always executed internally.)
1882 In scalar context, the method returns a boolean value which indicates
1884 if a carry over (to the next higher bit position) has occured. In
1885 list context, the method returns the carry and the overflow flag (in
1886 this order).
1887 The overflow flag is true ("1") if the sign (i.e., the most
1889 significant bit) of the result is wrong. This can happen when
1890 subtracting a very large negative number from a very large positive
1891 number or vice-versa. See also further below.
1892 The carry in- and output is needed mainly for cascading, i.e., to
1894 subtract numbers that are fragmented into several pieces.
1895 Example:
1897 # initialize
1899 for ( $i = 0; $i < $n; $i++ )
1901 {
1902 $a[$i] = Bit::Vector->new($bits);
1903 $b[$i] = Bit::Vector->new($bits);
1904 $c[$i] = Bit::Vector->new($bits);
1905 }
1906 # fill @a and @b
1908 # $a[ 0 ] is low order part,
1910 # $a[$n-1] is high order part,
1911 # and same for @b
1912 # subtract
1914 $carry = 0;
1916 for ( $i = 0; $i < $n; $i++ )
1917 {
1918 $carry = $c[$i]->subtract($a[$i],$b[$i],$carry);
1919 }
1920 Note that it makes no difference to this method whether the numbers
1922 in "$vec1" and "$vec2" are unsigned or signed (i.e., in two's
1923 complement binary representation).
1924 Note however that the return value (carry flag) is not meaningful
1926 when the numbers are SIGNED.
1927 Moreover, when the numbers are signed, a special type of error can
1929 occur which is commonly called an "overflow error".
1930 An overflow error occurs when the sign of the result (its most
1932 significant bit) is flipped (i.e., falsified) by a carry over from
1933 the next-lower bit position ("MSB-1").
1934 In fact matters are a bit more complicated than that: the overflow
1936 flag is set to "true" whenever there is a carry over from bit
1937 position MSB-1 to the most significant bit (MSB) but no carry over
1938 from the MSB to the output carry flag, or vice-versa, i.e., when
1939 there is no carry over from bit position MSB-1 to the most
1940 significant bit (MSB) but a carry over to the output carry flag.
1941 Thus the overflow flag is the result of an exclusive-or operation
1943 between incoming and outgoing carry over at the most significant bit
1944 position.
1945 • "$vec2->Neg($vec1);"
1947 "$vec2->Negate($vec1);"
1949 This method calculates the two's complement of the number in bit
1951 vector "$vec1" and stores the result in bit vector "$vec2".
1952 Calculating the two's complement of a given number in binary
1954 representation consists of inverting all bits and incrementing the
1955 result by one.
1956 This is the same as changing the sign of the given number from ""+""
1958 to ""-"" or vice-versa. In other words, applying this method twice on
1959 a given number yields the original number again.
1960 Note that in-place processing is also possible, i.e., "$vec1" and
1962 "$vec2" may be identical.
1963 Most importantly, beware that this method produces a counter-
1965 intuitive result if the number contained in bit vector "$vec1" is "2
1966 ^ (n-1)" (i.e., "1000...0000"), where ""n"" is the number of bits the
1967 given bit vector contains: The negated value of this number is the
1968 number itself!
1969 • "$vec2->Abs($vec1);"
1971 "$vec2->Absolute($vec1);"
1973 Depending on the sign (i.e., the most significant bit) of the number
1975 in bit vector "$vec1", the contents of bit vector "$vec1" are copied
1976 to bit vector "$vec2" either with the method ""Copy()"" (if the
1977 number in bit vector "$vec1" is positive), or with ""Negate()"" (if
1978 the number in bit vector "$vec1" is negative).
1979 In other words, this method calculates the absolute value of the
1981 number in bit vector "$vec1" and stores the result in bit vector
1982 "$vec2".
1983 Note that in-place processing is also possible, i.e., "$vec1" and
1985 "$vec2" may be identical.
1986 Most importantly, beware that this method produces a counter-
1988 intuitive result if the number contained in bit vector "$vec1" is "2
1989 ^ (n-1)" (i.e., "1000...0000"), where ""n"" is the number of bits the
1990 given bit vector contains: The absolute value of this number is the
1991 number itself, even though this number is still negative by
1992 definition (the most significant bit is still set)!
1993 • "$sign = $vector->Sign();"
1995 This method returns "0" if all bits in the given bit vector are
1997 cleared, i.e., if the given bit vector contains the number "0", or if
1998 the given bit vector has a length of zero (contains no bits at all).
1999 If not all bits are cleared, this method returns ""-1"" if the most
2001 significant bit is set (i.e., if the bit vector contains a negative
2002 number), or "1" otherwise (i.e., if the bit vector contains a
2003 positive number).
2004 • "$vec3->Multiply($vec1,$vec2);"
2006 This method multiplies the two numbers contained in bit vector
2008 "$vec1" and "$vec2" and stores the result in bit vector "$vec3".
2009 Note that this method regards its arguments as SIGNED.
2011 If you want to make sure that a large number can never be treated as
2013 being negative by mistake, make your bit vectors at least one bit
2014 longer than the largest number you wish to represent, right from the
2015 start, or proceed as follows:
2016 $msb1 = $vec1->msb();
2018 $msb2 = $vec2->msb();
2019 $vec1->Resize($vec1->Size()+1);
2020 $vec2->Resize($vec2->Size()+1);
2021 $vec3->Resize($vec3->Size()+1);
2022 $vec1->MSB($msb1);
2023 $vec2->MSB($msb2);
2024 $vec3->Multiply($vec1,$vec2);
2025 Note also that all three bit vector arguments must in principle obey
2027 the rule of matching sizes, but that the bit vector "$vec3" may be
2028 larger than the two factors "$vec1" and "$vec2".
2029 In fact multiplying two binary numbers with ""n"" bits may yield a
2031 result which is at most ""2n"" bits long.
2032 Therefore, it is usually a good idea to let bit vector "$vec3" have
2034 twice the size of bit vector "$vec1" and "$vec2", unless you are
2035 absolutely sure that the result will fit into a bit vector of the
2036 same size as the two factors.
2037 If you are wrong, a fatal "numeric overflow error" will occur.
2039 Finally, note that in-place processing is possible, i.e., "$vec3" may
2041 be identical with "$vec1" or "$vec2", or both.
2042 • "$quot->Divide($vec1,$vec2,$rest);"
2044 This method divides the two numbers contained in bit vector "$vec1"
2046 and "$vec2" and stores the quotient in bit vector "$quot" and the
2047 remainder in bit vector "$rest".
2048 I.e.,
2050 $quot = $vec1 / $vec2; # div
2051 $rest = $vec1 % $vec2; # mod
2052 Therefore, "$quot" and "$rest" must be two DISTINCT bit vectors, or a
2054 fatal "result vector(s) must be distinct" error will occur.
2055 Note also that a fatal "division by zero error" will occur if "$vec2"
2057 is equal to zero.
2058 Note further that this method regards its arguments as SIGNED.
2060 If you want to make sure that a large number can never be treated as
2062 being negative by mistake, make your bit vectors at least one bit
2063 longer than the largest number you wish to represent, right from the
2064 start, or proceed as follows:
2065 $msb1 = $vec1->msb();
2067 $msb2 = $vec2->msb();
2068 $vec1->Resize($vec1->Size()+1);
2069 $vec2->Resize($vec2->Size()+1);
2070 $quot->Resize($quot->Size()+1);
2071 $rest->Resize($rest->Size()+1);
2072 $vec1->MSB($msb1);
2073 $vec2->MSB($msb2);
2074 $quot->Divide($vec1,$vec2,$rest);
2075 Finally, note that in-place processing is possible, i.e., "$quot" may
2077 be identical with "$vec1" or "$vec2" or both, and "$rest" may also be
2078 identical with "$vec1" or "$vec2" or both, as long as "$quot" and
2079 "$rest" are distinct. (!)
2080 • "$vecgcd->GCD($veca,$vecb);"
2082 This method calculates the "Greatest Common Divisor" of the two
2084 numbers contained in bit vector "$veca" and "$vecb" and stores the
2085 result in bit vector "$vecgcd".
2086 The method uses Euklid's algorithm internally:
2088 int GCD(int a, int b)
2090 {
2091 int t;
2092 while (b != 0)
2094 {
2095 t = a % b; /* = remainder of (a div b) */
2096 a = b;
2097 b = t;
2098 }
2099 return(a);
2100 }
2101 Note that "GCD(z,0) == GCD(0,z) == z".
2103 • "$vecgcd->GCD($vecx,$vecy,$veca,$vecb);"
2105 This variant of the "GCD" method calculates the "Greatest Common
2107 Divisor" of the two numbers contained in bit vector "$veca" and
2108 "$vecb" and stores the result in bit vector "$vecgcd".
2109 Moreover, it determines the two factors which are necessary in order
2111 to represent the greatest common divisor as a linear combination of
2112 its two arguments, i.e., the two factors "x" and "y" so that
2113 "GCD(a,b) == x * a + y * b", and stores them in bit vector "$vecx"
2114 and "$vecy", respectively.
2115 For example:
2117 a = 2322
2119 b = 654
2120 GCD( 2322, 654 ) == 6
2122 x = 20
2124 y = -71
2125 20 * 2322 - 71 * 654 == 6
2127 Please see http://www.cut-the-knot.org/blue/extension.shtml for an
2129 explanation of how this extension of Euklid's algorithm works.
2130 • "$vec3->Power($vec1,$vec2);"
2132 This method calculates the exponentiation of base "$vec1" elevated to
2134 the "$vec2" power, i.e., ""$vec1 ** $vec2"", and stores the result in
2135 bit vector "$vec3".
2136 The method uses an efficient divide-and-conquer algorithm:
2138 Suppose the exponent is (decimal) 13, for example. The binary
2140 representation of this exponent is "1101".
2141 This means we want to calculate
2143 $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 * $vec1 *
2145 $vec1 * $vec1 * $vec1 * $vec1 *
2146 $vec1
2147 That is, "$vec1" multiplied with itself 13 times. The grouping into
2149 lines above is no coincidence. The first line comprises 8 factors,
2150 the second contains 4, and the last line just one. This just happens
2151 to be the binary representation of 13. ";-)"
2152 We then calculate a series of squares (of squares of squares...) of
2154 the base, i.e.,
2155 $power[0] = $vec1;
2157 $power[1] = $vec1 * $vec1;
2158 $power[2] = $power[1] * $power[1];
2159 $power[3] = $power[2] * $power[2];
2160 etc.
2161 To calculate the power of our example, we simply initialize our
2163 result with 1 and consecutively multiply it with the items of the
2164 series of powers we just calculated, if the corresponding bit of the
2165 binary representation of the exponent is set:
2166 $result = 1;
2168 $result *= $power[0] if ($vec2 & 1);
2169 $result *= $power[1] if ($vec2 & 2);
2170 $result *= $power[2] if ($vec2 & 4);
2171 $result *= $power[3] if ($vec2 & 8);
2172 etc.
2173 The bit vector "$vec3" must be of the same size as the base "$vec1"
2175 or greater. "$vec3" and "$vec1" may be the same vector (i.e., in-
2176 place calculation as in ""$vec1 **= $vec2;"" is possible), but
2177 "$vec3" and "$vec2" must be distinct. Finally, the exponent "$vec2"
2178 must be positive. A fatal error occurs if any of these conditions is
2179 not met.
2180 • "$vector->Block_Store($buffer);"
2182 This method allows you to load the contents of a given bit vector in
2184 one go.
2185 This is useful when you store the contents of a bit vector in a file,
2187 for instance (using method ""Block_Read()""), and when you want to
2188 restore the previously saved bit vector.
2189 For this, "$buffer" MUST be a string (NO automatic conversion from
2191 numeric to string is provided here as would normally in Perl!)
2192 containing the bit vector in "low order byte first" order.
2193 If the given string is shorter than what is needed to completely fill
2195 the given bit vector, the remaining (most significant) bytes of the
2196 bit vector are filled with zeros, i.e., the previous contents of the
2197 bit vector are always erased completely.
2198 If the given string is longer than what is needed to completely fill
2200 the given bit vector, the superfluous bytes are simply ignored.
2201 See "sysread" in perlfunc for how to read in the contents of
2203 "$buffer" from a file prior to passing it to this method.
2204 • "$buffer = $vector->Block_Read();"
2206 This method allows you to export the contents of a given bit vector
2208 in one block.
2209 This is useful when you want to save the contents of a bit vector for
2211 later, for instance in a file.
2212 The advantage of this method is that it allows you to do so in the
2214 compactest possible format, in binary.
2215 The method returns a Perl string which contains an exact copy of the
2217 contents of the given bit vector in "low order byte first" order.
2218 See "syswrite" in perlfunc for how to write the data from this string
2220 to a file.
2221 • "$size = $vector->Word_Size();"
2223 Each bit vector is internally organized as an array of machine words.
2225 The methods whose names begin with "Word_" allow you to access this
2227 internal array of machine words.
2228 Note that because the size of a machine word may vary from system to
2230 system, these methods are inherently MACHINE-DEPENDENT!
2231 Therefore, DO NOT USE these methods unless you are absolutely certain
2233 that portability of your code is not an issue!
2234 You have been warned!
2236 To be machine-independent, use the methods whose names begin with
2238 ""Chunk_"" instead, with chunk sizes no greater than 32 bits.
2239 The method ""Word_Size()"" returns the number of machine words that
2241 the internal array of words of the given bit vector contains.
2242 This is similar in function to the term ""scalar(@array)"" for a Perl
2244 array.
2245 • "$vector->Word_Store($offset,$word);"
2247 This method allows you to store a given value "$word" at a given
2249 position "$offset" in the internal array of words of the given bit
2250 vector.
2251 Note that "$offset" must lie in the permitted range between "0" and
2253 ""$vector->Word_Size()-1"", or a fatal "offset out of range" error
2254 will occur.
2255 This method is similar in function to the expression
2257 ""$array[$offset] = $word;"" for a Perl array.
2258 • "$word = $vector->Word_Read($offset);"
2260 This method allows you to access the value of a given machine word at
2262 position "$offset" in the internal array of words of the given bit
2263 vector.
2264 Note that "$offset" must lie in the permitted range between "0" and
2266 ""$vector->Word_Size()-1"", or a fatal "offset out of range" error
2267 will occur.
2268 This method is similar in function to the expression ""$word =
2270 $array[$offset];"" for a Perl array.
2271 • "$vector->Word_List_Store(@words);"
2273 This method allows you to store a list of values "@words" in the
2275 internal array of machine words of the given bit vector.
2276 Thereby the LEFTMOST value in the list ("$words[0]") is stored in the
2278 LEAST significant word of the internal array of words (the one with
2279 offset "0"), the next value from the list ("$words[1]") is stored in
2280 the word with offset "1", and so on, as intuitively expected.
2281 If the list "@words" contains fewer elements than the internal array
2283 of words of the given bit vector contains machine words, the
2284 remaining (most significant) words are filled with zeros.
2285 If the list "@words" contains more elements than the internal array
2287 of words of the given bit vector contains machine words, the
2288 superfluous values are simply ignored.
2289 This method is comparable in function to the expression ""@array =
2291 @words;"" for a Perl array.
2292 • "@words = $vector->Word_List_Read();"
2294 This method allows you to retrieve the internal array of machine
2296 words of the given bit vector all at once.
2297 Thereby the LEFTMOST value in the returned list ("$words[0]") is the
2299 LEAST significant word from the given bit vector, and the RIGHTMOST
2300 value in the returned list ("$words[$#words]") is the MOST
2301 significant word of the given bit vector.
2302 This method is similar in function to the expression ""@words =
2304 @array;"" for a Perl array.
2305 • "$vector->Word_Insert($offset,$count);"
2307 This method inserts "$count" empty new machine words at position
2309 "$offset" in the internal array of words of the given bit vector.
2310 The "$count" most significant words are lost, and all words starting
2312 with word number "$offset" up to and including word number
2313 ""$vector->Word_Size()-$count-1"" are moved up by "$count" places.
2314 The now vacant "$count" words starting at word number "$offset" (up
2316 to and including word number ""$offset+$count-1"") are then set to
2317 zero (cleared).
2318 Note that this method does NOT increase the size of the given bit
2320 vector, i.e., the bit vector is NOT extended at its upper end to
2321 "rescue" the "$count" uppermost (most significant) words - instead,
2322 these words are lost forever.
2323 If you don't want this to happen, you have to increase the size of
2325 the given bit vector EXPLICITLY and BEFORE you perform the "Insert"
2326 operation, with a statement such as the following:
2327 $vector->Resize($vector->Size() + $count * Bit::Vector->Word_Bits());
2329 Note also that "$offset" must lie in the permitted range between "0"
2331 and ""$vector->Word_Size()-1"", or a fatal "offset out of range"
2332 error will occur.
2333 If the term ""$offset + $count"" exceeds ""$vector->Word_Size()-1"",
2335 all the words starting with word number "$offset" up to word number
2336 ""$vector->Word_Size()-1"" are simply cleared.
2337 • "$vector->Word_Delete($offset,$count);"
2339 This method deletes, i.e., removes the words starting at position
2341 "$offset" up to and including word number ""$offset+$count-1"" from
2342 the internal array of machine words of the given bit vector.
2343 The remaining uppermost words (starting at position
2345 ""$offset+$count"" up to and including word number
2346 ""$vector->Word_Size()-1"") are moved down by "$count" places.
2347 The now vacant uppermost (most significant) "$count" words are then
2349 set to zero (cleared).
2350 Note that this method does NOT decrease the size of the given bit
2352 vector, i.e., the bit vector is NOT clipped at its upper end to "get
2353 rid of" the vacant "$count" uppermost words.
2354 If you don't want this, i.e., if you want the bit vector to shrink
2356 accordingly, you have to do so EXPLICITLY and AFTER the "Delete"
2357 operation, with a couple of statements such as these:
2358 $bits = $vector->Size();
2360 $count *= Bit::Vector->Word_Bits();
2361 if ($count > $bits) { $count = $bits; }
2362 $vector->Resize($bits - $count);
2363 Note also that "$offset" must lie in the permitted range between "0"
2365 and ""$vector->Word_Size()-1"", or a fatal "offset out of range"
2366 error will occur.
2367 If the term ""$offset + $count"" exceeds ""$vector->Word_Size()-1"",
2369 all the words starting with word number "$offset" up to word number
2370 ""$vector->Word_Size()-1"" are simply cleared.
2371 • "$vector->Chunk_Store($chunksize,$offset,$chunk);"
2373 This method allows you to set more than one bit at a time with
2375 different values.
2376 You can access chunks (i.e., ranges of contiguous bits) between one
2378 and at most ""Bit::Vector->Long_Bits()"" bits wide.
2379 In order to be portable, though, you should never use chunk sizes
2381 larger than 32 bits.
2382 If the given "$chunksize" does not lie between "1" and
2384 ""Bit::Vector->Long_Bits()"", a fatal "chunk size out of range" error
2385 will occur.
2386 The method copies the "$chunksize" least significant bits from the
2388 value "$chunk" to the given bit vector, starting at bit position
2389 "$offset" and proceeding upwards until bit number
2390 ""$offset+$chunksize-1"".
2391 (I.e., bit number "0" of "$chunk" becomes bit number "$offset" in the
2393 given bit vector, and bit number ""$chunksize-1"" becomes bit number
2394 ""$offset+$chunksize-1"".)
2395 If the term ""$offset+$chunksize-1"" exceeds ""$vector->Size()-1"",
2397 the corresponding superfluous (most significant) bits from "$chunk"
2398 are simply ignored.
2399 Note that "$offset" itself must lie in the permitted range between
2401 "0" and ""$vector->Size()-1"", or a fatal "offset out of range" error
2402 will occur.
2403 This method (as well as the other ""Chunk_"" methods) is useful, for
2405 example, when you are reading in data in chunks of, say, 8 bits,
2406 which you need to access later, say, using 16 bits at a time (like
2407 audio CD wave files, for instance).
2408 • "$chunk = $vector->Chunk_Read($chunksize,$offset);"
2410 This method allows you to read the values of more than one bit at a
2412 time.
2413 You can read chunks (i.e., ranges of contiguous bits) between one and
2415 at most ""Bit::Vector->Long_Bits()"" bits wide.
2416 In order to be portable, though, you should never use chunk sizes
2418 larger than 32 bits.
2419 If the given "$chunksize" does not lie between "1" and
2421 ""Bit::Vector->Long_Bits()"", a fatal "chunk size out of range" error
2422 will occur.
2423 The method returns the "$chunksize" bits from the given bit vector
2425 starting at bit position "$offset" and proceeding upwards until bit
2426 number ""$offset+$chunksize-1"".
2427 (I.e., bit number "$offset" of the given bit vector becomes bit
2429 number "0" of the returned value, and bit number
2430 ""$offset+$chunksize-1"" becomes bit number ""$chunksize-1"".)
2431 If the term ""$offset+$chunksize-1"" exceeds ""$vector->Size()-1"",
2433 the non-existent bits are simply not returned.
2434 Note that "$offset" itself must lie in the permitted range between
2436 "0" and ""$vector->Size()-1"", or a fatal "offset out of range" error
2437 will occur.
2438 • "$vector->Chunk_List_Store($chunksize,@chunks);"
2440 This method allows you to fill the given bit vector with a list of
2442 data packets ("chunks") of any size ("$chunksize") you like (within
2443 certain limits).
2444 In fact the given "$chunksize" must lie in the range between "1" and
2446 ""Bit::Vector->Long_Bits()"", or a fatal "chunk size out of range"
2447 error will occur.
2448 In order to be portable, though, you should never use chunk sizes
2450 larger than 32 bits.
2451 The given bit vector is thereby filled in ascending order: The first
2453 chunk from the list (i.e., "$chunks[0]") fills the "$chunksize" least
2454 significant bits, the next chunk from the list ("$chunks[1]") fills
2455 the bits number "$chunksize" to number ""2*$chunksize-1"", the third
2456 chunk ("$chunks[2]") fills the bits number ""2*$chunksize"", to
2457 number ""3*$chunksize-1"", and so on.
2458 If there a less chunks in the list than are needed to fill the entire
2460 bit vector, the remaining (most significant) bits are cleared, i.e.,
2461 the previous contents of the given bit vector are always erased
2462 completely.
2463 If there are more chunks in the list than are needed to fill the
2465 entire bit vector, and/or if a chunk extends beyond
2466 ""$vector->Size()-1"" (which happens whenever ""$vector->Size()"" is
2467 not a multiple of "$chunksize"), the superfluous chunks and/or bits
2468 are simply ignored.
2469 The method is useful, for example (and among many other
2471 applications), for the conversion of packet sizes in a data stream.
2472 This method can also be used to store an octal string in a given bit
2474 vector:
2475 $vector->Chunk_List_Store(3, split(//, reverse $string));
2477 Note however that unlike the conversion methods ""from_Hex()"",
2479 ""from_Bin()"", ""from_Dec()"" and ""from_Enum()"", this statement
2480 does not include any syntax checking, i.e., it may fail silently,
2481 without warning.
2482 To perform syntax checking, add the following statements:
2484 if ($string =~ /^[0-7]+$/)
2486 {
2487 # okay, go ahead with conversion as shown above
2488 }
2489 else
2490 {
2491 # error, string contains other than octal characters
2492 }
2493 Another application is to store a repetitive pattern in a given bit
2495 vector:
2496 $pattern = 0xDEADBEEF;
2498 $length = 32; # = length of $pattern in bits
2499 $size = $vector->Size();
2500 $factor = int($size / $length);
2501 if ($size % $length) { $factor++; }
2502 $vector->Chunk_List_Store($length, ($pattern) x $factor);
2503 • "@chunks = $vector->Chunk_List_Read($chunksize);"
2505 This method allows you to access the contents of the given bit vector
2507 in form of a list of data packets ("chunks") of a size ("$chunksize")
2508 of your choosing (within certain limits).
2509 In fact the given "$chunksize" must lie in the range between "1" and
2511 ""Bit::Vector->Long_Bits()"", or a fatal "chunk size out of range"
2512 error will occur.
2513 In order to be portable, though, you should never use chunk sizes
2515 larger than 32 bits.
2516 The given bit vector is thereby read in ascending order: The
2518 "$chunksize" least significant bits (bits number "0" to
2519 ""$chunksize-1"") become the first chunk in the returned list (i.e.,
2520 "$chunks[0]"). The bits number "$chunksize" to ""2*$chunksize-1""
2521 become the next chunk in the list ("$chunks[1]"), and so on.
2522 If ""$vector->Size()"" is not a multiple of "$chunksize", the last
2524 chunk in the list will contain fewer bits than "$chunksize".
2525 BEWARE that for large bit vectors and/or small values of
2527 "$chunksize", the number of returned list elements can be extremely
2528 large! BE CAREFUL!
2529 You could blow up your application with lack of memory (each list
2531 element is a full-grown Perl scalar, internally, with an associated
2532 memory overhead for its administration!) or at least cause a
2533 noticeable, more or less long-lasting "freeze" of your application!
2534 Possible applications:
2536 The method is especially useful in the conversion of packet sizes in
2538 a data stream.
2539 This method can also be used to convert a given bit vector to a
2541 string of octal numbers:
2542 $string = reverse join('', $vector->Chunk_List_Read(3));
2544 • "$vector->Index_List_Remove(@indices);"
2546 This method allows you to specify a list of indices of bits which
2548 should be turned off in the given bit vector.
2549 In fact this method is a shortcut for
2551 foreach $index (@indices)
2553 {
2554 $vector->Bit_Off($index);
2555 }
2556 In contrast to all other import methods in this module, this method
2558 does NOT clear the given bit vector before processing its list of
2559 arguments.
2560 Instead, this method allows you to accumulate the results of various
2562 consecutive calls.
2563 (The same holds for the method ""Index_List_Store()"". As a
2565 consequence, you can "wipe out" what you did using the method
2566 ""Index_List_Remove()"" by passing the identical argument list to the
2567 method ""Index_List_Store()"".)
2568 • "$vector->Index_List_Store(@indices);"
2570 This method allows you to specify a list of indices of bits which
2572 should be turned on in the given bit vector.
2573 In fact this method is a shortcut for
2575 foreach $index (@indices)
2577 {
2578 $vector->Bit_On($index);
2579 }
2580 In contrast to all other import methods in this module, this method
2582 does NOT clear the given bit vector before processing its list of
2583 arguments.
2584 Instead, this method allows you to accumulate the results of various
2586 consecutive calls.
2587 (The same holds for the method ""Index_List_Remove()"". As a
2589 consequence, you can "wipe out" what you did using the method
2590 ""Index_List_Store()"" by passing the identical argument list to the
2591 method ""Index_List_Remove()"".)
2592 • "@indices = $vector->Index_List_Read();"
2594 This method returns a list of Perl scalars.
2596 The list contains one scalar for each set bit in the given bit
2598 vector.
2599 BEWARE that for large bit vectors, this can result in a literally
2601 overwhelming number of list elements! BE CAREFUL! You could run out
2602 of memory or slow down your application considerably!
2603 Each scalar contains the number of the index corresponding to the bit
2605 in question.
2606 These indices are always returned in ascending order.
2608 If the given bit vector is empty (contains only cleared bits) or if
2610 it has a length of zero (if it contains no bits at all), the method
2611 returns an empty list.
2612 This method can be useful, for instance, to obtain a list of prime
2614 numbers:
2615 $limit = 1000; # or whatever
2617 $vector = Bit::Vector->new($limit+1);
2618 $vector->Primes();
2619 @primes = $vector->Index_List_Read();
2620 • "$vec3->Or($vec1,$vec2);"
2622 "$set3->Union($set1,$set2);"
2624 This method calculates the union of "$set1" and "$set2" and stores
2626 the result in "$set3".
2627 This is usually written as ""$set3 = $set1 u $set2"" in set theory
2629 (where "u" is the "cup" operator).
2630 (On systems where the "cup" character is unavailable this operator is
2632 often denoted by a plus sign "+".)
2633 In-place calculation is also possible, i.e., "$set3" may be identical
2635 with "$set1" or "$set2" or both.
2636 • "$vec3->And($vec1,$vec2);"
2638 "$set3->Intersection($set1,$set2);"
2640 This method calculates the intersection of "$set1" and "$set2" and
2642 stores the result in "$set3".
2643 This is usually written as ""$set3 = $set1 n $set2"" in set theory
2645 (where "n" is the "cap" operator).
2646 (On systems where the "cap" character is unavailable this operator is
2648 often denoted by an asterisk "*".)
2649 In-place calculation is also possible, i.e., "$set3" may be identical
2651 with "$set1" or "$set2" or both.
2652 • "$vec3->AndNot($vec1,$vec2);"
2654 "$set3->Difference($set1,$set2);"
2656 This method calculates the difference of "$set1" less "$set2" and
2658 stores the result in "$set3".
2659 This is usually written as ""$set3 = $set1 \ $set2"" in set theory
2661 (where "\" is the "less" operator).
2662 In-place calculation is also possible, i.e., "$set3" may be identical
2664 with "$set1" or "$set2" or both.
2665 • "$vec3->Xor($vec1,$vec2);"
2667 "$set3->ExclusiveOr($set1,$set2);"
2669 This method calculates the symmetric difference of "$set1" and
2671 "$set2" and stores the result in "$set3".
2672 This can be written as ""$set3 = ($set1 u $set2) \ ($set1 n $set2)""
2674 in set theory (the union of the two sets less their intersection).
2675 When sets are implemented as bit vectors then the above formula is
2677 equivalent to the exclusive-or between corresponding bits of the two
2678 bit vectors (hence the name of this method).
2679 Note that this method is also much more efficient than evaluating the
2681 above formula explicitly since it uses a built-in machine language
2682 instruction internally.
2683 In-place calculation is also possible, i.e., "$set3" may be identical
2685 with "$set1" or "$set2" or both.
2686 • "$vec2->Not($vec1);"
2688 "$set2->Complement($set1);"
2690 This method calculates the complement of "$set1" and stores the
2692 result in "$set2".
2693 In "big integer" arithmetic, this is equivalent to calculating the
2695 one's complement of the number stored in the bit vector "$set1" in
2696 binary representation.
2697 In-place calculation is also possible, i.e., "$set2" may be identical
2699 with "$set1".
2700 • "if ($set1->subset($set2))"
2702 Returns "true" ("1") if "$set1" is a subset of "$set2" (i.e.,
2704 completely contained in "$set2") and "false" ("0") otherwise.
2705 This means that any bit which is set ("1") in "$set1" must also be
2707 set in "$set2", but "$set2" may contain set bits which are not set in
2708 "$set1", in order for the condition of subset relationship to be true
2709 between these two sets.
2710 Note that by definition, if two sets are identical, they are also
2712 subsets (and also supersets) of each other.
2713 • "$norm = $set->Norm();"
2715 Returns the norm (number of bits which are set) of the given vector.
2717 This is equivalent to the number of elements contained in the given
2719 set.
2720 Uses a byte lookup table for calculating the number of set bits per
2722 byte, and thus needs a time for evaluation (and a number of loops)
2723 linearly proportional to the length of the given bit vector (in
2724 bytes).
2725 This should be the fastest algorithm on average.
2727 • "$norm = $set->Norm2();"
2729 Returns the norm (number of bits which are set) of the given vector.
2731 This is equivalent to the number of elements contained in the given
2733 set.
2734 This does the same as the method ""Norm()"" above, only with a
2736 different algorithm:
2737 This method counts the number of set and cleared bits at the same
2739 time and will stop when either of them has been exhausted, thus
2740 needing at most half as many loops per machine word as the total
2741 number of bits in a machine word - in fact it will need a number of
2742 loops equal to the minimum of the number of set bits and the number
2743 of cleared bits.
2744 This might be a faster algorithm than of the method ""Norm()"" above
2746 on some systems, depending on the system's architecture and the
2747 compiler and optimisation used, for bit vectors with sparse set bits
2748 and for bit vectors with sparse cleared bits (i.e., predominantly set
2749 bits).
2750 • "$norm = $set->Norm3();"
2752 Returns the norm (number of bits which are set) of the given vector.
2754 This is equivalent to the number of elements contained in the given
2756 set.
2757 This does the same as the two methods ""Norm()"" and ""Norm2()""
2759 above, however with a different algorithm.
2760 In fact this is the implementation of the method ""Norm()"" used in
2762 previous versions of this module.
2763 The method needs a number of loops per machine word equal to the
2765 number of set bits in that machine word.
2766 Only for bit vectors with sparse set bits will this method be fast;
2768 it will depend on a system's architecture and compiler whether the
2769 method will be faster than any of the two methods above in such
2770 cases.
2771 On average however, this is probably the slowest method of the three.
2773 • "$min = $set->Min();"
2775 Returns the minimum of the given set, i.e., the minimum of all
2777 indices of all set bits in the given bit vector "$set".
2778 If the set is empty (no set bits), plus infinity (represented by the
2780 constant "MAX_LONG" on your system) is returned.
2781 (This constant is usually 2 ^ (n-1) - 1, where ""n"" is the number of
2783 bits of an unsigned long on your machine.)
2784 • "$max = $set->Max();"
2786 Returns the maximum of the given set, i.e., the maximum of all
2788 indices of all set bits in the given bit vector "$set".
2789 If the set is empty (no set bits), minus infinity (represented by the
2791 constant "MIN_LONG" on your system) is returned.
2792 (This constant is usually -(2 ^ (n-1) - 1) or -(2 ^ (n-1)), where
2794 ""n"" is the number of bits of an unsigned long on your machine.)
2795 • "$m3->Multiplication($r3,$c3,$m1,$r1,$c1,$m2,$r2,$c2);"
2797 This method multiplies two boolean matrices (stored as bit vectors)
2799 "$m1" and "$m2" and stores the result in matrix "$m3".
2800 The method uses the binary "xor" operation (""^"") as the boolean
2802 addition operator (""+"").
2803 An exception is raised if the product of the number of rows and
2805 columns of any of the three matrices differs from the actual size of
2806 their underlying bit vector.
2807 An exception is also raised if the numbers of rows and columns of the
2809 three matrices do not harmonize in the required manner:
2810 rows3 == rows1
2812 cols3 == cols2
2813 cols1 == rows2
2814 This method is used by the module "Math::MatrixBool".
2816 See Math::MatrixBool(3) for details.
2818 • "$m3->Product($r3,$c3,$m1,$r1,$c1,$m2,$r2,$c2);"
2820 This method multiplies two boolean matrices (stored as bit vectors)
2822 "$m1" and "$m2" and stores the result in matrix "$m3".
2823 This special method uses the binary "or" operation (""|"") as the
2825 boolean addition operator (""+"").
2826 An exception is raised if the product of the number of rows and
2828 columns of any of the three matrices differs from the actual size of
2829 their underlying bit vector.
2830 An exception is also raised if the numbers of rows and columns of the
2832 three matrices do not harmonize in the required manner:
2833 rows3 == rows1
2835 cols3 == cols2
2836 cols1 == rows2
2837 This method is used by the module "Math::MatrixBool".
2839 See Math::MatrixBool(3) for details.
2841 • "$matrix->Closure($rows,$cols);"
2843 This method calculates the reflexive transitive closure of the given
2845 boolean matrix (stored as a bit vector) using Kleene's algoritm.
2846 (See Math::Kleene(3) for a brief introduction into the theory behind
2848 Kleene's algorithm.)
2849 The reflexive transitive closure answers the question whether a path
2851 exists between any two vertices of a graph whose edges are given as a
2852 matrix:
2853 If a (directed) edge exists going from vertex "i" to vertex "j", then
2855 the element in the matrix with coordinates (i,j) is set to "1"
2856 (otherwise it remains set to "0").
2857 If the edges are undirected, the resulting matrix is symmetric, i.e.,
2859 elements (i,j) and (j,i) always contain the same value.
2860 The matrix representing the edges of the graph only answers the
2862 question whether an EDGE exists between any two vertices of the graph
2863 or not, whereas the reflexive transitive closure answers the question
2864 whether a PATH (a series of adjacent edges) exists between any two
2865 vertices of the graph!
2866 Note that the contents of the given matrix are modified by this
2868 method, so make a copy of the initial matrix in time if you are going
2869 to need it again later.
2870 An exception is raised if the given matrix is not quadratic, i.e., if
2872 the number of rows and columns of the given matrix is not identical.
2873 An exception is also raised if the product of the number of rows and
2875 columns of the given matrix differs from the actual size of its
2876 underlying bit vector.
2877 This method is used by the module "Math::MatrixBool".
2879 See Math::MatrixBool(3) for details.
2881 • "$matrix2->Transpose($rows2,$cols2,$matrix1,$rows1,$cols1);"
2883 This method calculates the transpose of a boolean matrix "$matrix1"
2885 (stored as a bit vector) and stores the result in matrix "$matrix2".
2886 The transpose of a boolean matrix, representing the edges of a graph,
2888 can be used for finding the strongly connected components of that
2889 graph.
2890 An exception is raised if the product of the number of rows and
2892 columns of any of the two matrices differs from the actual size of
2893 its underlying bit vector.
2894 An exception is also raised if the following conditions are not met:
2896 rows2 == cols1
2898 cols2 == rows1
2899 Note that in-place processing ("$matrix1" and "$matrix2" are
2901 identical) is only possible if the matrix is quadratic. Otherwise, a
2902 fatal "matrix is not quadratic" error will occur.
2903 This method is used by the module "Math::MatrixBool".
2905 See Math::MatrixBool(3) for details.
2907
2909 Bit::Vector::Overload(3), Bit::Vector::String(3), Storable(3).
2910 Set::IntRange(3), Math::MatrixBool(3), Math::MatrixReal(3),
2912 DFA::Kleene(3), Math::Kleene(3), Graph::Kruskal(3).
2913
2915 This man page documents "Bit::Vector" version 7.4.
2916
2918 Steffen Beyer
2919 mailto:STBEY@cpan.org
2920 http://www.engelschall.com/u/sb/download/
2921
2923 Copyright (c) 1995 - 2013 by Steffen Beyer. All rights reserved.
2924
2926 This package is free software; you can redistribute it and/or modify it
2927 under the same terms as Perl itself, i.e., under the terms of the
2928 "Artistic License" or the "GNU General Public License".
2929 The C library at the core of this Perl module can additionally be
2931 redistributed and/or modified under the terms of the "GNU Library
2932 General Public License".
2933 Please refer to the files "Artistic.txt", "GNU_GPL.txt" and
2935 "GNU_LGPL.txt" in this distribution for details!
2936
2938 This package is distributed in the hope that it will be useful, but
2939 WITHOUT ANY WARRANTY; without even the implied warranty of
2940 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
2941 See the "GNU General Public License" for more details.
2943perl v5.34.0 2021-07-22 Vector(3)