Bitwise Operators

Did you know that 2 AND 2 is not equal to 4? Well, it's not – open up Windows Calculator, click [2] [and] [2] [=], and you will see that the result is 2. But how does this work? This seems to make no sense. Haven't we all heard the expression "put 2 and 2 together"?

The simple answer here is that AND is a bitwise operator – an operator that works on the individual bits (binary digits) of a number. Bitwise operators are extremely useful in the world of computers. A computer's CPU (processor) works with binary numbers, and as you will learn in this article, these so-called bitwise operators are the fundamental arithmetic operations that a CPU performs.

Logical operators

You use logical operators every day. Take, for example, an everyday situation like ordering pizza. You can opt for a pizza with ham and pepperoni on it, meaning that you would like both items on the pizza. Alternately, you can opt for ham or pepperoni.

Logical operators are comparison operators – that is, you use them to compare things. In real life, you can think "if the pizza has ham and pepperoni on it, I will eat it". In pseudocode, this would be

if (pizza.toppings.ham == true) and (pizza.toppings.pepperoni == true)
pizza.eat()
end if

Logical AND

The first operator we will briefly discuss is the AND operator. Logical AND is represented in different programming languages differently; the most common representations are AND and &&. AND evaluates to true if both expressions are true, otherwise it evaluates to false, as can be seen in the below truth table. Here, 0 represents false and 1 represents true.

Note that the order of the operands does not matter. 1 AND 0 is identical in meaning to 0 AND 1, much like the fact that saying "My pizza has ham and pepperoni on it" is the same as saying "My pizza has pepperoni and ham on it."

Logical OR

The OR operator introduces an issue, namely the issue of exclusiveness. In the case of "you can have cake OR a cookie", it's possible to take both, because the two things are not mutually exclusive. However, in the case of "the light is on OR it is off", OR is exclusive; it's not possible for the light to be on and off simultaneously.

The OR operator is defined to be inclusive, like in the first example. Thus, if you say that you want your pizza to have ham OR pepperoni on it, valid possibilities would be: pepperoni with no ham, ham with no pepperoni, ham and pepperoni. Logical OR is often represented as OR and ||.

Logical XOR

The XOR operator (exclusive OR) is like the OR operator, but it is only true when one of the conditions (not both) is true. It is represented by XOR and ^ in common programming languages. (Note that the ^ symbol is used by some languages such as VB to represent powers; this is a completely unrelated operation.)

Logical NOT

The NOT operator simply reverses the truth of an expression. NOT 1 is equal to 0, and NOT 0 is equal to 1, assuming that 1 means true and 0 means false. It is represented as NOT and ! in code.

Binary numbers

Computers use the binary number system. The term "binary" simply means "two", and the binary number system uses base 2 (as opposed to the conventional base-10 system we use in daily life). The decimal (base 10) number "5" is represented in binary as "101" and the decimal number "2" is represented in binary as "10".

Binary is quite simple – in fact, if it weren't for the fact that we used the decimal system, we would consider binary to be much simpler. Binary numbers have only 2 possible values per place value – 0 and 1 – so you don't need to worry about what to do with different "on" states in each place value.

If you think back to first grade, you will remember the concept of place values. In the decimal system, there is the 1's place, 10's place, 100's place, and so on. Notice a pattern here: each place value is a power of 10. The 1's place is 10^0 (here ^ is used to signify arithmetic powers, not XOR), the 10's place is 10^1, the 100's place is 10^2. Now apply this knowledge to binary, but use powers of 2. You then have the 1's place, 2's place, 4's place, 8's place, and so on.

To convert a number from binary to decimal, start from one side and multiply the bit (binary digit) by its place value. For this example, we will start from the left. Take the number 1110. The place values from left to right are 8, 4, 2, 1. Go through each bit and if it's a one, add the place value; if it's a 0, don't add anything. Mathematically, this will be 1*8 + 1*4 + 1*2 + 0*2 = 14.

Putting 2 and 2 together: Bitwise operations

As you saw above, a binary number is simply a sequence of 0's and 1's – a sequence of "true" and "false" bits. Now, to demystify bitwise operators once and for all: a bitwise operation is simply a logical operation performed on every bit in 2 binary numbers. That's all there is to it.

Bitwise AND, OR, XOR

Now that you know how binary numbers work and how logical operators work, you can use bitwise operators. A bitwise AND operation on 2 numbers is known as "and-ing" and a bitwise OR operation is known as "or-ing" (here, "and" and "or" are used as verbs). You need to follow similar rules to addition with these three operations: line up the numbers so that the 1's place is in the same location and pad the left side with zeros until both numbers have the same amount of digits.

Let's try the following operation: 10101101 AND 00110011. It's easier to see if we write them vertically:

    10101101
AND 00110011
------------

