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 0 | Bit 1 | Bit 0 & Bit 1
| | false | true | false
| | false | false | false
| | true | true | true
| | true | false | false
|
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 0 | Bit 1 | Bit 0 | Bit 1
| | false | true | true
| | false | false | false
| | true | true | true
| | true | false | true
|
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
| | false | true
| | true | false
|
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 0 | Bit 1 | Bit 0 ^ Bit 1
| | false | true | true
| | false | false | false
| | true | true | false
| | true | false | true
|
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
|
Re: Bit operations for beginners
by liz (Monsignor) on Aug 08, 2003 at 15:16 UTC
|
$a = 0;
$b = 0;
$c = $a++ && $b++; # only $a++ is evaluated
print "a = $a, b = $b\n"; # prints "a = 1, b = 0"
And:
$a = 0;
$b = 0;
$c = ++$a || ++$b; # only ++$a is evaluated
print "a = $a, b = $b\n"; # prints "a = 1, b = 0"
Otherwise I think this can go to Tutorials as well...
Liz | [reply]
[d/l]
[select] |
|
|
Ups :( I even proofread it 5-6 times... Remember, always have someone else proofread it too...
T
I
M
T
O
W
T
D
I
| [reply]
[d/l] |
Re: Bit operations for beginners
by halley (Prior) on Aug 08, 2003 at 14:19 UTC
|
It's a good start at a useful topic for those who haven't gone through a basic Boolean algebra course (such as electrical logic or an optional part of high school algebra).
I would even recommend this move into Tutorials, if you could tighten up the topic a little more and pay a little more attention to grammar, readability and markup. I'd probably recommend you refer to ~ as the bitwise 'inverse' operator instead of the bitwise 'not' operator, to reduce a little confusion.
The parts about using bitwise operators on strings or characters may be more clear if pulled out into a separate section: bitwise strings is just like a loop, performing bitwise operations on each character position in the pair of strings.
Also, instead of briefly explaining logical operators (! not && and || or), and the use of DeMorgan's Theorem, just leave a caveat that these aren't bitwise operators-- plenty of material for a follow-up tutorial.
--
[ e d @ h a l l e y . c c ] | [reply]
[d/l]
[select] |
Re: Bit operations for beginners
by theorbtwo (Prior) on Aug 08, 2003 at 15:33 UTC
|
Just a little nit -- the 2nd paragraph seems to equate the and and & operators. This is incorrect, and is && (and a special low-precdence version of it, at that).
Other then that, and the other nits mentioned by liz and halley, it looks quite nice. You've got my ++, and tutorials vote if you fix them up.
Update: s/browseruk/halley/
Warning: Unless otherwise stated, code is untested. Do not use without understanding. Code is posted in the hopes it is useful, but without warranty. All copyrights are relinquished into the public domain unless otherwise stated. I am not an angel. I am capable of error, and err on a fairly regular basis. If I made a mistake, please let me know (such as by replying to this node).
| [reply] |
Re: Bit operations for beginners
by Limbic~Region (Chancellor) on Aug 08, 2003 at 17:19 UTC
|
Cine,
I would also like to see this cleaned up so it could be considered for Tutorials. With that in mind, I have one more nit.
You may be surprised that it is not the "!" operator, which is more known as the "not" operator, but that is because "~" is the "bitwise not" operator.
The "!" operator is used to reverse a true value to false and not actually looking at the specific bits.
I would change 'which is more known as' to 'which is more commonly known as'. I would change 'The "!" operator is used to reverse a true value to false' to 'The "!" operator is used to flip flop the truth of a value from true to false or false to true'.
Cheers - L~R | [reply] |
|
|
Additionally, '~' is more correctly called the (1's) complement operator, or bitwise negation operator, both according to perlop and, by its functionality, mathematics itself. Calling it the 'not' operator is confusing, imo.
| [reply]
[d/l] |
Re: Bit operations for beginners
by demerphq (Chancellor) on Aug 08, 2003 at 18:18 UTC
|
I always found it useful to have a chart of all of the boolean operators (and the symbolic logic operators) in one row. This shows all the possibilities at a glance, and also shows how there are "special" operators which can be used to construct all the rest. (NAND and NOR particularly). Another interesting thing to do is to create a binary tree with 4 levels and then mark off each leaf as representing a given operator (or identity), which reveals that there are several potentially useful binary operators which are almost never used.
Anyway, just thought id mention this as it seemed somewhat germane. :-)
---
demerphq
<Elian> And I do take a kind of perverse pleasure in having an OO assembly language...
| [reply]
[d/l] |
|
|
| [reply] |
|
|
Yep, thats the kind of thing I had in mind. Except that I find it useful to have a chart that has all of the posibile permutations of binary boolean operations. For one it makes it easier to see how you can construct operators from each other. But mostly because I personally find it interesting how the chart of possible operators can be interpreted in different ways, and how complete it is. For instance XOR is commonly used computing and engineering, but rarely in symbolic logic, whereas -> (the conditional) is the opposite.
Actually I've always found this chart to be fascinating and for lack of a better term, very "deep". The fact that the binary enumeration of 0-15 happens to encode all the binary operators (at least in a boolean sense), along with the unary NOT, identity and empty set, and that you can construct all from some, but not all from every is somewhat amazing to me. I guess its just psychobable but to me theres something special there. The first time I put one together I sort of felt like I had just discovered the boolean table of elements or something. Anyway, I digress. :-)
| Dec | Bin | | A | B | | 0 | !(A || B) | !A && B | !A | A && !B | !B | A ^ B | !(A && B) | A && B | A == B | B | !A || B | A | A || !B | A || B | 1 |
|---|
| 0 | 00 | | 0 | 0 | | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 01 | | 0 | 1 | | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 2 | 10 | | 1 | 0 | | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 3 | 11 | | 1 | 1 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| Dec | Bin | | A | B | | False
(1) | nor
neither
(2,8) | lt
(3,9) | ¬A
not A
(4) | gt
(3,9) | ¬B
not B
(4) | xor
ne
(5,8) | nand
(2,8) | and
both
conjunct.
A∧B
A•B
(8) | xnor
bicond.
eq
A≡B
(5,8) | B
(6) | A→B
A⊃B
le
cond.
(7,9) | A
(6) | B→A
B⊃A
ge
cond.
(7,9) | or
either
disjunct.
A∨B
A+B
(8) | True
(1) |
|---|
- (*)
These are included for completeness. They also have special properties, like A==A or 0,
B==B and 1.
-
These are interesting in that its fairly easy to construct any other operator from either alone.
- (**)Im not sure what to call these. Perhaps 'falsifies' as in 'B falsifies A' or 'A falsifies B'.
They are the reverse of the conditional or implication (see 7).
- (*)
Negation
- This is logical equality and logical inequality not the traditional perl value equivelence.
However using negation you can ensure perl value equivelence as well, ie !$a == !$b or
!$a != !$b (the later is better written $a ^ $b)
- (*)
Identity.
- (**)Conditional or implication. A implies B. This is only false when A is True and B is not True. Symbolic logic makes
heavy use of this operator, where it can be used to test the truth of assertions
like "if A then B".
- Commutative and associative. A op B == B op A and
( A op B ) op C == A op ( B op C
)
- Transitive and Non Associative. A op B != B op A.
If A op B
and B op C then A op C.
(*) It may be a bit strange to think of these as binary operators, but its not that big of a
stretch to do so. And in visualizing the relationships between the other more important operators I find
its useful to include them.
(**) 3 and 7 are interesting in that in effect they are the boolean equivelents of the relational operators.
Like you I order my chart as a mathematician, engineer or programmer would, and not as a philosopher (who usually use T and F and who "count" from True to False), nor as Cine did. In fact I find his ordering quite unusual, and might even venture to argue that it is plain "wrong" to do so. I certainly think that both of the latter approaches make visualizing the enumeration of the possible input/output states to be much less intuitive. (Actually the whole T/F and ordering thing really got my goat in certain classes in school.)
---
demerphq
<Elian> And I do take a kind of perverse pleasure in having an OO assembly language...
| [reply]
[d/l]
[select] |
|
|
|
|
Re: Bit operations for beginners
by Enlil (Parson) on Aug 08, 2003 at 17:41 UTC
|
| [reply] |
Re: Bit operations for beginners
by ido50 (Scribe) on Aug 09, 2003 at 14:50 UTC
|
First of all thanks Cine for the nice tutorial.
Second of all, if anyone looks for further information, Nathan Torkington had a nice article on The Perl Journal a few years back titled "What is Truth", which deals with "truth" as Perl's Bitwise and Boolean operators see it. The article was printed on issue 14 (1999) and can be viewed online here (Free, of course (-: ).
-------------------------
Live fat, die young | [reply] |
Re: Bit operations for beginners
by mrborisguy (Hermit) on Jun 22, 2005 at 00:15 UTC
|
I just have to be difficult, it's the way I am:
There are 4 bit operations, and, or, xor and inverse
It's been shown already in this thread, but not said yet that there are actually more than 4 bit operations. 'and', 'or', 'xor', and 'inverse' are the common ones used in Perl (and most of the programming languages that have crossed my path) and in fact any bit operator can be created using those - they're a complete set or something (actually, still complete without 'xor'); but technically they aren't the only four bit operators.
(Good work, by the way!) ++
-Bryan
| [reply] |
|
|
For two inputs, there are 16 operations. Most of them are rarely useful, which is why we don't have Perl operators for them.
By the way, everything can be implemented solely with nand:
p | q | p nand q
---+---+----------
0 | 0 | 1
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
not p === p nand p
p and q === (p nand q) nand (p nand q)
p or q === (p nand p) nand (q nand q)
p xor q === (p nand (q nand q)) nand ((p nand p) nand q)
Other operatations could also be used instead of nand. nor, for example:
p | q | p nor q
---+---+---------
0 | 0 | 1
0 | 1 | 0
1 | 0 | 0
1 | 1 | 0
~(p nor q)
not p === p nor p
p and q === (p nor p) nor (q nor q)
p or q === (p nor q) nor (p nor q)
p xor q === [something very long]
| [reply]
[d/l]
[select] |
|
|
p xor q === [something very long]
Hell's teeth! You weren't kidding.
I remember xor as (p and not q) or (q and not p) and it's been something like 30 years since I played with nand and nor expansions, so I expanded that:
xor === (p and not q) or (q and not p)
expand the 'not's
=== (p and (q nor q)) or (q and (p nor p))
expand the 'and's
=== ((p nor p) nor ((q nor q) nor (q nor q)))
or ((q nor q) nor ((p nor p) nor (p nor p)))
expand the 'or's
=== (((p nor p) nor ((q nor q) nor (q nor q)))
nor ((q nor q) nor ((p nor p) nor (p nor p))))
nor (((q nor q) nor ((p nor p) nor (p nor p)))
nor ((p nor p) nor ((q nor q) nor (q nor q))))
Then it struck me that ((x nor x) nor (x nor x)) is x, which reduces it to
=== (((p nor p) nor q) nor ((q nor q) nor p))
nor (((q nor q) nor p) nor ((p nor p) nor q))
It's certainly more digestable (just :), but are there any other reductions in there?
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
The "good enough" maybe good enough for the now, and perfection maybe unobtainable, but that should not preclude us from striving for perfection, when time, circumstance or desire allow.
| [reply]
[d/l]
[select] |
|
|
Re: Bit operations for beginners
by wagemonkey (Initiate) on Feb 04, 2005 at 17:37 UTC
|
You have defined XOR as (a&b) | (~a&~b) , surely this is the inverse of XOR ( the biconditional).
Shouldn't XOR be defined as (a&~b) | (~a&b)? | [reply]
[d/l]
[select] |
|
|
| [reply]
[d/l] |
Re: Bit operations for beginners
by ikegami (Patriarch) on Jun 21, 2005 at 21:26 UTC
|
I find it very odd (and incorrect) that bit ops are performed on booleans in the tables.
| [reply] |
|
|
Why? A boolean is either true or false. A bit is either 1 or 0. Commonly, boolean's are notated as 1 and 0, in fact, when we did boolean algebra in discreet structures, we always used 1's and 0's. I think it is very accepted and correct that bit ops are performed on booleans.
-Bryan
| [reply] |
|
|
Bits means, by definition, Binary digITS. "true" and "false" are not digits, but "0" and "1" are. Why use a reprentation when you can use an actual value?
Besides, it's vague. While 0 and 1 can be false and true, false and true can be more than 0 and 1. Why say "I like food" when you mean "I like chocolate"?
The term "boolean algebra" applies to both logical operators (for which values T and F are typically used) and bitwise operators (for which inputs 0 and 1 are typically used), so what you used in boolean algebra class is moot. Besides, you're not teaching boolean algrebra, you're teaching bitwise operators. What applies to one doesn't necesasrily apply to the other.
By the way, you might have noticed everyone else used 1s and 0s in their replies.
There's something else that's inconsistent. In the tables, Bit0 starts with 0/false then goes to 1/true, but Bit1 does the opposite. It makes for highly irregular (non-standard) and confusing tables. Look at the order everyone else used in their replies. They all used the same, standard order. Here it is for convenience:
or with three inputs:
| Bit0 | Bit1 | Bit2 |
|---|
| 0 | 0 | 0 |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| 1 | 1 | 1 |
etc.
| [reply] |
Re: Bit operations for beginners
by Anonymous Monk on Sep 16, 2003 at 08:25 UTC
|
Is there any perl module to help simplify boolean algebra?
If i feed it k-map, it comes up with solution, and simplifies it? thanks | [reply] |
|
|
