Tangible Computing
5. Logical Operations on Bits



5.1 Basic Logic Operations

Although Aristotle is considered the Western philosophical founder of formal logic and reasoning, our modern approach to logic as an algebraic mathematical system is due to George Boole. In many programming languages, the logical type consisting of the two values, True and False, is called a boolean (but no such type exists in C). Boole is an intellectual founder of computing.

All programming languages make decisions (if, while, for, etc.) on the basis of the value of a conditional expression. Every conditional expression evaluates to True or False. Conditional expression are constructed with logical operators.

The simplest logical operation is negation. It is described with the following truth table. In the table we give the possible logical values of the arguments, True (T) and False (F), and the name of the operator. We give the logical name, not X, as well as the corresponding C operator, !X.

X not X
!X
F T
T F


So when Not is applied to the logical value, it results in the opposite value. True becomes False and False becomes True. Because there is only one argument to Not, it is called a unary operator. The next set of operations take two arguments, and are thus are examples of a binary operator. In addition, because the operator is between its two arguments it is called an infix operator.

X Y X AND Y
X && Y		 X OR Y
X || Y		 X IFF Y
X == Y		 X XOR Y
X != Y		 X IMPLIES Y
!X || Y
F F F F T F T
F T F T F T T
T F F T F T F
T T T T T F T


From the table we can see the following:
AND is only True when X and Y are True.
OR is inclusive or, and is only True when either X and/or Y is True.
IFF is 'if and only if', and is only True when X and Y have the same value.
XOR is exclusive or, and is only True if X or Y is True, but not when they have the same value.
IMPLIES can be phrased as, "if X occurs, then Y happens". It is possible for the result to be True if Y does or doesn't 'occur', but Y must be True if X 'occurs', which is why when X is True and Y is False, the result is False.
IMPORTANT: In C there is no logical data type. Integers (signed or unsigned) can be used as logical values, where 0 is false and non-0 is true. So you have to be careful, !0 is any non-0 value, and is not guaranteed to be the same non-0 value. So it is not necessarily the case that
!(!x) == x
Or
x == y, when both x and y are true
There are pros and cons to this interpretation, and we will discuss it more. But the main thing is that in C, != and == are NOT logical operators. First, you should review the notes: http://ugweb.cs.ualberta.ca/~c296/ConcreteComputing/section/logicalops.htm IMPORTANT: In languages without an explicit Boolean (logical) type, things can get tricky. In C there is no logical data type. Integers (signed or unsigned), or any other string of bits, can be used as logical values, where 0 is false and non-0 is true. So you have to be careful, !0 is any non-0 value, and is not guaranteed to always be the same non-0 value. So it is not necessarily the case that !(!x) == x Or x == y, when both x and y are true There are pros and cons to this interpretation, and we will discuss it more. But the main thing is that in C, != and == are NOT logical operators, they are comparisons between strings of bits. So, cache_has_data is intended to be a logical flag. If it is false (i.e. 0) then we want to read a new block, hence the ! cache_has_data (read as "not cache_has_data") in the condition of the if. According to the C standard, Calvin and Stefan are correct. ! 0 is required to be 1. But remember that true is not required to be 1, but most of the time it probably is because the result comes from a logical operation. But you should not rely on it being 1, so never do a test against 1 to see if something is true, it can result in some very strange bugs. I'm not sure what the standard is for other languages like Perl - have to check. Besides, why would you ever test if v is true by doing: if ( v == 1 ) { ... } when it is much clearer to say if ( v ) { ... }. I'm not sure what the standard is for other languages. Perl ensures that !0 is 1 , but it is not the case that (0 || x) is 1 if x is true. Perl has this useful behaviour that || returns the first non-0 value it encounters. So (0 || 3) is 3 , not 1.

5.2 DeMorgan's Laws

One of the most important collection of rules for manipulating logical formulas is DeMorgan's Laws They are
!(X && Y) == (!X) || (!Y)
!(X || Y) == (!X) && (!Y)
The && and || operators swap roles when the law is applied. This is an example of duality.

5.3 Logic and Bit Operations

If we let 0 represent false, and 1 represent true, then all of the above operations can be applied to a bit, or a pair of bits, as follows.

Note: There are different names for the operators. NOT is the tilde (~), AND is a single ampersand (&), OR is a vertical bar (|), and XOR is a caret (^).

X ~X
0 1
1 0


X Y X & Y X | Y X ^ Y
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0


When working with strings of bits of equal length, we can extend these operations by performing them pairwise. So when working with a byte, we do pairwise operations on all 8 bits. For example:

X 0000 0000 1111 1111 1101 0101
~X 1111 1111 0000 0000 0010 1010


X 0010 1101
Y 1010 1010
X & Y 0010 1000
X | Y 1010 1111
X ^ Y 1000 0111


Note how exclusive or, XOR, can be used with a mask to flip bits. Where the mask is 1, the corrseponding bit of the order argument is flipped.

5.4 Bit Shifting

The final bit operation we introduce is the left and right shift. The << operator is the shift left, and the >> is the shift right.

As a general rule, integers intepreted as bit strings should always be declared as unsigned. In these cases, the shift operators do what is expected, that is shift a 0 into any vacated position. Note, the left hand argument is not altered by the shift.

So x << n shifts the bits in x left n positions, putting 0 into the right hand bits that are vacated.

So x >> n shifts the bits in x right n positions, putting 0 into the left hand bits that are vacated.

If x is signed, then the right shift behaves differently. Instead of putting 0 into the vacated left positions, the leftmost digit is duplicated. So if x is positive, then 0 is shifted in, but if negative, then 1 is shifted in.

Here are code examples for the arduino:

Unsigned ints: code/Bits/Shifts01/Shifts01.ino

    #include <string.h>
    void setup()
    {
      Serial.begin( 9600 );
    }
     
    /*
      Examples of shifting unsigned ints
    */
     
    void loop()
    {
      uint16_t x;
      uint16_t y;
      uint16_t z;
      
      x = 0x00;
      Serial.println(x, HEX);
      y = ~x;
      Serial.println(y, HEX);
      
      for (uint8_t i = 0; i <= 16; i++ ) {
        Serial.print("i ");  Serial.print(i);
        z = y << i;
        Serial.print(", y << i "); Serial.print(z, HEX);
        z = y >> i;
        Serial.print(", y >> i "); Serial.print(z, HEX);
     
        Serial.println("");
      }
      
      while ( 1 ) {}
      delay(1000);
    }
            
     
     


Signed ints: code/Bits/Shifts02/Shifts02.ino

    #include <string.h>
    void setup()
    {
      Serial.begin( 9600 );
    }
     
    /*
      Examples of shifting interacting with signed ints
    */
     
    void loop()
    {
      int16_t x;
      int16_t y;
      uint16_t z;
      
      x = 0x00;
      Serial.println(x, HEX);
      y = ~x;
      Serial.println(y, HEX);
      
      for (int i=0; i <= 16; i++ ) {
        Serial.print("i ");  Serial.print(i);
        z = y << i;
        Serial.print(", y << i "); Serial.print(z, HEX);
        z = y >> i;
        Serial.print(", y >> i "); Serial.print(z, HEX);
     
        Serial.println("");
      }
      
      while ( 1 ) {}
      delay(1000);
    }
            
     
     


5.5 Bit Manipulation

A bit mask is a pattern of bits that is designed to identify certain bits in an bit string.

If you want to test the value of a bit in a particular position, set that bit to one and make the rest 0 (say by doing a shift left of a 1). Then an & operation will keep only the bit you wish to test. The result will be 0 (logical false) if that bit was indeed a 0, and non-0 (logical true) if that bit was a 1.
int x = 3476;
if ( X & 0x0002 ) {
     // the second bit from the right is a 1
}
else {
     // the second bit from the right is a 0
}
You can set to 1, clear to 0, or flip any bit in a word by using a mask and assignment statement.
X = X | 0x0004; // set the 3rd bit from the right to a 1
X = X & ~0x0004; // set the 3rd bit from the right to a 0
X = X ^ 0x0004; // flip the 3rd bit from the right.
5. Logical Operations on Bits
Tangible Computing / Version 3.20 2013-03-25