Yes I know, it’s a strange title, but bear with me, you’ll soon see why.
Every so often, you see things that seem to confuse all developers, regardless of time in the industry, or level of skill. The process of performing Boolean operations, unfortunately, seems to be one of these things.
I’m writing this post with the .NET developer in mind, and any code presented will be in C#, but the concepts I’m about to discuss are applicable to any programming language.
So, What Do We Mean by Bit Twiddling?
Well, to clarify that, we first need to take a trip back to Computer Science 101. For many younger developers who’ve been schooled using a language-based approach, this might actually be something new to them. To those who’ve done a dedicated CS or electronics course, this will probably just serve as a bit of a refresher.
The chips in your computer communicate using a series of electronic pulses; these pulses travel along “Busses” in groups. The sizes of these groups are what determine the “Bit Size” of your PC.
A 32-bit machine will group these busses into groups of 32 individual wires, each carrying one set of pulses. Likewise, a 64-bit machine will make groups of 64 wires.
I’m not going to deep dive into this subject because that would take a whole book. Instead, we’res interested only in the behaviour of one wire at a time.
Why?
Well, because the behaviour of one wire is perfectly modelled in computer software, when you start looking at performing Boolean operations on your data.
The wires in your PC can either have an electric current in them, or not. This typically manifests itself as +5 volts or 0 volts. When looking at the same thing from a software point of view, we can easily say that +5 volts is equal to “True” and 0 volts is equal to “False.”
Once you start to understand this, you begin to understand how numbers are represented by your PC. Take the following example:
128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | Decimal |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 128 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 255 |
Table 1: 8 Bit binary values
In Table 1, I listed the first 8 wires, or as it’s more commonly known, a “Byte.” Each wire from the right going towards the left is given a power of 2 (because it can only be in one of two states: 1 or 0), and each power of 2 as you go left is multiplied twice by itself.
In the first row, the “1” indicates that wire 1 has +5 volts in it, while the “0”s in the other wires give 0 volts. This is how the computer represents a value of “1” as electrical signals, to mean a data value of “1” in your program.
In the second number, we have “128” because only the wire with value “128” has +5 volts in it.
The 3rd number is 255, because if you add up all the numbers 1 through to 128, you get 255, and all the wires for that number have +5 volts in them.
If you wanted to represent a value of “24,” you’d put +5 volts into wires “16” and “4.”
When you look at these values in your program code, if you convert them to binary notation, you’ll see exactly the same thing, with 0s and 1s in the appropriate columns.
Bigger numbers are represented by adding more wires. In Table 1, we could add a 9th column equal to 256 (128 * 2) and that would give us a 9-bit number, whose maximum value would be “512.”
All This Is Interesting Stuff, but if C# Takes Care of All This for Me, Why Do I Need to Care?
You need to care because this is how your if/then statements work, and how your transparent graphics merge pixels without destroying other graphics.
The very fundamentals of how a computer makes its decisions revolve around seven very basic logic operations:
- And
- Nand
- Or
- Nor
- Xor
- Nxor
- Not (Inverse)
These basic logic rules govern pretty much everything your PC does, and are the absolute fundamentals of how the CPU in your PC decides what to do based on what numerical instructions it’s given.
It also happens that knowing this stuff has a load of uses in software, too.
The rules are simple to interpret, and each one has a defined set of inputs that give exactly one output. The following tables are the Truth Tables used to describe these rules:
AND
Input A | Input B | Output |
0 | 0 | 0 |
1 | 0 | 0 |
0 | 1 | 0 |
1 | 1 | 1 |
The rule for an AND states that the output is “1” only when all of its inputs are “1.”
NAND
Input A | Input B | Output |
0 | 0 | 1 |
1 | 0 | 0 |
0 | 1 | 0 |
1 | 1 | 0 |
The rule for a NAND states that the output is “1” only when all of its inputs are not equal to “1.”
OR
Input A | Input B | Output |
0 | 0 | 0 |
1 | 0 | 1 |
0 | 1 | 1 |
1 | 1 | 1 |
The rule for an OR states that the output is “1” only when one or more of its inputs are “1.”
NOR
Input A | Input B | Output |
0 | 0 | 1 |
1 | 0 | 1 |
0 | 1 | 1 |
1 | 1 | 0 |
The rule for a NOR states that the output is “1” only when one or more of its inputs are not “1.”
XOR
Input A | Input B | Output |
0 | 0 | 0 |
1 | 0 | 1 |
0 | 1 | 1 |
1 | 1 | 0 |
The rule for an XOR states that the output is “1” only when all of its inputs are different to each other.
NXOR
Input A | Input B | Output |
0 | 0 | 1 |
1 | 0 | 0 |
0 | 1 | 0 |
1 | 1 | 1 |
The rule for a NXOR states that the output is “1” only when all of its inputs are not different to each other.
NOT (Inverter)
Input | Output |
0 | 1 |
1 | 0 |
The rule for a NOT states that the output is to be the opposite of the input.
Enough Theory. Let’s See Some Code.
Create a simple console program in Visual Studio, and make sure program.cs has the following code in it:
using System; namespace bit_twiddling { class Program { static void Main() { int num1 = 1; int num2 = 2; int result = num1 & num2; Console.WriteLine("AND"); Console.WriteLine("Input A = {0} [{1}]", num1, Convert.ToString(num1, 2)); Console.WriteLine("Input B = {0} [{1}]", num2, Convert.ToString(num2, 2)); Console.WriteLine("Result = {0} [{1}]", result, Convert.ToString(result, 2)); } } }
If you press F5 and run this, you should see the following:
Figure 1: Output from our program ANDing two numbers
The Binary representation of “1” is “00000001” and the binary representation of “2” is “00000010.” If you AND them as per the previous logic rules, you get the following:
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 2 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Looking at the two columns with a 0 in and referring to the truth table:
1 AND 0 = 0
0 AND 1 = 0
So, our result gives us a 0.
Let’s now change the code slightly and make num2 equal to 3
int num2 = 3;
Then run our program again. What do we see this time?
Figure 2: Output from AND operation with the second number changed to 3
You can see from Figure 2 that our result is now equal to input A, and what we’ve effectively done is used the input in num1 to turn off any bits in num2 that we don’t care about.
This comes in handy, for example, when we only want part of a number.
Let’s alter our code once more, and this time try an OR operation.
Change your code in program.cs so it looks like the following:
using System; namespace bit_twiddling { class Program { static void Main() { int num1 = 1; int num2 = 2; int result = num1 | num2; Console.WriteLine("OR"); Console.WriteLine("Input A = {0} [{1}]", num1, Convert.ToString(num1, 2)); Console.WriteLine("Input B = {0} [{1}]", num2, Convert.ToString(num2, 2)); Console.WriteLine("Result = {0} [{1}]", result, Convert.ToString(result, 2)); } } }
Now, try running it and you should see the following:
Figure 3: Result of the OR operation
This time you can clearly see that the opposite of the AND operation has happened, and you’ve set the 1st bit in your result using the input in num1.
Using an OR operation effectively sets parts of a number without changing parts already present.
An OR operation is often used in computer graphics when merging two images together, and ensures that existing information is preserved.
In .NET, the operators you use for these operations are as follows:
- & = AND
- | = OR
- ^ = XOR
- ! = NOT
To get NAND/NOR and NXOR, simply prefix the output with a NOT; for example:
int result = !(num1 | num2);
This will give you the same result as a NOR; whereas
int result = !(num1 & num2);
will equal the output of a NAND.
I’ll leave the XOR and NXOR operations as an exercise for the reader to play with.
Got a tricky .NET problem you can’t solve, or simply just want to know if there’s an API for that? Hunt me down on Twitter as @shawty_ds or come and visit the Lidnug (Linked .NET) user group on the Linked-In platform that I help run, and let me hear your thoughts. It may even make it into a post in this column.