Re: bitwise operators

I think that adequate explanation has been given to your question about how bitwise operations work, so I won't talk about that. You did ask though, how they could be useful, and there are many different areas in which bitwise operations are important, including cryptography, internal database management, graphical rendering engines, and algorithms. I do not want to bore/overwhelm you with complex examples, but here are a couple of general ideas behind thier use.

1. Cryptography
This is a very simple example, but still very powerful.

Bitwise Operators can play a very important role in cryptographic/masking algorithms. For example, say that you had a piece of binary data, for simplicity, these 15 bytes:

This is a test.

You also have a 15 byte "mask", a string of random bytes, the same length as the length of the string to be masked. Again, for simplicity, lets say the (obviously not very random) mask is:

abcdefghijklmno

To encode the orginal data, you would apply the mask "abcdefghijklmno" to the data "This is a test." You would do this by using the XOR bitwise operation.

THE XOR OPERATOR

The XOR operator works on bits in the same ways as explained in previous responses. The XOR test is true(1) if the two bits that are being compared are different(1 and 0), or false(0) if they are the same. Therefore, performing the XOR operation on the following 2 bytes would work as shown:

10010111
01011100
-----------
11001011

Now, lets look at the last 2 bytes in the above example and XOR them:

01011100
11001011
-----------
10010111

You get the original piece of data back!
Getting back to our 15 byte example, if you XOR "This is a test." with "abcdefghijklmno", you will get a 15 byte piece of "masked data", that is hopelessly encoded and cannot be decoded by anyone without our incredibly secure and hard to guess mask. This new masked data(which is not shown here, it turns out to be ugly, hard to display binary), can be reverted back to the original by XORing it with the mask to obtain the data, or the data to obtain the mask. This is probably the most secure way to well, secure data, because since the mask is random(usually), the masked data can be just as easily be reverted back to the string "No test here..." using another mask.

2. Internal data structures
Bitwise operators can be used to manipulate data in a very efficient way that has been stored in bit fields, used in many areas including video games and 3D vector engines. It is also important in advanced mathematical algorithms. Instead of providing more, drawn out examples, I will provide you with the following sources, if you are still interested.

Mastering Algorithms with Perl -- Explains the use of bit vectors in mathematical algorithms and Encrypting data using the XOR method I discussed.

http://www.cs.cf.ac.uk/Dave/PERL/node36.html -- Discusses bitwise operators including bitwise shifts

Programming Perl -- General information about bitwise operations, probably the book you are already reading

CPAN also has some interesting/useful modules including Tie::VecArray and Bit::Vector.
There is a site with some really good information on this topic, I can't find it at the moment, I will update this node with the information when I find it though.

Hope this helps,
tigervamp

Comment on Re: bitwise operators

Replies are listed 'Best First'.
Re: Re: bitwise operators by mattr (Curate) on May 29, 2001 at 15:42 UTC
Wow these responses are wonderful. Makes me want to dive in.. But to keep it simple, I always remember "AND and OR, multiply and plus." That's because with single-digit binary numbers, AND gives you the same result as multiplication and the same goes for OR and addition. (A truth table, which shows the grid of all possible pairs and the result you get for a given operation, is helpful.) Understanding binary is good in Perl when you want to check the return value of a system function, since it may look like 128 for example but you know it is just the 8th bit that is set to 1. You can shift that bit left or right to simulate multiplication or division by two. Binary logic is also the fundamental idea behind the operators "and", "or", "\|", "\|\|", "&", and "&&". If you ever use all capitals constants for system control you are probably using binary without realizing it. You also need to know what you are doing here when you tie a database or use other routines that let you hand them a number of boolean (single bit) flags. Also if you are doing Perl in windows or talking to a C program, you may very well need to set "flags" or use a "bit mask". For example, say you have a window drawing function and it treats each bit of an argument as a display option. Perhaps the second bit means "the window has beveled edges" and the fourth bit means "vertical scrollbar should be displayed". Then you would want to set both bits to specify both options, in other words take a string of 8 zeroes and set the second and fourth bits to ones (usually we count right to left so the first bit is on the right). In base two you get 00001010 (in base two, or binary) or 2^1 + 2^3 = 2+8 = 10 (in base 10). Now If you got the current setting and it was 8 (scrollbar displayed) and you wanted to add bevelled edges, you could add (binary OR) that value (8, or in binary 00001000) with your bit mask (10, or in binary 00001010). Since OR is like addition, it makes sense that every digit set to one in your mask will become set. Likewise, if you had used AND, every bit set to zero in your mask would be cleared because anything AND 0 is like multiplying. by zero. Usually these display options are given all capitals names like V_SCROLLBAR and BEVELED_EDGE. Then if you have a function DrawWindow that takes three bytes (x, y, and type) as arguments, you can draw a window at coordinates x and y with something like DrawWindow(x,y,V_SCROLLBAR\|BEVELED_EDGE). So the more bits you have, the more options you can set. This is really the front end for the C or C++ code in which the function was originally written, and the byte size of each argument is predefined. This means that you can only specify up to eight window options at once if type is only one byte long. So you may see a function called something like DrawWindowEx which might be a function that might allows many more settings because it had a 32 bit (4 byte) argument. Another example is this snippet from DB_File.pm: sub LOCK_SH { 1 } sub LOCK_EX { 2 } sub LOCK_NB { 4 } sub LOCK_UN { 8 } ... unless (flock (DB_FH, LOCK_EX \| LOCK_NB)) { .... } That means a file lock on the file handle DB_FH is being requested and that the lock should be both exclusive and nonblocking. Unless flock returns a number greater than 0, the .... code is executed. So now you can read this too: $db = tie(%db, 'DB_File', '/tmp/foo.db', O_CREAT\|O_RDWR, 0644) \|\| die "dbcreat /tmp/foo.db $!"; You see someone (Paul Marquess, writer of that module) was trying to tie a hash variable (db) to a file (foo.db) using the DB_File module and opening the database file with file creation and Read/Write permission. In the last line of code above, you see bitwise OR (single pipemark) being used to add two flags, and you also see logical OR (double pipe, synonymous with "or") which will cause the "die" code to be executed if Perl decides it needs to look at it to evaluate the entire line. It is neat that "die" is not looked at if what comes before the double pipe is true, since in bitwise addition you already know the answer if you can tell the first value of your pair of binary digits is true (i.e. set to one). So binary logic is pretty important in Perl! By the way if you are curious what kind of constants are out there, you can check out Fcntl.pm, or (in unix) try "man fcntl" to see what the values are on your system. A Windows programmer's guide will also be full to the brim with these all caps flags.	[reply]

Replies are listed 'Best First'.

Re: Re: bitwise operators
by mattr (Curate) on May 29, 2001 at 15:42 UTC

But to keep it simple, I always remember
"AND and OR, multiply and plus."

That's because with single-digit binary numbers, AND gives you the same result as multiplication and the same goes for OR and addition. (A truth table, which shows the grid of all possible pairs and the result you get for a given operation, is helpful.)

Understanding binary is good in Perl when you want to check the return value of a system function, since it may look like 128 for example but you know it is just the 8th bit that is set to 1. You can shift that bit left or right to simulate multiplication or division by two.

Binary logic is also the fundamental idea behind the operators "and", "or", "|", "||", "&", and "&&". If you ever use all capitals constants for system control you are probably using binary without realizing it. You also need to know what you are doing here when you tie a database or use other routines that let you hand them a number of boolean (single bit) flags.

Also if you are doing Perl in windows or talking to a C program, you may very well need to set "flags" or use a "bit mask". For example, say you have a window drawing function and it treats each bit of an argument as a display option. Perhaps the second bit means "the window has beveled edges" and the fourth bit means "vertical scrollbar should be displayed". Then you would want to set both bits to specify both options, in other words take a string of 8 zeroes and set the second and fourth bits to ones (usually we count right to left so the first bit is on the right). In base two you get 00001010 (in base two, or binary) or 2^1 + 2^3 = 2+8 = 10 (in base 10).

Now If you got the current setting and it was 8 (scrollbar displayed) and you wanted to add bevelled edges, you could add (binary OR) that value (8, or in binary 00001000) with your bit mask (10, or in binary 00001010). Since OR is like addition, it makes sense that every digit set to one in your mask will become set. Likewise, if you had used AND, every bit set to zero in your mask would be cleared because anything AND 0 is like multiplying. by zero.

Usually these display options are given all capitals names like V_SCROLLBAR and BEVELED_EDGE. Then if you have a function DrawWindow that takes three bytes (x, y, and type) as arguments, you can draw a window at coordinates x and y with something like DrawWindow(x,y,V_SCROLLBAR|BEVELED_EDGE).

So the more bits you have, the more options you can set. This is really the front end for the C or C++ code in which the function was originally written, and the byte size of each argument is predefined. This means that you can only specify up to eight window options at once if type is only one byte long. So you may see a function called something like DrawWindowEx which might be a function that might allows many more settings because it had a 32 bit (4 byte) argument.

Another example is this snippet from DB_File.pm:

sub LOCK_SH { 1 }
sub LOCK_EX { 2 }
sub LOCK_NB { 4 }
sub LOCK_UN { 8 }

...

unless (flock (DB_FH, LOCK_EX | LOCK_NB)) { .... }

That means a file lock on the file handle DB_FH is being requested and that the lock should be both exclusive and nonblocking. Unless flock returns a number greater than 0, the .... code is executed.

So now you can read this too:

$db = tie(%db, 'DB_File', '/tmp/foo.db', O_CREAT|O_RDWR, 0644)
|| die "dbcreat /tmp/foo.db $!";

You see someone (Paul Marquess, writer of that module) was trying to tie a hash variable (db) to a file (foo.db) using the DB_File module and opening the database file with file creation and Read/Write permission.

In the last line of code above, you see bitwise OR (single pipemark) being used to add two flags, and you also see logical OR (double pipe, synonymous with "or") which will cause the "die" code to be executed if Perl decides it needs to look at it to evaluate the entire line. It is neat that "die" is not looked at if what comes before the double pipe is true, since in bitwise addition you already know the answer if you can tell the first value of your pair of binary digits is true (i.e. set to one). So binary logic is pretty important in Perl!

By the way if you are curious what kind of constants are out there, you can check out Fcntl.pm, or (in unix) try "man fcntl" to see what the values are on your system. A Windows programmer's guide will also be full to the brim with these all caps flags.

[reply]