++ed by:
1 non-PAUSE user
Avinash Kak
and 1 contributors

NAME

Algorithm::BitVector --- A memory efficient packed representation of arbitrary sized bit arrays and for logical and arithmetic operations on such arrays.

SYNOPSIS

``````    use Algorithm::BitVector;

# Constructing a given sized bitvector of all zeros:
\$bv = Algorithm::BitVector->new( size => 7 );
print "\$bv\n";                                   # 0000000

# Constructing a bitvector whose integer value is specified:
\$bv = Algorithm::BitVector->new( intVal => 123456 );
print "\$bv\n";                                    # 11110001001000000
print int(\$bv);                                   # 123456

# Constructing a bitvector from a very large integer:
use Math::BigInt;
\$x = Math::BigInt->new('12345678901234567890123456789012345678901234567890');
\$bv = Algorithm::BitVector->new( intVal => \$x );

# Constructing a bitvector from a given bit string:
\$bv = Algorithm::BitVector->new( bitstring => '00110011' );

# Constructing a bitvector from an ASCII text string:
\$bv = Algorithm::BitVector->new( textstring => "hello\njello" );

# Constructing a bitvector from a hex string:
\$bv = Algorithm::BitVector->new( hexstring => "68656c6c6f" );

# Constructing a bitvector from a bit list passed as an anonymous array:
\$bv = Algorithm::BitVector->new( bitlist => [1, 1, 0, 1] );

# Constructing a bitvector from the contents of a disk file:
\$bv = Algorithm::BitVector->new( filename => 'testinput.txt' );
\$bv1 = \$bv->read_bits_from_file(64);         # bitvector from the first 64 bits
# and so on``````

CHANGES

Version 1.26 incorporates the following changes: (1) It allows you to carry out slice-based set and get operations on a BitVector object. The two new methods for these operations are named `get_slice()` and `set_slice()`. (2) It includes a new method named `min_canonical()` that returns a circularly rotated version of a BitVector with the least integer value. For obvious reasons, this version would also have the largest number of leading zeros. And (3) It fixes a bug in the implementation of the method `gf_divide_by_modulus()`.

Version 1.25 incorporates bugfix for the case when you try to construct a bitvector of a specified length from a large integer that is supplied to the module constructor as a `Math::BigInt` object.

Version 1.24 includes in the `Makefile.PL` file the minimum version restriction on the `List::Util` module that is imported.

Version 1.23 mentions the required modules in the `Makefile.PL` file but with no minimum version numbers. Additionally, the documentation associated with the methods was significantly upgraded in this version.

Version 1.22 removes the Perl version restriction from the module and the `Makefile.PL` files and the `PREREQ_PM` restrictions from the `Makefile.PL` file.

Version 1.21 fixes a bug in the code for the Miller-Rabin primality test function `test_for_primality()`. This version also places a hard limit on the size of the integers that are allowed to be tested for primality.

Version 1.2 fixes an important bug in creating bitvectors from the contents of a disk file. This version also includes corrections for some of the documentation errors discovered.

Version 1.1 incorporates additional type checking on the operands for the overloaded operators. Also fixed some minor documentation formatting issues.

DESCRIPTION

My main motivation for creating this module was to provide the students at Purdue and elsewhere with a Perl class whose API is the same as that of my Python based `BitVector` module that appears to have become popular for prototyping algorithms for cryptography and hash functions.

This module stores the bits of a bitvector in 16-bit unsigned shorts. As you can see in the constructor code for `new()`, after resolving the arguments with which the constructor is called, the very first thing the constructor does is to figure out how many of those 2-byte shorts it needs for the bits. That does not imply that the size of a bit array that is stored in a bitvector must be a multiple of 16. A bitvector can be of any size whatsoever. The `Algorithm::BitVector` class keeps track of the number of bits through its `size` instance variable.

Note that, except for one case, the constructor must be called with a single keyword argument, which determines how the bitvector will be constructed. The single exception to this rule is for the keyword argument `intVal` which you would normally use for constructing a bitvector from an integer. The additional option you can supply with `intVal` is `size`. When both `intVal` and `size` are specified in a constructor call, you get a bitvector of the specified size provided the value supplied for `size` is larger than what it takes to accommodate the bits for the `intVal` integer.

In addition to constructing bitvectors from integers, this module can also construct bitvectors from bit strings, from ASCII text strings, from hex strings, from a list of bits, and from the contents of a file. With regards to constructing bitvectors from integers, the module can construct very large bitvectors from very large integers stored as `Math::BigInt` objects.

The following `use overload` declaration in the module gives the list of the overloaded operators. Since `fallback` is set to 1, several other operators become overloaded by autogeneration from those shown below. For example, overloading of the 3-way numerical comparison operator `<=>` automatically overloads the `<`, `<=`, `>`, `>=`, `==`, and `!=` operators.

``````    use overload  '+'        =>    '_add',
'""'       =>    '_str',
'0+'       =>    '_int',
'~'        =>    '_invert',
'|'        =>    '_or',
'&'        =>    '_and',
'^'        =>    '_xor',
'<=>'      =>    '_compare',
'<<'       =>    '_lshift',
'>>'       =>    '_rshift',
'<>'       =>    '_iter',
'fallback' =>    1;``````

It is important to remember that the overloadings for the ``<<`' and ``>>`' operators are for circular left and right shifts (their usual meaning as bitwise operators is for non-circular shifts). This was done because the applications for which this module is intended is more likely to use circular shifts of bit fields than non-circular shifts. You can still carry out non-circular shifts by calling the methods `shift_left()` and `shift_right()` as illustrated elsewhere in this documentation.

Another important thing to bear in mind is the overloading of the ``+`' operator. It is NOT addition. On the other hand, it is a concatenation of the two operand bitvectors. This was done to keep the usage of this operator the same as in the Python version of this module.

By virtue of how the operators are overloaded, you can make the calls listed in the rest of this section. To illustrate these calls, I will use the following two bit vectors:

``````    \$bv1 = Algorithm::BitVector->new( bitstring => "111000" );
\$bv2 = Algorithm::BitVector->new( bitstring => "000101000" );``````

These two bitvectors are intentionally of different lengths to illustrate what role the size differences play in how the various operators work.

Concatenating two bitvectors:
``    \$bv3 = \$bv1 + \$bv2;                          # 111000000101000``

The concatenation of two bitvectors is returned as a new bitvector. This is made possible by the overload definition for the `+` operator.

Note that the following also works:

``    print \$bv1 . "hello";                        # 111000hello``

In this case, Perl implicitly converts the left operand of the `.' operator into a string (which is made possible by the overloading for the stringification operator in this module) and then returns the result as a string.

Creating the string representation of a bitvector:
``    print "\$bv1";                                # 111000   ``

This is made possible for the overload definition for the `""` operator.

Converting a bitvector to its integer value:
``    print int(\$bv1);                             # 56``

This is made possible by the overload definition for the `0+` operator.

Inverting a bitvector
``````    \$bv3 = ~ \$bv1;
print \$bv3;                                  # 000111``````

This is made possible by the overload definition for the `~` operator. The original bitvector on which this unary operator is invoked remains unchanged.

Taking logical OR of two bitvectors:
``    \$bv3 = \$bv1 | \$bv2;                          # 000111000 ``

When two bitvectors are of unequal length (as is the case here), the shorter vector is zero-padded on the left to equalize their lengths before the application of the logical operation. If this auto-padding property is not something you want, you should check the lengths of the argument bitvectors in your own script before invoking this operator. The result of the logical OR operation is returned as a new bitvector. The two operand bitvectors remain unchanged.

Taking logical AND of two bitvectors:
``    \$bv3 = \$bv1 & \$bv2;                          # 000101000``

When two bitvectors are of unequal length (as is the case here), the shorter vector is zero-padded on the left to equalize their lengths before the application of the logical operation. If this auto-padding property is not something you want, you should check the lengths of the argument bitvectors in your own script before invoking this operator. The result of the logical AND operation is returned as a new bitvector. The two operand bitvectors remain unchanged.

Taking logical XOR of two bitvectors:
``    \$bv3 = \$bv1 ^ \$bv2;                          # 000010000``

When two bitvectors are of unequal length (as is the case here), the shorter vector is zero-padded on the left to equalize their lengths before the application of the logical operation. If this auto-padding property is not something you want, you should check the lengths of the argument bitvectors in your own script before invoking this operator. The result of the logical XOR operation is returned as a new bitvector. The two operand bitvectors remain unchanged.

Comparing bitvectors:
``````    \$bv1 < \$bv2 ?  print "yes\n"  :  print "no\n";        # no

\$bv1 > \$bv2 ?  print "yes\n"  :  print "no\n";        # yes

\$bv1 <= \$bv2 ?  print "yes\n"  :  print "no\n";       # no

\$bv1 >= \$bv2 ?  print "yes\n"  :  print "no\n";       # yes

\$bv1 == \$bv2 ?  print "yes\n"  :  print "no\n";       # no

\$bv1 != \$bv2 ?  print "yes\n"  :  print "no\n";       # yes``````

The overload definitions for all these operators are autogenerated from the overload definition for the 3-way numerical comparison operator '`<=>`'. The bitvectors are compared on the basis of their integer values. That is, `\$bv1` is less than `\$bv2` if `int(\$bv1)` is less than `int(\$bv2)`.

