If you have been looking at bitcoins and in particular the SHA256 algorithm, you would have come across this formula:
Maj(x,y,z)=(x∧y)⊕(x∧z)⊕(y∧z)
Ch(x,y,z)=(x∧y)⊕(¬x∧z)
The first thing I said to myself was “What the heck does this mean? Do I need a PhD to understand this?”
Well, the good news is that the meaning is pretty simple and no you don’t need a PhD.
First of all, these are logic symbols that students studying logic use. Programmers don’t use these.
The upside down V (∧) means AND.
The circle with the plus inside (⊕) means XOR or eXclusive OR.
The bent line or garden hoe as I call it (¬) is the negation or a NOT.
Side note: V means OR.
AND is easy to understand.
0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1
ie both inputs need to be true for the output to be true.
Check out this example. 116 & 122 = 112. Why?
01110100 = 116 (t)
01111010 = 122 (z)
————–
01110000 = 112 (p)
If converted to ascii text, you get t & z = p. Cool eh?
XOR is a bit tricky. Basically the output is true when the inputs are different.
0 AND 0 = 0
0 AND 1 = 1
1 AND 0 = 1
1 AND 1 = 0
Negation is easy as well. Whatever the value is, make it the opposite.
0 => 1
1 => 0
Wikipedia (http://en.wikipedia.org/wiki/List_of_logic_symbols) has a full list of other symbols.
How does this relate to programming?
In the C language, these are bitwise operators. I’ll explain more below.
∧ becomes &
⊕ becomes ^ (caret)
¬ becomes ~
V become | (just for completeness)
So to represent this in C, it becomes:
#define CH(x,y,z) (((x) & (y)) ^ (~(x) & (z)))
But hang on. You might be wondering what && and || and ! mean? These also mean AND, OR and NOT respectively but these are logical operators, not bitwise operators. (Why did I not mention logical XOR? Because there isn’t one. Check out: http://benpfaff.org/writings/clc/logical-xor.html and see if that makes sense).
What’s the diff?
The logical operator works on boolean (true or false conditions) and the bitwise operator works on bits (1’s and 0’s).
What the heck does that mean?
Check out this example for logical operators. http://www.tutorialspoint.com/cprogramming/c_logical_operators.htm
And check out this example for bitwise operators.
http://www.tutorialspoint.com/cprogramming/c_bitwise_operators.htm
You’ll notice that generally speaking you’ll not need to use bitwise operators…. unless you want to play with 1’s and 0’s.