Bit Twiddling

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:

Bit1
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?

Bit2
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:

Bit3
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.



About the Author

Peter Shaw

As an early adopter of IT back in the late 1970s to early 1980s, I started out with a humble little 1KB Sinclair ZX81 home computer. Within a very short space of time, this small 1KB machine became a 16KB Tandy TRS-80, followed by an Acorn Electron and, eventually, after going through many other different machines, a 4MB, ARM-powered Acorn A5000. After leaving school and getting involved with DOS-based PCs, I went on to train in many different disciplines in the computer networking and communications industries. After returning to university in the mid-1990s and gaining a Bachelor of Science in Computing for Industry, I now run my own consulting business in the northeast of England called Digital Solutions Computer Software, Ltd. I advise clients at both a hardware and software level in many different IT disciplines, covering a wide range of domain-specific knowledge—from mobile communications and networks right through to geographic information systems and banking and finance.

Related Articles

Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date