In-place circular shifting:
``````    \$n = 3;

\$bv1 << \$n;                                           # \$bv1 is now 000111
\$bv1 >> \$n;                                           # \$bv1 is now 111000``````

Since Perl does not expect these two operators to be invoked in a void context, such statements in your code will elicit a warning from Perl to that effect. If these warnings annoy you, you can turn them off by surrounding such statements with `no warnings "void";` and `use warnings;` directives. The other option is to invoke such statements in the following manner:

``````    \$bv1 = \$bv1 << \$n;
\$bv2 = \$bv1 >> \$n; ``````

That works because the overload definitions for these bit shift operators return the bitvector object on which they are invoked. As it turns out, this also allows for chained invocation of these operators, as in

``````    \$bv1 = \$bv1 << 3 << 1 >> 2;                          # 100011

\$bv1 = \$bv1 << 2 >> 1 >> 3;                          # 111000``````
Iterating over a bitvector:
``````    while (<\$bv1>) {
print "\$_  ";
}                                                    # 1  1  1  0  0  0``````

This is made possible by the overload definition for the `<>` operator. The `Algorithm::BitVector` class includes an inner class `BitVecIterator` for this purpose.

CONSTRUCTING BITVECTORS

Constructing an empty bitvector:
``````    \$bv = Algorithm::BitVector->new( size => 0 );

print "\$bv\n";                                                   # no output``````
Constructing a given sized bitvector of all zeros:
``    \$bv = Algorithm::BitVector->new( size => 13 );                   # 0000000000000``
Constructing a bitvector from an integer value:
``    \$bv = Algorithm::BitVector->new( intVal => 5006 );               # 1001110001110 ``

The module returns the smallest possible bitvector that would accommodate the integer value provided with the `intVal` option.

Constructing a bitvector by specifying both the size and the integer values:

As mentioned, with the `intVal` option, you get the smallest possible bitvector that can be generated from that integer. If you want a larger bitvector, you can also supply the `size` option as shown below:

``    \$bv = Algorithm::BitVector->new( intVal => 5006, size => 16 );   # 0001001110001110  ``

If the value supplied for the `size` option in such a call is not larger than the smallest bit array that represents the `intVal` value, the constructor will throw an exception.

Constructing a bitvector from a very large integer:
``````    use Math::BigInt;
\$x = Math::BigInt->new('12345678901234567890123456789012345678901234567890');
\$bv = Algorithm::BitVector->new( intVal => \$x );
#1000011100100111111101100011011010011010101011111000001111001010000\
#10101000000100110011101000111101011111000110001111111000110010110110\
#01110001111110000101011010010``````
Constructing a bitvector from a bit string:
``    \$bv = Algorithm::BitVector->new( bitstring => '00110011' );     # 00110011``
Constructing a bitvector from an ASCII text string:
``````    \$bv = Algorithm::BitVector->new( textstring => "hello\n" );
# 011010000110010101101100011011000110111100001010``````
Constructing a bitvector from a hex string:
``````    \$bv = Algorithm::BitVector->new( hexstring => "68656c6c6f" );
# 0110100001100101011011000110110001101111``````
Constructing a bitvector from a bit list:
``    \$bv = Algorithm::BitVector->new( bitlist => [1, 1, 0, 1] );       # 1101``
Constructing a bitvector from the contents of a disk file:
``````    \$bv = Algorithm::BitVector->new( filename => 'testinput1.txt' );

print "\$bv\n";                               # Nothing to show yet

\$bv1 = \$bv->read_bits_from_file(64);         # Now you have a bitvector from the
#   first 64 bits``````

Note that it takes two calls to create bitvectors from the contents of a file. The first merely creates an empty bitvector just to set the necessary file handle for reading the file. It is the second call in which you invoke the method `read_bits_from_file()` that actually returns a bitvector from the bits read from the file. Each call to `read_bits_from_file()` in this manner spits out a new bit vector.

METHODS

close_file_handle()

When you construct bitvectors by block scanning a disk file, after you are done, you can call this method to close the file handle that was created to read the file:

``````    \$bv = Algorithm::BitVector->new( filename => 'testinput.txt' );
## your code to read bit blocks for constructing bitvectors goes here
\$bv->close_file_handle();``````

The constructor call in the first statement opens a file handle for reading the bits. It is this file handle that is closed by calling `close_file_handle()`,

count_bits()

``````    \$bv = Algorithm::BitVector->new( intVal => 45, size => 16 );
print \$bv->count_bits();                       # 4``````

This method returns an integer value which is the number of bits set to 1 in the bitvector on which the method is invoked.

count_bits_sparse()

Say you have a bitvector with two million bits:

``    \$bv = Algorithm::BitVector->new( size => 2000000 );     ``

and you happen to set its individual bits by

``````    \$bv->set_bit(345234, 1);
\$bv->set_bit(233, 1);
\$bv->set_bit(243, 1);
\$bv->set_bit(18, 1);
\$bv->set_bit(785, 1);``````

The following call returns the number of bits set in the bitvector:

``    print \$bv->count_bits_sparse();               # 5   ``

For very long bitvectors, as in the example here, this method will work much faster than the `count_bits()` method. However, for dense bitvectors, I expect `count_bits()` to work faster.

deep_copy()

``    \$bv_copy = \$bv->deep_copy();``

Subsequently, any alterations to the bitvectors pointed to by either `\$bv` or `\$bv_copy` will not affect the other.

divide_into_two()

``````    (\$bv1, \$bv2) = \$bv->divide_into_two();              # say \$bv = 0000000000101101
print "\$bv1\n";                                     # 00000000
print "\$bv2\n";                                     # 00101101  ``````

Divides an even sized bitvector into two bitvectors, each of size half of the bitvector on which this method is invoked. Throws an exception when invoked on a bitvector that is not even sized.

gcd()

This method uses the Euclid's algorithm to return the Greatest Common Divisor of the integer values represented by the two bitvectors. The following example shows a call to `gcd()` returning the GCD of the integer values of the bitvectors `\$bv1` and `\$bv2`.

``````    \$bv1 = Algorithm::BitVector->new( bitstring => '01100110' );   # 102
\$bv2 = Algorithm::BitVector->new( bitstring => '011010' );     # 26
\$gcd = \$bv1->gcd( \$bv2 );                                      # 10
print int(\$gcd);                                               # 2``````

The result returned by `gcd()` is a bitvector.

gen_random_bits()

``````    \$bv = Algorithm::BitVector->new( intVal => 0 );
\$bv = \$bv->gen_random_bits(16);                        # 1100111001010101``````

The call to `gen_random_bits()` returns a bitvector whose bits are randomly generated. The number of bits in the returned bitvector equals the argument integer.

get_bit()

This method gives you array-like access to the individual bits of a bitvector.

``````    \$bv = Algorithm::BitVector->new( bitstring => '10111' );
print \$bv->get_bit(0);                           # 1   (the first bit)
print \$bv->get_bit(1);                           # 0
print \$bv->get_bit(4);                           # 1   (the last bit) ``````

Negative values for the index scan a bitvector from right to left, with the `-1` index standing for the last (meaning the right-most) bit in the vector:

``````    print \$bv->get_bit(-1);                          # 1   (the last bit)
print \$bv->get_bit(-2);                          # 1
print \$bv->get_bit(-5);                          # 1   (the first bit)``````

The `get_bit()` can also return a slice of a bitvector if the argument to the method is an anonymous array of the index range you desire, as in the second statement below:

``````    \$bv = Algorithm::BitVector->new( bitstring => "10111011");
my \$arr = \$bv->get_bit( [3..7] );
print "@\$arr\n";                                 # 1 1 0 1 1 ``````

In this example, we want `get_bit()` to return all bits at positions indexed 3 through 7, both ends inclusive. Note that the slice is returned as an array of bits.

get_bitvector_in_ascii()

``````    \$bv = Algorithm::BitVector->new( textstring => "hello" );
print "\$bv\n";                              # 0110100001100101011011000110110001101111
print \$bv->get_bitvector_in_ascrii();                           # hello                        ``````

The method returns a string of ASCII characters by converting successive 8-bit slices of the bitvector into an ASCII character. It throws an exception if the size of the bit pattern is not a multiple of 8. Calling this method to create a text-based print representation of a bit vector makes sense only if you don't expect to see any unprintable characters in the successive 8-bit slices of the bitvector. Let's say you have created a bitvector from a text string using the appropriate constructor call. Subsequently, you encrypted this text string. Next, you or someone else decrypts the encrypted bit stream. Since what comes out at the decryption end must be the original text string, it would make sense to invoke this method to recover the original text.

get_bitvector_in_hex()

Assuming that length of your bitvector is a multiple of 4, this methods returns a hex representation of the bit pattern:

``````    \$bv = Algorithm::BitVector->new(bitstring => "0110100001100101011011000110110001101111");
print \$bv->get_bitvector_in_hex();             # 68656c6c6f``````

The hex representation is returned in the form if a string of hex characters. This method throws an exception if the size of the bitvector is not a multiple of 4.

get_slice()

You can use this method to get a slice of a BitVector that is within a specified range. You can specify the index range with the usual range operator in Perl. If the index range is, say, '5..11', the method will return all bits at index values 5 through 10.

``````    my \$bv9 = Algorithm::BitVector->new( intVal => 63437, size => 16 );
print "BitVector for testing get_slice(): \$bv9\n";     # 1111011111001101
my \$slice_bv = \$bv9->get_slice( [5..11] );
print "slice BitVector for index values 5 through 10: \$slice_bv\n";    # 111110    ``````

Note that the method returns the slice in the form of a BitVector object.

gf_divide_by_modulus()

This method is for modular division in the Galois Field `GF(2^n)`. You must specify the modulus polynomial through a bit pattern and also the value of the integer `n`:

``````    \$mod = Algorithm::BitVector->new( bitstring => '100011011' );   # AES modulus
\$n = 8;
\$a = Algorithm::BitVector->new( bitstring => '11100010110001' );
(\$quotient, \$remainder) = \$a->gf_divide_by_modulus(\$mod, \$n);
print "\$quotient\n";                           # 00000000111010
print "\$remainder\n";                          # 10001111 ``````

What this example illustrates is dividing the bitvector `\$a` by the modulus bit vector `\$mod`. For a more general division of one bitvector `\$a` by another bit vector `\$b`, you would carry out a multiplication of `\$a` by the MI of `\$b`, where MI stands for "multiplicative inverse" as returned by a call to the method `gf_MI()`. A call to `gf_divide_by_modulus()` returns two bitvectors, one for the quotient and the other for the remainder.

gf_MI()

This method returns the multiplicative inverse of a bit pattern in the Galois Field `GF(2^n)`. You must specify both the modulus polynomial through its bit pattern and the value of `n`:

``````    \$modulus = Algorithm::BitVector->new( bitstring => '100011011' );     # AES modulus
\$n = 8;
\$a = Algorithm::BitVector->new( bitstring => '00110011' );
print \$a->gf_MI(\$modulus, \$n);                     # 01101100                                  ``````

Note that the multiplicative inverse is returned as a bitvector.

gf_multiply()

This method returns a product of two bit patterns in the Galois Field `GF(2)` field. That is, given any two polynomials with their coefficients drawn from the 0 and 1 values in `GF(2)`, this method returns the product polynomial.

``````    \$a = Algorithm::BitVector->new( bitstring => '0110001' );
\$b = Algorithm::BitVector->new( bitstring => '0110' );
print \$a->gf_multiply(\$b);                                #00010100110``````

As you would expect, in general, the bit pattern returned by this method will be longer than the lengths of the two operand bitvectors. The result returned by the method is in the form of a bitvector.

gf_multiply_modular()

This method carries out modular multiplication in the Galois Field `GF(2^n)`. You must supply it the bitvector for the modulus polynomial and the value of `n`.

``````    \$modulus = Algorithm::BitVector->new( bitstring => '100011011' );     # AES modulus
\$n = 8;
\$a = Algorithm::BitVector->new( bitstring => '0110001' );
\$b = Algorithm::BitVector->new( bitstring => '0110' );
print \$a->gf_multiply_modular(\$b, \$modulus, \$n);         # 10100110                            ``````

This example returns the product of the bit patterns `\$a` and `\$b` modulo the bit pattern `\$modulus` in `GF(2^8)`. The result returned by the method is in the form of a bitvector.

hamming_distance()

Hamming distance is commonly used to measure dissimilarity between two bitvectors of the same size.

``````    \$bv1 = Algorithm::BitVector->new( bitstring => '11111111' );
\$bv2 = Algorithm::BitVector->new( bitstring => '00101011' );
print \$bv1->hamming_distance( \$bv2 );                            # 4``````

This distance returns the number of bit positions in which two the bit patterns differ. The method throws an exception if the two bitvectors are not of the same length. The value returned is an integer.

int_value()

You can find the integer value of a bitvector by

``````    \$bv = Algorithm::BitVector->new( intVal => 5678 );
print \$bv3->int_value();                             # 5678``````

or, even more simply by

``    print int(\$bv);                                      # 5678``

which works on account of the overloading of the `0+` operator.

is_power_of_2()

You can use this predicate to test if the integer value of a bitvector is a power of 2:

``````    \$bv = Algorithm::BitVector->new( bitstring => '10000000001110' );
print int(\$bv);                                        # 826
print \$bv->is_power_of_2();                            # 0   ``````

The predicate returns 1 for true and 0 for false.

is_power_of_2_sparse()

This does the same thing as the `is_power_of_2()` method but in a way that makes it faster for large bitvectors with very few bits set.

``````    \$bv = Algorithm::BitVector->new( size => 2000000 );
\$bv->set_bit(345234, 1);
print \$bv->is_power_of_2_sparse();                    # 1``````

jaccard_distance()

The Jaccard distance between two bitvectors is 1 minus the Jaccard similarity coefficient:

``````    \$bv1 = Algorithm::BitVector->new( bitstring => '11111111' );
\$bv2 = Algorithm::BitVector->new( bitstring => '10101011' );
print \$bv1->jaccard_distance( \$bv2 );                         # 0.375``````

The value returned by the method is a floating point number between 0 and 1.

jaccard_similarity()

This method returns the Jaccard similarity coefficient between the two bitvectors pointed to by `\$bv1` and `\$bv2`:

``````    \$bv1 = Algorithm::BitVector->new( bitstring => '11111111' );
\$bv2 = Algorithm::BitVector->new( bitstring => '10101011' );
print \$bv1->jaccard_similarity( \$bv2 );                       # 0.675``````

The value returned by the method is a floating point number between 0 and 1.

length()

This method returns the total number of bits in a bitvector:

``````    \$bv = Algorithm::BitVector->new( intVal => 5678 );
print \$bv;                                                    # 1011000101110
print \$bv->length();                                          # 13  ``````

Note that what `length()` returns is the total size of a bitvector, including any leading zeros.

min_canonical()

This method returns the min-int-value circularly rotated version of a BitVector. I refer to this form of a BitVector as its "min canonical form".

``````    \$bv = Algorithm::BitVector->new( bitstring => "00011100010010" );
print \$bv->min_canonical();                                   # 00001110001001``````

multiplicative_inverse()

This method calculates the multiplicative inverse using normal integer arithmetic. For multiplicative inverses in a Galois Field `GF(2^n)`, use the method `gf_MI()` described earlier in this API.

``````    \$modulus = Algorithm::BitVector->new( intVal => 32 );
\$bv = Algorithm::BitVector->new( intVal => 17 );
\$result = \$bv->multiplicative_inverse( \$modulus );
if (\$result) {
print \$result;                                                # 10001
} else {
print "No multiplicative inverse in this case\n";
}``````

What this example says is that the multiplicative inverse of 17 modulo 32 is 17. That is because 17 times 17 in modulo 32 arithmetic equals 1. When using this method, you must test the value returned for 0. If the returned value is 0, that means that the number corresponding to the bitvector on which this method is invoked does not possess a multiplicative inverse with respect to the modulus.

next_set_bit()

Starting from a given bit position, this method returns the index of the next bit that is set in a bitvector:

``````    \$bv = Algorithm::BitVector->new( bitstring => '00000000000001' );
print \$bv->next_set_bit(5);                                  # 13                              ``````

In this example, we are asking the method to return the index of the bit that is set after the bit position indexed 5. The method returns -1 if there is no next set bit.

You can pad a bitvector from the left with a designated number of zeros:

``````    \$bv = Algorithm::BitVector->new( bitstring => '101010' );
print \$bv->pad_from_left( 4 );                               # 0000101010``````

The method returns the bitvector on which it is invoked. So you can think of it as an in-place extension of a bitvector (although, under the hood, the extension is carried out by giving a new longer `_vector` attribute to the bitvector object).

You can pad a bitvector from the right with a designated number of zeros:

``````    \$bv = Algorithm::BitVector->new( bitstring => '101010' );
print \$bv->pad_from_right( 4 );                              # 1010100000``````

The method returns the bitvector on which it is invoked. So you can think of it as an in-place extension of a bitvector (although, under the hood, the extension is carried out by giving a new longer `_vector` attribute to the bitvector object).

permute()

You can permute the bits in a bitvector with a permutation list as shown below:

``````    \$bv1 = Algorithm::BitVector->new( intVal => 203, size => 8 );
print \$bv1;                                                   # 11001011
\$bv2 =  \$bv1->permute( [3, 2, 1, 0, 7, 6, 5, 4] );
print \$bv2;                                                   # 00111101``````

The method returns a new bitvector with permuted bits.

rank_of_bit_set_at_index()

You can measure the "rank" of a bit that is set at a given index. Rank is the number of bits that are set up to the argument position, as in

``````    \$bv = Algorithm::BitVector->new( bitstring => '01010101011100' );
print \$bv->rank_of_bit_set_at_index( 10 );                    # 6``````

The value 6 returned by this call to `rank_of_bit_set_at_index()` is the number of bits set up to the position indexed 10 (including that position). The method throws an exception if there is no bit set at the argument position.

Constructing bitvectors from the contents of a disk file takes two steps: First you must make the call shown in the first statement below. The purpose of this call is to create a file handle that is associated with the variable `\$bv` in this case. Subsequent invocations of `read_bits_from_file(\$n)` on this variable will read blocks of `\$n` bits and return a bitvector for each block thus read. The variable `\$n` must be a multiple of 8 for this to work.

``````    \$bv = Algorithm::BitVector->new( filename => 'testinput.txt' );
...
...
\$bv->close_file_handle();``````

When reading a file as shown above, you can test the attribute `more_to_read` of the bitvector object in order to find out if there is more to be read in the file. The `while` loop shown below reads all of a file in 64-bit blocks.

``````    \$bv = Algorithm::BitVector->new( filename => 'testinput.txt' );
}
\$bv->close_file_handle();``````

The size of the last bitvector constructed from a file corresponds to how many bytes remain unread in the file at that point. It is your responsibility to zero-pad the last bitvector appropriately if, say, you are doing block encryption of the whole file.

reset()

You can reset a previously constructed bitvector all either all 1's or all 0's by calling this method:

``````    \$bv = Algorithm::BitVector->new( intVal => 203, size => 8 );
print \$bv;                                                  # 11001011
\$bv->reset(1);
print \$bv;                                                  # 11111111
\$bv->reset(0);
print \$bv;                                                  # 00000000  ``````

What the method accomplishes can be thought of as in-place resetting of the bits. The method does not return anything.

reverse()

Given a bitvector, you can construct a bitvector with all the bits reversed, in the sense that what was left-to-right earlier now becomes right-to-left, as in

``````    \$bv = Algorithm::BitVector->new( bitstring => '01100001' );
print \$bv->reverse();                                       # 10000110                         ``````

A call to this method returns a new bitvector whose bits are in reverse order in relation to the bits in the bitvector on which the method is called.

runs()

This method returns an array of runs of 1's and 0's in a bitvector:

``````    \$bv = Algorithm::BitVector->new( bitlist => [1,1,1,0,0,1] );
my @bvruns = \$bv->runs();
print "@bvruns\n";                                     # 111  00  1   ``````

Each element of the array that is returned by `runs()` is a string of either 1's or 0's.

set_bit()

With array-like indexing, you can use this method to set the individual bits of a previously constructed bitvector. Both positive and negative values are allowed for the bit position index. The method takes two explicit arguments, the first for the position of the bit you want to set and the second for the value of the bit.

``````    \$bv = Algorithm::BitVector->new( bitstring => '1111' );
\$bv->set_bit(0,0);                                # set the first bit to 0
\$bv->set_bit(1,0);                                # set the next bit to 0
print \$bv;                                        # 0011
\$bv->set_bit(-1,0);                               # set the last bit to 0
\$bv->set_bit(-2,0);                               # set the bit before the last bit to 0
print \$bv;                                        # 0000       ``````

set_slice()

You can set a slice in a given BitVector by calling this method. It takes two arguments, with the first argument as the range of the position index values at which you want to set the bits and the second argument the bit values at those positions.

``````    \$bv =  Algorithm::BitVector->new( intVal => 63437, size => 16 );
\$values_bv = Algorithm::BitVector->new( bitlist => [1,1,1,1] );
\$bv->set_slice( [4..8], \$values_bv );
print "BitVector after set_slice():  \$bv\n";     # 1111111111001101``````

When specifying the index values with the range operator in the form `i..j`, you would be setting the bits at the positions `i` through `j-1`.

set_value()

This method can be used to change the bit pattern associated with a previously constructed bitvector:

``````    \$bv = Algorithm::BitVector->new( intVal => 7, size => 16 );
print \$bv;                                 # 0000000000000111
\$bv->set_value( intVal => 45 );
print \$bv;                                 # 101101    ``````

You can think of this method as carrying out an in-place resetting of the bit array in a bitvector. The method does not return anything.

shift_left()

If you want to shift a bitvector non-circularly to the left, this is the method to call:

``````    \$bv = Algorithm::BitVector->new( bitlist => [1,1, 1, 0, 0, 1] );
\$bv->shift_left(3);
print \$bv;                                                  # 001000
\$bv = Algorithm::BitVector->new( bitlist => [1,1, 1, 0, 0, 1] );
\$bv->shift_left(3)->shift_right(3);
print \$bv;                                                  # 000001 ``````

As the bitvector is shifted non-circularly to the left, the exposed bit positions on the right are filled with zeros. Note that the method returns the bitvector object on which it is invoked. That is the reason why the chained invocation of the method in the fifth statement above works.

shift_right()

If you want to shift a bitvector non-circularly to the right, this is the method to call:

``````    \$bv = Algorithm::BitVector->new( bitlist => [1,1, 1, 0, 0, 1] );
\$bv->shift_right(3);
print \$bv;                                                  # 000111
\$bv = Algorithm::BitVector->new( bitlist => [1,1, 1, 0, 0, 1] );
\$bv->shift_right(3)->shift_right(2);
print \$bv;                                                  # 000001 ``````

