GLProgramming.com

home :: about :: development guides :: irc :: forums :: search :: paste :: links :: contribute :: code dump

-> Click here to learn how to get live help <-



 
 

Development Guide Library


Logic and Bitwise operations by baldurk

Introduction

This will probably end up being a relatively short DG, but I think a lot of people could benefit from a brush up, or learning more about, logic and bitwise operations. Although the sample code is in C++, it is simply there to demonstrate the concepts, and not actual code. Therefore even if your language of choice is not C/C++, you should still be able to benefit from this DG.

What topics are going to be covered?

I'm going to cover logic, meaning logical AND, OR, NOT and XOR. I'll also cover the topic that is perhaps more specific to C/C++; short-circuiting. More on that when we get to it.

Under bitwise operations, essentially I will cover the same. Meaning bitwise AND, NOT, OR and XOR. I'll also cover bitshifts.

Logic operations

First we'll look at logic operations in general. These operations only apply to (one, but mostly) two bits. You can see this best in a table. With 2 bits, you can have 4 possible combinations for the bits, assuming order matters: 0 and 0, 0 and 1, 1 and 0, 1 and 1. This is the accepted order to list the operations, as it is the order of the binary numbers 0 to 3: 00, 01, 10, 11.

For each operation I will show you a table for the inputs and the output. First up, logical AND.

Also, in C++ and most other languages, 0 is the value for false, and all other numbers evaluate to true. This is important, because if you rely on 1 being true and everything else being false, you introduce bugs. Remember that -1 is true as well.

Logical AND

<table><tr><td>

Input 1

</td><td>

Input 2

</td><td>

Output

</td></tr> <tr><td>0</td><td>0</td><td>0</td></tr> <tr><td>0</td><td>1</td><td>0</td></tr> <tr><td>1</td><td>0</td><td>0</td></tr> <tr><td>1</td><td>1</td><td>1</td></tr> </table>

From this it is easy to see that AND only outputs a 1 if the inputs are 1 AND 1. The operations are named so that you can easily remember what they do. AND is useful for logic conditions where you want to make sure that several conditions are met. e.g:


// determine if the computer can boot up and can be used
if( power_being_supplied && keyboard_connected && monitor_connected)
{
    start_computer();
}


Now, obviously that example is silly, but you get the point. You can see that the C++ operator for logical AND is &&. Note that there are two &s. One & is bitwise AND, which is something different entirely. This is the same in a lot of languages.

In this example, the if would fail and start_computer would not be called if any of the conditions were false. Even if the keyboard and the monitor are connect, if there's no power the if will fail.

If you are confused by what seems to be 3 inputs, then look at it as two ANDs.

One AND has the inputs power_being_supplied and keyboard_connected. If either of those is 0, the output of this "sub-AND" will be 0.
Then the second AND is the result of the previous and monitor_connected. So if the first AND fails, because power_being_supplied is false, or keyboard_connected is false, the second AND can never pass.

Here's a clearer example, with brackets, to show what I mean.


// determine if the computer can boot up and can be used
if(   (power_being_supplied && keyboard_connected)
                            &&
                     monitor_connected
  )
{
    start_computer();
}


If you don't understand, try looking back at my explanation again. Try to think of it as two ANDs combined, rather than one big AND.
If you do understand, that's good, as the same principle applies for all these operations.

Logical OR

<table><tr><td>

Input 1

</td><td>

Input 2

</td><td>

Output

</td></tr> <tr><td>0</td><td>0</td><td>0</td></tr> <tr><td>0</td><td>1</td><td>1</td></tr> <tr><td>1</td><td>0</td><td>1</td></tr> <tr><td>1</td><td>1</td><td>1</td></tr> </table>

As you can see, OR outputs 1 most of the time. It only outputs a 0 when both the inputs are 0. This means it outputs a 1 when input one is 1 OR input two is 1. Again, simple enough to remember.

The application of this in logical conditions means that the overall condition will pass if any of the sub-conditions are true. For example:


// determine if we can drive to work
if( own_a_motor_bike || own_a_car || own_a_hovercraft )
{
    drive_to_work();
}


If you have a motor_bike, or a car, or a hovercraft then you can drive to work. If you have more than one, you can still drive to work. But if you have none, you can't drive to work.

Also note the C++ operator (and in a lot of languages) for logical NOT is ||.

Logical NOT

<table><tr><td>

Input 1

</td><td>

Output

</td></tr> <tr><td>0</td><td>1</td></tr> <tr><td>1</td><td>0</td></tr> </table>

NOT is the simplest of the logical operations. It simply returns the inverse of whatever the input. 1 for 0 and 0 for 1. So if input 1 is a 0, the output is NOT 0 so it has to be a 1.

In logical conditions, this can be very very useful. Here's a more programming-related example:


// if pointer p is valid (ie. not NULL). If not, print an error message
if( !p )
{
    printf("assert, p == NULLn");
    return 1;
}


for those of you reading who don't quite understand that example for whatever reason, let me explain. p is a pointer to some data. It's basically a number, and that number is the address of a piece of data in memory that we want to write to. Now, if p isn't pointing at memory, then it points at NULL, or 0. In that case, we don't want to write it. If it is pointing at something, it will be some number.

If it's valid, then p will be some number, so !p will be 0. It's not exactly the same as 1 -> 0 and 0 -> 1. But it acts the same. The result is that !p is 0, so the if fails. If it's invalid, however, then !0 = 1, so the if is executed and the error message is displayed.

Logical XOR

<table><tr><td>

Input 1

</td><td>

Input 2

</td><td>

Output

</td></tr> <tr><td>0</td><td>0</td><td>0</td></tr> <tr><td>0</td><td>1</td><td>1</td></tr> <tr><td>1</td><td>0</td><td>1</td></tr> <tr><td>1</td><td>1</td><td>0</td></tr> </table>

Logical XOR is an interesting operation in a few ways. First, it's logic table as you can see is slightly different, although that's not much to go on. XOR has a name which once you know it makes sense, but it isn't immediately obvious what it does. XOR is short for eXclusive OR. This means it's like an OR, but it eXcludes the 1, 1 option for the inputs. I find it easiest to remember it as only being 1 if the inputs are different: 0, 1 and 1, 0.

Also, XOR is the only operation I will discuss here that doesn't have a direct C++ operator. It is easy to simulate with the three we have already discussed though. Like so:


inline int xor(int input_1, int input_2)
{
    return (input_1 || input2) && !(input_1 && input_2);
}


This could use some explaining. If input 1 and input 2 are 0, then the first bracket will fail. In all other circumstances (0, 1; 1, 0 and 1, 1) it will pass. The second bracket will only fail if both inputs are 1. Inside the bracket is a simple AND which will only pass if they are 1, 1. We then NOT that, so that it only fails if they are 1, 1. As a sidenote, here you can see an important use of the NOT, which is to reverse the logic of any condition. The overall result is a XOR gate.

Short-circuiting

Short-circuiting is something that many programmers use and occaisonally rely on. This is the very simple principle that as soon as you can determine that a condition is true or false, then you move on. Let's look back at our "driving to work" example.


// determine if we can drive to work
if( own_a_motor_bike || own_a_car || own_a_hovercraft )
{
    drive_to_work();
}


Let's say, for the example, that own_a_motor_bike is true. The important thing to note about this is that if own_a_motor_bike is true, then it doesn't matter what the other two are, the whole expression will still be true. This is an example of short-circuiting. As soon as you can determine the value of the overall condition, you use it. This means that own_a_car is never checked, if own_a_motor_bike is true.

This can be very useful in circumstances like this:


// we want to check if the memory location p is pointing at is 5
if( p && *p == 5)
{
    // do something here
}


Now, if p is a valid pointer, then the first part will be true. We can then check the value that p is pointing at without worrying about reading invalid memory (not entirely true, but for the sake of this DG it is). However, if p is NULL, then we know that the whole expression is going to be false, no matter if *p is 5 or not. This means we don't check *p, and so we avoid an exception for accessing invalid memory.

Bitwise operations

I'm not putting in tables for the bitwise functions, because they are the same. bitwise simply means that we apply it differently. Whereas 01101011 (logical AND) 00101100 is 11111111 (not exactly, but effectively it is). 01101011 (bitwise AND) 00101100 is 00101000. You can perhaps already see the main difference. Whereas logical operations treat the numbers as either true (not 0) or false (0) then work with them as if they are just single bits, bitwise operations take pairs of bits, and operate on them. So all the bits are treated as bits, and the number as a whole is ignored. This is the main, important, distinction.

For this reason I won't focus on each of the operations as much as I did above, simply provide examples. Note that for AND and OR the C++ operators are simply half the logical operators: && -> & and || -> |. For NOT the operator is ~ and for XOR the operator us ^.