One "feature" of bitwise arithmetic is that you don't need to deal with carrying digits over; thus, it does not matter which direction you start evaluating from. Here, we will evaluate from the left. Start comparing the two leftmost digits: 1 and 0. Now, just evaluate these as explained in the "Logical Operators" section: 1 AND 0 = 0. Write a 0 beneath the two digits, and move on to the next pair: 0 AND 0 = 0. Again, write this down. The next pair is 1 AND 1 = 1. So far, you have:

    10101101
AND 00110011
------------
    001.....

If you continue all the way until the end, your result will be 00100001. It's not that hard, is it?

To perform OR and XOR operations, follow the exact same steps above, but substitute the appropriate operators.

   10101101
OR 00110011
-----------
   10111111

    10101101
XOR 00110011
------------
    10011110

Note that these operators can be chained together, as in 10101101 OR 00000111 OR 10010000, due to the fact that it's possible to do this with logical operators.

Bitwise NOT

Bitwise NOT is actually much simpler than bitwise AND, OR, and XOR: all you need to here is reverse each bit in a single number. NOT 10101101 becomes 01010010; to arrive at this answer, all you need to do is replace all 1's with 0's and all 0's with 1's.

Bit shift operators

We now need to introduce two new operators: the left shift operator, represented by LSH and <<, and the right shift operator, represented by RSH and >>. As can be inferred from their name, these operators shift the bits in a binary number by the specified amount.

The expression 00011000 << 2 simply means to shift each bit 2 places to the left, resulting in 01100000. Similarly, 10000000 >> 7 results in 00000010.

What if we're asked to shift bits in such a way that we don't have room to hold them? This can be the case if we're shifting to the right, or if we're shifting to the left with a limited amount of space (which is always the case in a computer). The answer is usually "the bits are dropped." However, in some cases, the bits pushed off of the left end wrap around to the right and vice versa.

Applications of bitwise operators

Now you may be thinking "this is cool, but what's the point of it?" Well, bitwise operators are used every day by your computer, whether you like it or not. Not only that, but a CPU thinks in ANDs, ORs, XORs, NOTs, and bit shifts. Thanks to this, one can use bitwise operators to do many cool things very quickly; three applications of bitwise operators are outlined here.

Flags and Bitmasks: Ordering Pizza

Perhaps the most common use of bitwise operators is in flags and bitmasks. The principle behind flags and bitmasks is that one can, through appropriate use of bitwise operators, manipulate each bit inside a given byte, effectively turning it into 8 separate boolean values (there are 8 bits in a byte). Each byte is basically an on/off switch. To "set" a bit means to change its value to 1 (or turn the "switch" on), and to "unset" a bit means to change its value to 0 (or turn the "switch" off).

You can define a variable for each bit as follows. Here, I will define possible flags for options used in ordering a pizza:

CHEESE = 1		//00000001
CHICKEN = 2		//00000010
PEPPERONI = 4		//00000100
HAM = 8			//00001000
SAUSAGE = 16		//00010000
OLIVES = 32		//00100000
ONIONS = 64		//01000000
STUFFED_CRUST = 128	//10000000

Notice that each flag is a power of two. That's because a power of two has only a single "1" amongst other 0's. This allows us to use bitwise operators to set just that one bit. Any numeric variable can be declared as the variable holding the flags; a byte will hold 8 flags, while a 32-bit integer will hold (you guessed it) 32 flags. Let's define a byte to hold flags for the pizza, called PizzaFlags.

Setting bits

To set a bit, we use the OR operator, like so:

PizzaFlags = PizzaFlags OR CHEESE OR PEPPERONI OR ONIONS

Using "OR" may seem counter-intuitive at first – doesn't "and" mean to put two things together? – but you must remember that it only works this way when comparing values. When setting values, the "opposite" is true, in the sense that writing is the "opposite" of reading. To test this out, perform the evaluation. You will notice that OR will set the bit specified in the flag as 1, and will leave the others alone.

   00000000 //Initial state
OR 00000001 //CHEESE bit
OR 00000100 //PEPPERONI bit
OR 01000000 //ONIONS bit
-----------
   01000101 //Final result

Unsetting bits

To unset a bit, you must combine two operators, AND and NOT. NOT will reverse the bits in the flag, and AND will unset the one 0 bit while leaving the others alone. Let's say that in the above example, we wanted to unset the ONIONS bit. We would write:

PizzaFlags = PizzaFlags AND NOT ONIONS

We will evaluate in two steps.

NOT 01000000 //ONIONS bit
------------
    10111111 //Inverse of ONIONS bit

    01000101 //Initial state
AND 10111111 //Inverse of ONIONS bit
------------
    00000101 //ONIONS bit unset

Toggling bits

What if you wanted to flip a bit back and forth each time, without having to check its state? That's where the XOR operator comes in handy. Although this has no practical value in the above pizza example, you can use XOR to flip the ONIONS bit back and forth.

    01000101 //Initial state
XOR 01000000 //ONIONS bit
------------
    00000101 //ONIONS bit toggled "off"

    00000101 //Initial state
XOR 01000000 //ONIONS bit
------------
    00000101 //ONIONS bit toggled "on"

Masking multiple bits: Colors

Now that we're comfortable working with single bits as on/off "switches", it's time to introduce a new concept: working with groups of bits. The only difference in implementation is that you would use masks containing more than one 1 bit. We will also make use of the bit shift operators. A very common use for this technique is for extracting and combining color channels.

How colors are stored

Many computers today use "24-bit" or "32-bit" color, but what exactly does this mean? Quite simply, it's the arrangement of bits in memory. Colors are stored as integers in memory, as it is possible to stuff 4 bytes (8 bits each) into a 32-bit integer; each color channel (red, green. blue, alpha) consumes 8 bits.

Most systems store 24-bit colors in either RGB or BGR format. Here is an example of a single pixel in BGR format, which is used by many Windows API functions:

00000000110000010101110111110001

Note that the first 8 bits are all zeroed out; they can be used for storing alpha (transparency) data in an ARGB image, but in many cases, these bits are just left empty. The reason for this is that a 32-bit CPU can process 32-bit integers much faster than nonstandard arrangements of 24 bits; thus it's actually faster to "waste" this space.

Masking color channels

What if you wanted to find the value of each individual channel, which is required for image processing? It's actually quite simple, thanks to bitwise operators. Using our knowledge of the layout of the color channels in memory, we can define masks that have 1's for the color channel values we want and 0's for the ones we don't.

RED_MASK =	00000000 00000000 00000000 11111111
GREEN_MASK =	00000000 00000000 11111111 00000000
BLUE_MASK =	00000000 11111111 00000000 00000000

The basics of hexadecimal numbers

When working with 32-bit integers, writing out the 0's and 1's can be quite tedious. That's why the octal (base 8) and hexadecimal (base 16) numbers exist – 8 and 16 are powers of 2, and thus each digit in an octal or hex number corresponds directly to several bits. For hexadecimal (which uses the digits 0-9 and then A-F), each digit is equivalent to 4 binary digits (because 2^4 = 16). Thus, our "huge" masks for red, green, and blue can be written in hex as:

RED_MASK =	0x000000FF
GREEN_MASK =	0x0000FF00
BLUE_MASK =	0x00FF0000

"0x" simply denotes that we're working with a hex number. Please note that we are working with BGR values, not RGB like HTML format colors use. If you're working with RGB values, simply reverse the values of RED_MASK and BLUE_MASK.

Extracting color channels

As before, we use the AND operator to mask out the bits we don't want. Let's try the green channel.

    00000000 11000001 01011101 11110001
AND 00000000 00000000 11111111 00000000
---------------------------------------
00000000 00000000 01011101 00000000

However, the value of 0101110100000000 is not the same as 01011101! We must perform an additional step; namely, shifting the bits over 8 places to the right:

00000000 00000000 01011101 00000000 >> 8
-----------------------------------
00000000 00000000 00000000 01011101

As we can visually see in the original color, the value of green is 01011101.

General Formula

The general formula formula for extracting color channels is as follows. Assume that COLOR is a 24-bit BGR value (which can be stored in a 32-bit integer). Also, use the mask values from above.

RED = (COLOR AND RED_MASK)
GREEN = (COLOR AND GREEN_MASK) >> 8
BLUE = (COLOR AND BLUE_MASK) >> 16

Combining channels

You can probably figure this out by yourself by now. After all, you know how to combine bits and how to shift them. Thus I will save you the explanation and just give you the formula, which is quite straightforward: it's basically the opposite of the formula used for extracting channels. First you perform the shifts, and then you perform the ORs.

COLOR = (RED) OR (GREEN << 8) OR (BLUE << 16)

Broken down in steps (only green is shown for simplicity's sake):

RED_T = 11110001 =        00000000 00000000 00000000 11110001
GREEN_T = 01011101 >> 8 = 00000000 00000000 01011101 00000000
BLUE_T = 11000001 >> 16 = 00000000 11000001 00000000 00000000

COLOR = RED_T OR GREEN_T OR BLUE_T

    00000000 00000000 00000000 11110001
OR  00000000 00000000 01011101 00000000
OR  00000000 11000001 00000000 00000000
---------------------------------------
    00000000 11000001 01011101 11110001

Conclusion

Whew, that was a long one. Probably the longest article I've written. I hope you've benefitted from it in some way, and hopefully it was worth the time it took to write.

Now back to the first question posed: why is 2 AND 2 not equal to 4? It's simply because 10 AND 10 (10 binary = 2 decimal) equals 10, since 1 AND 1 is 1 and 0 AND 0 is 0. In fact, anything AND itself IS itself.