Home arrow Perl Programming arrow Page 2 - Perl, Bit by Bit

A bit of a need - Perl

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.

TABLE OF CONTENTS:
  1. Perl, Bit by Bit
  2. A bit of a need
  3. Representing binary numbers
  4. Operating on bits using bitwise operators
By: Peyton McCullough
Rating: starstarstarstarstar / 6
August 04, 2009

print this article
SEARCH DEV SHED

TOOLS YOU CAN USE

advertisement

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.



 
 
>>> 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: