In previous posts I talked about what a bit is, how you can use it to represent information, and how you can extend the information quantity by combining bits. I also noted how many bits fits in a byte. In this other post, I mentioned what a shift is and how you can use it to set bit flags on micro's registers. I realized that I needed a concept before introducing to shift to unset bit flags, but the truth is that I wanted that way. So, If you think you missed the logic part of the whole thing, then reading what it follows maybe will be useful to you.

You are familiar with operations with numbers. You substract or add numbers by using an operation. Those numbers you use are called operands and the symbol used is called operator. So, if you add 2 and 3 and you write in our math notation (a.k.a. you are not E.T.) it's supposed to be:

 2 + 3 = 6 

There we have + as operator and number 2 and 3 as operands, and 6 being the result. The whole thing is an operation, and it's called addition. Although I didn't mentioned, operands can be an element of any kind of sets numbers: real, integer, natural, etc, and the result will depend upon that. I mean, when you add the integer 2 with a real number not integer, the result will be a real number. Well, this things do not happen with bits operations. Operands are bits and the result is another bit. Again, C bits operations are defined between bytes, so, you don't actually use a bit in those operations. But before talking about language specifics, let's present the most common bits operations.

OR.

Calculate this kind of operations it's easier than you think. All what you need is a table. This table indicates the truth values for each possible operand. You may think that it could be a lot of them, but there are only four (if you work with more than bit, the number increases! dig up yourself why). That's all you need to do the math.

I say: truth table. Ok, we must assume an empty-full theory, that is, none or all. Discrete values, just those two. To be this useful, we talk about true things, and false things. (Note: I can't go far away with this, I can't teach logic here, so at least you have the tips to search by yourself if you want to know the whole story of this, and more formally of course). We can say that 0 (none) represents false, and 1 (all) represents true. Then, if we need to say something about an expression involving this things, we are gonna say that the whole thing it is false or true, but not the two things together. This is the truth table - that indicates if the expression is true or false - for the OR operation:

a. 0 or 0 = 0
b. 0 or 1 = 1
c. 1 or 1 = 1
d. 1 or 1 = 1

That's it. That's the only thing you need to know to calculate OR expressions, but remember it's always useful to know the theory about things. The above table makes sense indeed. In a), If I tell you that I have two propositions that are false then, no matter which one you choose, both of them are false. So, what I'm saying it's all false. Then, in b) c) and d), if there are two propositions and one of them it's true, then no matter what value the other has. The result will be true. It's like saying: "What I'm telling you it's true, or not". Although, that kind of expressions that are always true without knowing the truth-value of the propositions has a particular name, you can see by yourself that no matter what else you say in an OR expression if you already said a truth (you know the truth-value this time).

Now, how does C makes use of it? The (boolean) OR operator is '|' and both operands goes to each side. If you need to print a home-made truth table you can simply state:

printf("0  or  0 =  %d\n",0 | 0);
printf("0  or  1 =  %d\n",0 | 1);
printf("1  or  0 =  %d\n",1 | 0);
printf("1  or  1 =  %d\n",1 | 1);

It's important to note that as we are using a language, the implementations are as the language specifications states. C standards are that 0 means false and !=0 means true. If you test this out you'll find out that an if condition "4" or "-9" matches true, and the if code will be executed as the example shows you:

/* If block not executed */
if (0)
{
     printf("0 or 0 = %d\n",0|0);
     printf("0 or 1 = %d\n",0|1);
     printf("1 or 0 = %d\n",1|0);
     printf("1 or 1 = %d\n",1|1);
}
/* If block executed */
if (4)
{
     printf("0 or 0 = %d\n",0|0);
     printf("0 or 1 = %d\n",0|1);
     printf("1 or 0 = %d\n",1|0);
     printf("1 or 1 = %d\n",1|1);
}
/* If block executed */
if (-9)
{
     printf("0 or 0 = %d\n",0|0);
     printf("0 or 1 = %d\n",0|1);
     printf("1 or 0 = %d\n",1|0);
     printf("1 or 1 = %d\n",1|1);
}

You may be thinking that I lie when I said that C uses bytes not bits. If you watch the code it's possible you think that the 0 and the 1 are the bits showed in the truth table above. Well, not actually. Zero integer is represented as 0000 0000 (not actually. Number representation depends on architecture. So, if an integer is represented by 4 bytes, you need to add three 0 bytes of what I've said. But, just to be independet of architecture, we'll think an integer as a value between 0 - 255 or -128 to 127.) and 1 as 0000 0001.

If you see then, you'll realized that the '|' operator is applying the OR operation to each correspondent bit, as follows:

0000 0000
^^^^ ^^^^  OR
0000 0001
---------
0000 0001 Result

And that's how C uses '|' operator. Go and make test by yourself, I used only a byte for the example but you can test this out. It's not casual that I used a byte to show you the example, the thing is that most registers are of 8bits or 16bits size long, so it'll came useful to you what you are doing when you use the OR operation. Test what happens when you use negatives values, float values, etc. And remember, the answer is a few lines above.

AND.

Well, as you may guess AND also has a truth table. And I present it now:

a. 0 and 0 = 0
b. 0 and 1 = 0
c. 1 and 1 = 0
d. 1 and 1 = 1

Two common things you may find here. The commutative property and again, the presence of an especial element. This time, not matter what truth you say if it's followed by a falseness. This especial elements - 0 for the AND and 1 for the OR - are called absorbent elements. This is because no matter what you state after one of them (in the corresponding operation), the results will always yield with the named elements. The 0 has this property for multiplication for example. Again, you can make a truth table with the AND operation with C statements. C use the '&' operator. So, 0 & 0 will be 0.

printf("0 or 0 = ‰d\n",0&0);
printf("0 or 1 = ‰d\n",0&1);
printf("1 or 0 = ‰d\n",1&0);
printf("1 or 1 = ‰d\n",1&1);

Remember that C will do the AND or OR operation bit by bit.

NEGATION (a.k.a. NOT)

This is the one's complement. Put it this way, if you are in a bi-state world, what would it be the complement of a known state? The simple answer is, the state what's left. So if our set is formed by only two numbers - say {0 , 1} - then the complement (noted in paragraph as '¬') ¬1 will be 0. That's a bit complement.

But, what happens when we have a byte and we make the one's complement? Imagine we are using C (remember that C operands are bytes) and we do:

return ~1;

First, we may know how numbers are represented. If 0000 0001 is the binary representation for that 1, then ~1 should be 1111 1110. I wrote a little program that shows you how a byte is composed. Yes! at level bit! cool, huh?

#include <stdio.h>
#include <tmath.h>

int main(){
  int i = 0;
  unsigned int a = ~1;
  unsigned int aux = 0;

  for (i = 0; i < 8; i++)
  {
     aux = a & (unsigned int) pow(2,i);
     printf("%d th bit: %d\n",i,aux>>i );
  }
}

You can compile it using gcc and don't forget to add the -lm.

Example:

$ gcc ex1.c -lm

In each step, line 11 is masking a value. First, is masking a value to leave only the first bit value. Then, the second and so on...Imagine this:

/* First pass */
0000 000[] = 'a' value & 0000 0001
/* Second pass */
0000 00[]0 = 'a' value & 0000 0010
/* Third pass */
0000 0[]00 = 'a' value & 0000 0100
/* Fourth pass */
0000 []000 = 'a' value & 0000 1000
...

Where [] is the not-known value of a at the ith bit. If you are wondering why pow(2,i), maybe you shoul re-read previous articles. A one and only one in one of the 8 positions of a byte represents a number that belongs to this set: {128, 64, 32, 16, 8, 4, 2, 1}. And, a way to automatically apply this mask is by using the power of two up to 7. Feel free to do the math. So, line 11 does that. Masks the value of a doing and AND operation as we saw earlier. Example: imagine 'a' is 1001 1100 and the mask is 0010 1000. Doing the operation we have:

1001 1100 'a' 
^^^^ ^^^^  AND
0010 1000  mask
---------
0000 1000 Result

/* First pass */
0000 000[] = a value & 0000 0001 
0000 000[] == 0000 000[] >> 0
/* Second pass */
0000 00*0 = a value & 0000 0010 
0000 000* == 0000 00*0 >> 1
/* Third pass */
0000 0*00 = a value & 0000 0100
0000 000* == 0000 0*00 >> 2
/* Fourth pass */
0000 *000 = a value & 0000 1000
0000 000* == 0000 *000 >> 3
...

And finally, the unsigned int is just there because we are using a byte.

Now...you get the importance here of the neutral element? We used the 1 for that, if there was a 1 then 1 is the result, if there was a 0 then 0 is the result. Go check out the truth table. We'll use the absorbent element in a few lines below. Wan't to improve it a little more? Actually, we can remove the math.h routines as we are only moving a bit through a byte.....Does this sounds usual to you? Yes, we're shifting a 1 one position at a time. This is equivalent but we get rid off math.h routines.

#include <stdio.h> 

int main()
{
    int i = 0;
    unsigned int a = ~1;
    unsigned int aux=0;
    for (i = 0; i < 8; i++)
    {
        printf("%d th bit: %d\n",i,aux>>i );
        aux = a & 1< i );
    }
}

Or even less:

#include <stdio.h>

int main()
{
    int i = 0;
    unsigned int a = ~1;
    for (i = 0; i < 8; i++)
    {
        printf("%d th bit: %d\n",i,(a & 1<<i)>>i );
    }
}

Ok, if you run this example you'll find out that the resulting number is 1111 1110 but, why C is showing -2? You get what I asked? If you print the binary you'll get 254:

printf("binary: %d\n",0b11111110);

This is related with what I told you before on other post about numbers representations and with the C printf format function. When the sign bit it's set, 1111 1110 depending on the representation used it's -2. You can imagine that 0000 0010 is 2, and when you use a specific representation then 1111 1110 is -2. I won't dig up in this, but please dig by yourself. For now on, you can test the different outputs with this code:

#include <stdio.h>

int main()
{
    int i = 0;
    unsigned int a = ~1;
    for (i = 0; i < 8; i++)
    {
        printf("%d th bit: %d\n",i,(a & 1<<i)>>i );
    }
    printf("Integer a: %d\n",a);
}

and this code:

#include 

int main()
{
    int i = 0;
    unsigned int a = ~1;
    for (i = 0; i < 8; i++)
    {
        printf("%d th bit: %d\n",i,(a & 1<<i)>>i );
    }
    printf("Unsigned char (our common representation): ‰hhu\n",a);
}

If you want to learn more about how printf() function works, then this is the place.

Putting this together.

Now, with the above stated I hope you don't think that ~1 is false, at least in C. Remember that C uses 0 as false and any other number as true value. Then, using ~1 as an if condition won't yield false never. A trick in micro's world to test if a bit flag is set in a register is then as follows:

if ( my_register & (1 << the_bit_i_want_to_check) )
{
/* your code here */
}

What that does is this:

1. Set a 1 in the requested position. You'll have plenty of 0s and only one 1.

2. Do an AND operation with the register. 0s will absorb the bit flags you don't care on the register, and the 1 will neutralize the value that is currently on the bit you want. Then, if it was a 0 there, the whole expression will be 0 and matches false (remember, C-related). If it was a 1, the whole expression will be a non-zero matching true.

Of course that if you have a complex operation to made, you can mix ANDs, ORs and NOTs as you like and keep in mind to respect the precedence of each other. It's not a syntax warning, though you may have not expected results. Same applies to common arithmetic operations such as addition and multiplication for example. When there's no need to use parenthesis you can avoid them, but remember that it's not the same this:

return ( 1 + 63 * 8); //parenthesis not needed here

than this:

return ( (1 + 63) * 8);   //parenthesis needed

Conclusion.

I always mention that this kind of articles are more introductories than other thing. May I say that there's same kind of analogy that we aren't going to study, that relations addition with OR operation, and multiplication with AND operation. You can dig up about that. At this time you should be able to use and, or, not and shift operations to investigate yourself. Also you should be able to set a bit flag in an 8bit register if you read this article. And recently, you should be able to ask for a specific bit in a register too. To unset a bit flag we need the concepts from this post. More implicated are and and not operations, so when I have time I'll write about how to unset bit flags.