Did you know that
2 AND 2 is not equal to 4? Well, it's not – open up
Windows Calculator, click  [and]  [=], 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.
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
The first operator we will briefly discuss is the
AND operator. Logical AND
is represented in different programming languages differently; the most common representations
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
|Expression:||1 AND 1||1 AND 0||0 AND 1||0 AND 0|
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."
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.
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
|Expression:||1 OR 1||1 OR 0||0 OR 1||0 OR 0|
XOR operator (exclusive OR) is like the
but it is only true when one of the conditions (not both) is true. It is represented
^ in common programming languages. (Note that
^ symbol is used by some languages such as VB to represent powers; this is a
completely unrelated operation.)
|Expression:||1 XOR 1||1 XOR 0||0 XOR 1||0 XOR 0|
NOT operator simply reverses the truth of an expression.
is equal to 0, and
NOT 0 is equal to 1, assuming that
1 means true
and 0 means false. It is represented as
! in code.
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
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?
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.
NOT is actually much simpler than bitwise
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
Bit shift operators
We now need to introduce two new operators: the left shift operator, represented
<<, and the right shift operator, represented
>>. As can be inferred from their name,
these operators shift the bits in a binary number by the specified amount.
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
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
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
To unset a bit, you must combine two operators,
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
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:
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
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.
The general formula formula for extracting color channels is as follows. Assume
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
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
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
1 AND 1 is 1 and
0 AND 0 is 0.
In fact, anything
AND itself IS itself.