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.

Expression: | 1 AND 1 | 1 AND 0 | 0 AND 1 | 0 AND 0 |
---|---|---|---|---|

Result: | 1 | 0 | 0 | 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."

### 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 `||`

.

Expression: | 1 OR 1 | 1 OR 0 | 0 OR 1 | 0 OR 0 |
---|---|---|---|---|

Result: | 1 | 1 | 1 | 0 |

### 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.)

Expression: | 1 XOR 1 | 1 XOR 0 | 0 XOR 1 | 0 XOR 0 |
---|---|---|---|---|

Result: | 0 | 1 | 1 | 0 |

### 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 `AND`

s, `OR`

s, `XOR`

s,
`NOT`

s, 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.

## Comments (10)

ex: #9 is stored. This is equil. to Cheese and Ham. So, if you started with the 9, how would you go about reversing the info to print out the Cheese and Ham?

Larry

`bitmask = 9`

for i = 0 to 7

if(bitmask AND CHEESE) then print "Cheese"

if(bitmask AND CHICKEN) then print "Chicken"

...

loop

This will work assuming that any nonzero value evaluates to True. Why will it work? Because AND will give you the bits in common with the bitmask and the given single bit such as CHEESE.

`00001001 //9 AND 00001000 //HAM ------------ 00001000 //Nonzero value means HAM bit is set`

`00001001 //9 AND 00000100 //PEPPERONI ------------ 00000000 //Zero value means PEPPERONI bit is not set`

## Leave a comment