bitwise AND:
01011100 input 1
&
11010101 input 2
=
01010100 answer

bitwise OR:
01011100 input 1
|
11010101 input 2
=
11011101 answer

bitwise XOR:
01011100 input 1
^
11010101 input 2
=
10001001 answer

bitwise NOT:
~
01011100 input
=
10100011 answer


Bitshift left and Bitshift right

The last of the bitwise operators, which I will go into more depth with are the bitshift left and bitshift right operators. They perform the same operation, only in different directions. That will become clearer to you as I explain them. For clarity, I'll only explain bitshift left.

It's quite simple to understand. All bitshift left does is shift all the bits to the left by the number you pass. Obviously, this requires one more bit to be added onto the right. This is a 0, always. If one bit is added onto the right, that means that one bit is lost off the left. And that is exactly right - it is lost.

The bit is thrown away, and will not come back, even if you shift to the right. That just means you'll have a bit lost off the right. However, this isn't as bad as it seems, because if the bit was a 0, then you haven't really lost anything because when you bitshift right then a 0 is put in it's place. Here's an example:


0000000010100000
<< 3
0000010100000000
<< 5
1010000000000000
<< 1
0100000000000000
>> 1
0010000000000000


Applications of bitwise operators - flags

Although there are many applications for bitwise operators, I'll show you a couple. First, flags.

I'll start with the example, then explain it. If you want a challenge, try to figure it out before reading the explanation.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#define FLAG1 1 << 0
#define FLAG2 1 << 1
#define FLAG3 1 << 2
#define FLAG4 1 << 3
#define FLAG5 1 << 4

// the flags are now like so:
000001  FLAG1
000010  FLAG2
000100  FLAG3
001000  FLAG4
010000  FLAG5

int data = FLAG2 | FLAG4 | FLAG5;

if(data & FLAG3)
{
    printf("flag 3n");
}
if(data & FLAG4)
{
    printf("flag 4n");
}


To start with, line 14, where we set data. Notice that the FLAGs only have 1 bit each, and each flag has a bit in a different column. This means that when we OR them together, each bit that has a 1 in data is because of a specific FLAG. if bit 2 (from the right) is a 1 in data, we can be absolutely sure that it is because we ORd in FLAG2, not FLAG4 or FLAG5.

Now, if each bit is because of a specific FLAG, then we can simply say "OK, bit 3 is on, so FLAG3 has been ORd. Let's take appropriate action". Now, how do you figure out if bit 3 is on? all you can do is say that data (in this case) is the decimal number 26. Bitwise AND to the rescue!

If we AND against the flag we want to check, because everything is 0 except the bit that we want to check, the result will only be 1 if the bit is enabled on the data. If the bit is 0 on the data, then the result of the bitwise AND will be 0, so if we put that in an if statement, it only passes if the bit is enabled on the data. Like this:


011010 data
&
000100 flag3
=
000000 zero, so the if will fail

011010 data
&
000010 flag2
=
000010


You can see in the second example that not only will the result be a positive number, therefore evaluate to true but it actually evaluates to the flag you're checking against.

Applications of bitwise operators - encryption

OK, so perhaps calling it encryption is exaggerating, but the principle is the same. This example only uses XOR, but shows you a very neat usage of it which uses a property of XOR - it reverses itself.

Let me show you again by example.


1
2
3
4
5
6
7
8
9
10
11
12
 
int data = 1389;
int key = 5202;

printf("data is %dn", data);

data = key ^ data; // encrypt the data

printf("data is %dn", data);

data = key ^ data; // decrypt the data

printf("data is %dn", data);


the output of this will be:

data is 1389
data is 4415
data is 1389


So you see, the XOR operation when used with the same key, encrypts the first time, then decrypts the second time.

The first step in understanding the code is to convert everything to binary:

0010101101101 is the data
1010001010010 is the key

when we XOR them together, we get


0010101101101 data
^
1010001010010 key
=
1000100111111 result


Now, let's work the magic by XORing the result with the key


1000100111111 result
^
1010001010010 key
=
0010101101101 data


Pretty simple to see. If you work through with some simply examples, you can prove easily enough that the operation reverses itself. However, don't rely on this for anything important!

Conclusion

I hope that not just new programmers learned something from this DG. If you have any questions, please feel free to email me.

- baldurk