As the bitvector is shifted non-circularly to the right, the exposed bit positions on the left are filled with zeros. Note that the method returns the bitvector object on which it is invoked. That is the reason why the chained invocation of the method in the fifth statement above works.

test_for_primality()

If the integer value of a bitvector is small (meaning smaller than `0x7f_ff_ff_ff`), you can use this method to test it for its primality through the Miller-Rabin probabilistic test:

``````    \$p = 7417;
\$bv = Algorithm::BitVector->new( intVal => \$p );
\$check = \$bv->test_for_primality();
print "The primality test for \$p: \$check\n";
# The primality test for 7417: is a prime with probability 0.99993896484375 ``````

The method returns one of two strings: If the primality test succeeds, the method returns a string like "`is a prime with probability xxxxx`". And if the test fails, the method returns the string "`is NOT a prime`".

unpermute()

This method reverses the permutation carried out by a call to the `permute()` method as shown below:

``````    \$bv1 = Algorithm::BitVector->new( intVal => 203, size => 8 );
print \$bv1;                                                   # 11001011
\$bv2 =  \$bv1->permute( [3, 2, 1, 0, 7, 6, 5, 4] );
print \$bv2;                                                   # 00111101
\$bv3 = \$bv2->unpermute( [3, 2, 1, 0, 7, 6, 5, 4] );
print \$bv3;                                                   # 11001011``````

The method returns a new bitvector with unpermuted bits. Also note that the method throws an exception if the permutation list is not as long as the size of the bitvector on which the method is invoked.

write_to_file()

This method writes the bitvectors in your program to a disk file:

``````    \$bv1 = Algorithm::BitVector->new( bitstring => '00001010' );
open my \$FILEOUT, ">test.txt";
\$bv1->write_to_file( \$FILEOUT );
close \$FILEOUT;``````

The size of a bitvector must be a multiple of 8 for this write method to work. If this condition is not met, the method will throw an exception.

Important for Windows Users: When writing an internally generated bitvector out to a disk file, it may be important to open the file in the binary mode, since otherwise the bit pattern `00001010' ('\n') in your bitstring will be written out as 0000110100001010 ('\r\n') which is the line break on Windows machines.

REQUIRED

This module imports the following modules:

``````    Math::BigInt
List::Util
Math::Random
Fcntl``````

THE `Examples` DIRECTORY

The `Examples` directory contains the following script that invokes all of the functionality of this module:

``    BitVectorDemo.pl``

In case there is any doubt about how exactly to invoke a method or how to use an operator, please look at the usage in this script.

None by design.

BUGS

Please notify the author if you encounter any bugs. When sending email, please place the string 'BitVector' in the subject line.

INSTALLATION

Download the archive from CPAN in any directory of your choice. Unpack the archive with a command that on a Linux machine would look like:

``    tar zxvf Algorithm-BitVector-1.26.tar.gz``

This will create an installation directory for you whose name will be `Algorithm-BitVector-1.26`. Enter this directory and execute the following commands for a standard install of the module if you have root privileges:

``````    perl Makefile.PL
make
make test
sudo make install``````

If you do not have root privileges, you can carry out a non-standard install the module in any directory of your choice by:

``````    perl Makefile.PL prefix=/some/other/directory/
make
make test
make install``````

With a non-standard install, you may also have to set your PERL5LIB environment variable so that this module can find the required other modules. How you do that would depend on what platform you are working on. In order to install this module in a Linux machine on which I use tcsh for the shell, I set the PERL5LIB environment variable by

``    setenv PERL5LIB /some/other/directory/lib64/perl5/:/some/other/directory/share/perl5/``

If I used bash, I'd need to declare:

``    export PERL5LIB=/some/other/directory/lib64/perl5/:/some/other/directory/share/perl5/``

THANKS

The bug in the primality test function, whose fix resulted in Version 1.21, was reported by Dana Jacobsen in a bug report filed at `rt.cpan.org`. Thanks Dana!

The restriction on the Perl version was removed on Slaven Rezic's recommendation. He says the module runs fine with Perl 5.8.9. Thanks Slaven!

Austin Nobis reported a documentation error in Version 1.24 which was fixed in Version 1.25. Thanks Austin!

AUTHOR

The author, Avinash Kak, recently finished a 17-years long "Objects Trilogy Project" with the publication of the book "Designing with Objects" by John-Wiley. If interested, visit his web page at Purdue to find out what this project was all about. You might like "Designing with Objects" especially if you enjoyed reading Harry Potter as a kid (or even as an adult, for that matter).

For all issues related to this module, contact the author at kak@purdue.edu

If you send email, please place the string "BitVector" in your subject line to get past the author's spam filter.

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

`` Copyright 2018 Avinash Kak``