When you program, you're usually doing it at some distance from the bits and bytes that your computer understands. There never seems to be a need to think about bits. But believe it or not, learning about bits can be to your advantage for certain programming purposes. Perl provides operators for working with bits that let you leverage this knowledge.
In the introduction, I made several claims about how helpful a knowledge of bits is, yet I offered no proof. After all, you may have been programming for quite some time without even giving a passing thought to working at the bit level. Even after reading this article, you may struggle to find applications for this knowledge. But they're there, I promise.
Let's start by looking at an algorithm for finding prime numbers, called the Sieve of Eratosthenes. Prime numbers may not be practical for most people, but I find them very interesting, and I think this example will illustrate some very important points. It's a very simple example demonstrating the need for bits.
So, what's the algorithm look like? Basically, you start with a list of numbers, from 2 (the lowest prime number) to whatever the maximum number you want to check for primality. Let's say we want to go from 2 to 15. The list would look like this:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
The algorithm involves crossing out numbers that aren't prime, but this is done in a systematic way. We start with the first number not crossed out, which is 2. Then, we cross out all of its multiples:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
We've made the first cut. Next, we have to find the next number that is not crossed out, which is 3. We cross out all of its multiples, just as we did with 2:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
We repeat this for every number less than the square root of the maximum number to be tested, and the remaining numbers are prime. In this case, the square root of 15 is just under 4, so we're done. All of the remaining numbers are prime:
2, 3, 5, 7, 11, 13
That's not very difficult at all. So, how do we represent this in Perl? It's very simple. All we need is a list of numbers on which to operate. A naïve solution is to create an array where each element is a number to be checked. So, we'd start with something like this:
my@numbers=(2,3,4,5,6,7,8,9,10,11,12,13,14,15);
Then, we could remove each non-prime number from the array as we encounter it, or make it zero or something. This works, but for larger arrays, this is extremely slow, and it's a waste of memory.
Another solution would be to make an array with values of 0 or 1 and use the indexes as the numbers. For example, if $numbers[2] is 1, then the number is prime. This is headed in the right direction, but it's really not any better than the first solution. Even if all you store in the elements are 0 and 1, Perl is still going to allocate more memory than you actually need. After all, you're still working with integers, and integers have quite a range, even if you don't take advantage of that range.
So, how do we implement this algorithm? By using bits, of course! We'll come back to this example at the end. Try to think of the exact solution as you read through this article.