Bitwise manipulation is when we perform a logical operation against each individual bit of a binary number. The logical connectives a.k.a. the bitwise operatorsAND, OR, and XOR can be used as masks that can affect the specific bits.
What is the point of Bitwise manipulation?
Human readability is certainly not the point, but speed and efficiency are. Bitwise operations are primitive actions that can be executed directly on the CPU meaning that they stake up less temporary/persistent storage and require less pre-processing overhead to compute. You can think of them like shortcuts.
AND
The AND logical operation can be used to turn off certain bits of a binary number, because:
1 AND 0 is 0
0 AND 0 is 0
Consider you have an input of 1101 1011 and a bitwise mask of 1111 1000. Examine the function table below:
Input
1
1
0
1
1
0
1
1
Mask
1
1
1
1
1
0
0
0
Result
1
1
0
1
1
0
0
0
Bitwise AND Mask Results
Notice that the mask only applies to the last three digits. The third to last digit is unchanged only because it was already 0.
OR
The AND logical operation can be used to turn off certain bits of a binary number, because:
1 AND 0 is 0
0 AND 0 is 0
Consider you have an input of 1001 1011 and a bitwise mask of 1110 0000. Examine the function table below:
Input
1
0
0
1
1
0
1
1
Mask
1
1
1
0
0
0
0
0
Result
1
1
1
1
1
0
1
1
Bitwise OR Mask Results
Notice that only the first three digits changed (except the first digit which was already a 1). The OR switch changed all the 0 bits to 1’s.
XOR
The XOR (Exlusive OR) logical function can be used to reverse certain bits of a binary number, because:
0 XOR 1 is 1
1 XOR 1 is 0
Consider you have an input of 1011 1001 and a bitwise mask of 0000 1111. Examine the function table below:
Input
1
0
1
1
1
0
0
1
Mask
0
0
0
0
1
1
1
1
Result
1
0
1
1
0
1
1
0
Bitwise XOR Mask Results
Notice that all four of the bits aligned with the mask are now the opposite of what they once were without exceptions. The bits have essentially been “flipped”.
Logical Shift Left
Performing a logical shift one bit to the left on a binary number means:
Moving all the bits of the number one place to the left
Discarding the most significant bit
Putting a 0 into the empty place on the right
Interestingly this is equivalent to multiply our binary number by 2. Notice that performing a logical shift three bits to the left on a binary number is the same as multiplying the number by 23 = 8.
Example:
If we start with the decimal number 14, three logical shifts to the left of its binary form results in the decimal number 112:
128
64
32
16
8
4
2
1
1410
0
0
0
0
1
1
1
0
2810
0
0
0
1
1
1
0
0
5610
0
0
1
1
1
0
0
0
11210
0
1
1
1
0
0
0
0
Logical Shift Left Results
Logical Shift Right
Performing a logical shift one bit to the right on a binary number means:
Moving all the bits of the number one place to the right
Discarding the least significant bit
Putting a 0 into the empty place on the left
As you might have guessed, this is equivalent to dividing our number by 2. Notice that performing a logical shift two bits to the right on a binary number is the same as dividing the number by 22 = 4.
Example:
If we start with the decimal number 112, two logical shifts to the right of its binary form results in the decimal number 28:
As discussed in the previous post, compound predicates are built from other predicates and propositions using logical connectives (¬, ∧, ∨, ⇒, ↔). The truth value of the compound predicate depends on the truth values of its components.
Truth tables can be used to define the meaning of logical operators and to investigate compound expressions. By investigating the truth values of compound expressions, you can establish new logical concepts. This is especially useful when it comes to rewrite rules which we will discuss a little bit later on.
Components of a Truth Table
Truth tables consists of a header and a body. When defining the meaning of a logical connective, the leftmost column lists the variable you are evaluating and the rightmost column lists the connective.
Example:
This truth table defines the conjunction connective. By looking at this truth table we can see that if P and Q both have a truth value of TRUE then the expression P ∧ Q also has a truth value of TRUE, but any other combination of P and Q means that the truth value of P ∧ Q is FALSE.
When investigating the truth value for a compound expression, the left most column headers list the variables and the rightmost header lists the compound expression.
The Body of a truth table always contains one row for every possible combination of the variables involved.
Note: The variables in a truth table are propositional variables. This allows you to work with the most simplified form of possible combinations and outcomes.
Here are truth tables for all of the logical connectives:
Note: Regarding the truth table for the Disjunction connective, this table shows the truth values for what is referred to as the inclusive or. This means that the proposition evaluates to TRUE if P and Q are both TRUE. You may encounter times when the exclusive or is specified (sometimes called XOR or EOR). This simply means that one of the criterion must be true but not both.
Equivalence and Implication
These two connectives may not be as immediately apparent or intuitive and the others so I think they warrant a bit more discussion.
Equivalence
This one isn’t too bad. It’s basically the same as the = operator (Note to self: check thesaurus for “same as”). It evaluates to TRUE if and only if the two involved propositional variables evaluate to the same truth value (either both TRUE or both FALSE).
Implication
This one is a bit more confusing because of the way “implies” is used informally versus its mathematical logical meaning. To better explain what the Implication connective means, I think it would be easier to start with what it doesn’t mean:
It doesn’t mean “suggests”.
It doesn’t mean “causes”.
The following sentence is completely logical under the mathematical definition of Implication:
“The sky is blue implies January is a month”
This does not mean “Since the sky is blue January is a month” or “January is a month because the sky is blue”
Note: Always remember that the ONLY time that an implies statement is FALSE is if the Antecedent (P) is TRUE but the Consequent (Q) is FALSE.
So let’s take a closer look at the Implication truth table again:
To better understand this, it might be better to evaluate the conditions in stages. We will start by examining the truth values for P. If the truth value for P is FALSE, we aren’t even going to check what the truth value for Q is because we already know that the expression is TRUE. If P is TRUE then we have to go on to evaluate if Q is TRUE, if it is the expression is TRUE, but if it isn’t then the expression is FALSE.
I like to think of this as “Innocent until proven guilty” or “True until proven false”.
Example:
Proposition: If your pet is a dog, then your pet is a male.
Suppose my pet is a dog… ok now I can check the gender… it turns out my dog is male… the statement must be true
Suppose my pet is a dog… ok now I can check the gender… it turns out my dog is female… I’ve proven the statement false
Suppose my pet is a cat… ok I could check the gender but it doesn’t really matter because the statement only applies to dogs so I wouldn’t be proving anything even if my cat was female… without evidence to prove that the statement wrong, I must assume that it is true.
Suppose my pet is a bird… same logic applies as if my pet was a cat… without evidence to prove that the statement wrong, I must assume that it is true.
Implication is probably the least intuitive of all the connectives and some of that probably comes from how we think about “implications” outside of mathematics. Let’s consider for a moment why this is.
Consider the following scenario:
I have a bag of 10 marbles. One is blue and nine are yellow.
I ask you to pick one marble out of the bag without looking and offer the following implication:
“If you pick a blue marble, the next will be yellow”
So you pick a marble:
Suppose I pick a blue marble… ok now I can pick another marble… it turns out it is yellow… The statement must be true. (T ⇒ T) = T
Suppose I pick a blue marble… ok now I can pick another marble… it turns out it is blue… The statement must be false. (T ⇒ F) = F
Those two seem pretty intuitive right? So let’s look at the tricky ones:
Suppose I pick a yellow marble… ok now I can pick another marble… it turns out it is also a yellow marble… ok so I don’t have enough information to know if the original statement is true or not. In real life if a friend asked me to do this and draw a conclusion I would say that there isn’t enough information to determine if it is TRUE or FALSE because the first marble I drew wasn’t blue so can’t actually test the hypothesis. Ahhh but let’s remember our definition of a proposition: a declarative sentence that when evaluated is either TRUE or FALSE, but not both.
By definition, our implication proposition MUST evaluate to either TRUE or FALSE, it cannot be both or neither. So now the question really becomes given this scenario, do we assume FALSE or do we assume TRUE? When it comes to implication, we always assume TRUE. This is why I use the phrase “innocent until proven guilty”. Just like in a court of law, the defendant is innocent until they can be proven guilty. Likewise when it comes to an implication, we assume that the overall statement (P ⇒ Q) is TRUE unless we can definitively prove that it is FALSE.
Predicate Strength
You can think about Implication as “ordering” the predicates that make up its operands. This order is referred to as the strength of the predicate. The “strongest” predicate is the one that implies the other. Consider P ⇒ Q, in this situation P is the stronger predicate and Q is the weaker.
Example:
The variable x is defined with a type of integer.
Consider the predicate: x > 5 ⇒ x > 0
To state that x is greater than 5 implies that x is greater than 0. This implication is TRUE regardless of the value of x, and the predicate x > 5 is the stronger predicate while x > 0 is the weaker one.
The only time that both predicates are of equal strength is when P ⇒ Q and Q ⇒ P. When the predicates are of equal strength they are equivalent: ↔
We use cookies on our website to give you the most relevant experience by remembering your preferences and repeat visits. By clicking “Accept”, you consent to the use of ALL the cookies. You can review our cookie policy here.
This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
