Home arrow Perl Programming arrow Page 3 - More Perl Bits

Bit vectors - Perl

In the last article, I talked about the need to work at the bit level in Perl and in other languages. In order to understand bits, we first took a look at how binary numbers are represented in Perl, and then we took a look at two bitwise operators, AND and OR. In looking at the operators, we looked at their most common uses in programming. We also began to look at an algorithm for finding prime numbers, but we stopped upon seeing that there is no easy implementation, at least not without a knowledge of bits.

TABLE OF CONTENTS:
  1. More Perl Bits
  2. Bit shift operators
  3. Bit vectors
  4. The vec function
  5. Finding prime numbers
By: Peyton McCullough
Rating: starstarstarstarstar / 1
September 14, 2009

print this article
SEARCH DEV SHED

TOOLS YOU CAN USE

advertisement
 

Up until now, we've just been storing plain binary numbers as scalars and then manipulating them with various bit operators. This is fine for many operations, but there are some serious disadvantages to it. First, we're limited to a certain number of bits (32 bits of 64 bits, depending on your machine). If we go over this, we'll get an error. Second, they are a bit difficult to work with. Extracting the value of a particular bit or set of bits requires some ugly code. 

Now is actually a good time to return to the Sieve of Eratosthenes algorithm that we examined at the beginning of the previous article. Recall that in order to implement the algorithm, we needed a way to eliminate non-prime numbers from a list. We looked at two ways to do this, but both were horribly inefficient. The second method, however, was heading in the right direction. 

In the second method, we had a large array whose indexes were the actual numbers (we would start at 2, discarding 0 and 1, since the latter two are not prime). If the value at a particular index was 1, then we knew the number represented by the index was prime. Otherwise, it was not prime. 

This is inefficient because the numbers 0 and 1 are still going to be treated as integers, and that requires quite a bit of memory. However, you know that only one bit is required to represent either value. So, why not just use one bit? Well, because we can't just create a normal array of “bits.” We can, however, create a bit vector. 

A bit vector is simply a long sequence of bits which may be divided up into individual units of data, or elements. These elements are sets of bits that may have varying sizes, depending on what exactly we want to store. In our situation, we only need to store one of two values, so each unit only needs to have one bit. 

So, if we're storing prime numbers from 0 to 10, we'd have a bit vector that looks like this internally:

 

00110101000

 

This indicates that the numbers 2, 3, 5 and 7 are prime, and that the numbers 0, 1, 4, 6, 8, 9 and 10 are not prime. 



 
 
>>> More Perl Programming Articles          >>> More By Peyton McCullough
 

blog comments powered by Disqus
escort Bursa Bursa escort Antalya eskort
   

PERL PROGRAMMING ARTICLES

- Perl Turns 25
- Lists and Arguments in Perl
- Variables and Arguments in Perl
- Understanding Scope and Packages in Perl
- Arguments and Return Values in Perl
- Invoking Perl Subroutines and Functions
- Subroutines and Functions in Perl
- Perl Basics: Writing and Debugging Programs
- Structure and Statements in Perl
- First Steps in Perl
- Completing Regular Expression Basics
- Modifiers, Boundaries, and Regular Expressio...
- Quantifiers and Other Regular Expression Bas...
- Parsing and Regular Expression Basics
- Hash Functions

Developer Shed Affiliates

 


Dev Shed Tutorial Topics: