Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
This is not really a Perl specific subject, but nonetheless a problem for people who are beginning to program.

There are 4 bit operations, and, or, xor and inverse, which in Perl is accessable as the character operators &, |, ^ and ~, because they are not to be confused with the actual and-, or- and not-operators, whom we will return to later. Because these operations are bit operations, they work on individual bits in a number, but as we shall see in Perl they also magically work on all the bits in strings.

Except for inverse they require two arguments also called operands, a left operand and a right operand. For none of these operations is it important which is the right or the left, they would yield the same result reversed. inverse only requires a single operand.

The & operator

This is the operator you use when you want to know need to know if two items both are true. true and false in bits are commonly respectively 1 and 0 or on and off
The truth schema, for and is
Bit 0Bit 1Bit 0 & Bit 1
falsetruefalse
falsefalsefalse
truetruetrue
truefalsefalse

Thus if we have the numbers 234 and 15, in bit representation 11101010 and 00001111 and do 234 & 15. We then for each bit in the left operand and it with the corresponding bit in the right operand and check the schema every time. Thus the result is 00001010 or 10 in decimal.

Using a char as example instead, we have an "A" and "a", respectively 01000001 and 01100001 in ASCII. If we and them together, we get 01000001 or "A".

The | operator

This operator check if either the right operand or the left operand is true, or if they are both true. Thus this is false, only when both operands are false.
The truth schema, for or is
Bit 0Bit 1Bit 0 | Bit 1
falsetruetrue
falsefalsefalse
truetruetrue
truefalsetrue

Again, our examples with 234 and 15 or 11101010 and 00001111. The result is now 11101111 or 239. And the example with "A" and "a" or 01000001 and 01100001 in ASCII, result is 01100001 or "a".

The ~ operator

The inverse operator only takes a single argument and simply reverses all bits. Thus all true values become false and all false values become true.
Bit 0~Bit 0
falsetrue
truefalse

This operator is actually also called the not operator, but most people associate that with the other operator with the same name, the ! operator. The distiction is that ~ is the "bitwise" not operator. The ! operator is used to reverse a true value to false and not actually looking at the specific bits. This is also how perl does it, everything else would surprise people, imagine what would happen if !"1", did it bitwise... 1 is 00110001, so !"1" would be 11001110 which in iso8859-1 is "LATIN CAPITAL LETTER I WITH CIRCUMFLEX"... But in perl !"1" is 0, which makes it false. Just to confuse the matter some more, ~ is also called the (1's) complement operator, or the bitwise negation operator.

Unlike what you also may imagine, ~234 is not 00010101, but 11111111111111111111111100010101... This is simply because Perl's representation of the number is much longer than a simple 8 bits. Also this is on my machine and my compiled version of Perl, on other machines or builds it may be longer or shorter.

Also notice that this does not work on a list. With @a=(1,0), print ~@a would not print "01", but will evaluate the length of the @a and invert that number.

The ^ operator

The XOR operator is not like, the other operators known from the common language, mostly because it is a composition of more operations.

XOR means eXclusive OR. Expressed in other bit operations it is (a&~b) | (~a&b). In more humane terms, it is this or that, but not both.
The truth schema, for ^ is
Bit 0Bit 1Bit 0 ^ Bit 1
falsetruetrue
falsefalsefalse
truetruefalse
truefalsetrue

You may wonder what this operator is used for, but if you think a little about it what is actually tells you is "are the operand identical?". In many cases we could have used == or eq to tell us that, but other times we actually need to know where and what the difference is. For example we have two very long strings "aaaa" and "aaba", and need to find where the difference is. The result of "aaaa"^"aaba" is "\0x00\0x00\0x03\0x00", we can then run tr/\0x00/1/c to get the number of bytes that are different and we can use index to then search for 1 in the string to find the actual place in the original string they differ.

The boolean operators

Boolean operators are much like their bitwise counterparts. We already looked at the ! operator, which turns a true value into a false and false values into true ones. Thus it is actually as though we converted the entire expression into a single bit and reversed that bit.

We also have && and ||, && works by evaluating the left operand, and if and only if that returns a true value the right operand is evaluated and that result is returned. || works similar, but only evaluates the left operand if the right operand was false.

Thus unlike their bitwise cousins, the ordering of operands is important here, just think of $a && $b/$a if $a is 0...

In the start I wrote that you should not confuse the and operator with the & operator, this is because and is the same as &&. Same goes for or which is the same as || and also ! which is not. The difference is that the named versions have lower precedens, which means that the implicit parentheses are put differently when Perl is looking at your code.

Conclusion

I now hope you have a better understanding of how bitwise operations work, and are able to understand why people sometimes do things like "onestring" ^ "anotherstring".

Here is a small tip, if you ever find yourself with a long complex boolean expression:
!a && !b && !c can be written as !(a || b ||c), and
!a || !b || !c as !(a && b && c)...
This is also known as DeMorgan's Theorem

Update: Fixed the errors liz pointed out
Update: Added link to DeMorgan's Theorem
Update: Rewrote "xxx" to xxx
Update: Changed 0 and 1 to true and false
Update: Rewrote bits and pieces
Update: XOR was wrong

T I M T O W T D I


In reply to Bit operations for beginners by Cine

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others browsing the Monastery: (14)
    As of 2014-12-18 09:03 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      Is guessing a good strategy for surviving in the IT business?





      Results (47 votes), past polls