AS3: Bitwise Operations

[Diki]

AS3: Bitwise Operations
-----------------
AS3: Main
-----------------

What are bitwise operations?
They are operations that are performed on the bits of a given value. Typically bitwise operations are used with integers. Throughout this tutorial I will only use integers in my examples.

What are the bitwise operators?
They are: ~, |, &, ^, >>, >>>, and <<. Here is a brief explanation of most of them:

~ (Bitwise Compliment)
The ~ operator "flips" each bit. That is, in any given value, all "0"s will become "1", and all "1"s will become "0".
Using this operator you can find the maximum possible value of the uint type:

var uint_max:uint = uint(~0);

This is because the integer value "0" is represented in this manner:

00000000  00000000  00000000  00000000

So when the bitwise compliment is used, every "0" becomes a "1", and every "1" becomes a "0".
Since there are no "1"s, the new value is this:

11111111  11111111  11111111  11111111

Which is precisely the maximum value that a 32-bit unsigned integer can hold.

| (Bitwise OR)
The | operator is very similar to the || operator. The main difference being that | compares bits, and || compares the values that the bits represent.
Let us assume, hypothetically, that in AS3 it is possible to represent a 1-byte integer. With a value of "64" it would look like this:

01000000

Now, assume we have another 1-byte value that is equal to "32". It would look like this:

00100000

If you were to perform a bitwise OR on the two values, like so 64 | 32, this is what happens:

64 | 32 equals:

01000000 (64)
00100000 (32)
-----------------
01100000 (96)

The bitwise OR compares each bit. If either bit is "1" the new bit is also "1". So you can think of it this way:

0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
1 + 1 = 1

& (Bitwise AND)
The & operator, just like the | operator, is similar to the && operator, respectively.
The difference between bitwise OR and bitwise AND is that the AND operator requires both bits to be "1" in order for the new bit to be "1" as well.
You can think of it like this:

0 + 0 = 0
1 + 0 = 0
0 + 1 = 0
1 + 1 = 1

So, using the same two 1-byte integers as above, 64 and 32, you will receive a very different result:

64 & 32 equals:

01000000 (64)
00100000 (32)
-----------------
00000000 (0)

^ (Bitwise Exclusive OR)
The bitwise exlcusive OR operator is kind of like the | and & operator combined.
It functions in this manner:

0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
1 + 1 = 0

In other words: one, or the other, but not both..
Using the same two 1-byte integer values above, you will get these results:

64 ^ 32 equals:

01000000 (64)
00100000 (32)
-----------------
01100000 (96)

In this case it is identical to using the bitwise OR, as there are no two matching "1" bit values.
But lets take a look at two different values:

213 ^ 137

11010101 (213)
10001001 (137)
-----------------
01011100 (92)

Number Systems and Bitshifting
Before explaining how bitshifting works, I must ensure that you have an understanding of how number systems work.
Understanding the difference between binary, octal, decimal, and hexadecimal will make understanding bitshifting a sinch.

First: What exactly is binary?.
Binary is a base2 number system. This means that each decimal point can only represent two differnet values: 0 or 1.
This is very differnet from the number system that you know and love, which is base10.

A base10 number system works like this: take the number "11738" for example.

11738

10000  1000  100  10  1
1      1     7    3   8

11738 means: (One 10,000) + (One 1,000) + (Seven 100s) + (Three 10s) + (Eight 1s).

Now, to make the math a little easier, lets take a look at a smaller value in binary.
Here is what 195 looks like:

11000011

128  64  32  16  8  4  2  1
1    1   0   0   0  0  1  1

11000011 means: (One 128) + (One 64) + (Zero 32s) + (Zero 16s) + (Zero 8s) + (Zero 4s) + (One 2) + (One 1).
Look fimiliar?

Let's take a look at a third, and final, example using hexadecimal. That crazy number system with the letters.
Let's take the number 61,804:

0x5F16C

65536  4096  256  16  1
5      F     1    6   C

0x5F16C means: (Five 65536s, F(15) 4096s, One 256, Six 16s, C(12) 1s).

Now you may be wondering how those 1-10000, 1-128, and 1-65536 ranges are calculated.
It is very simple:

The value of each decimal place is equal to the product of the previous value and the base, with the exception of the first decimal place, which is always "1".
In other words: in base10 the values increment 1..10..100..1000 because each value is being multiplied by the base, which is "10".
In binary the values increment 1..2..4..8 because each value is multiplied by the base, which is "2".
In hexadecimal the values increment 1..16..256..4096 because, you guessed it, the value is mutliplied by the base, which is "16".

If you are reading this section then I assume you now have a solid understanding of how number systems work.
So, let's take a look at what bitshifting is all about.

>> (Right Bitshift)
The >> operator "shifts" bits to the right. It is difficult to adequately explain what this means without just using numbers.
Consider the following:

213 >> 2 equals:
Step 1) 11010101 (213) (initial value)
Step 2) 01101010 (106) (first shift)
Step 3) 00110101 (53)  (second shift)

The bits get shifted to the right. Any bits that fall off the right end are lost. A zero is always padded onto the left.
Bitshifting is the binary equivalent of dividing. Each right bit shift is the equivalent of dividing by two (because binary is base2, remember?).

>>> (Logical Right Bitshift)
The >>> operator is almost identical to the >> operator. The only difference is that the >>> operator will preserve the "sign" of the value. That is, whether the value is negative or positive. This is useful when working with unsigned integers and you do not want the value to overflow into a negative value.

<< (Left Bitshift)
The << operator is pretty much the opposite of the >> operator.
The >> operator is the equivalent of dividing by two, and the << operator is the equivalent of multiplying by two.

Consider the following:

213 << 2 equals:
Step 1) 11010101 (213) (initial value)
Step 2) 10101010 (170) (first shift)
Step 3) 01010100 (84)  (second shift)

Wait a second. That didn't multiply by two at all!
That is because the integer is a 1-byte value, which I have been using to make the example simper.
In AS3 an integer value is 4-bytes. So lets look at what would actually happen in AS3:

213 << 2 equals:
Step 1) 00000000  00000000  00000000  11010101 (213) (initial value)
Step 2) 00000000  00000000  00000001  10101010 (426) (first shift)
Step 3) 00000000  00000000  00000011  01010100 (852) (second shift)

All bits get shifted to the left, and zeros are padded onto the right.

Continued in next post...
Since bitshifting is in the "left direction" there is no <<< operator. That only exists for right bitshifts.

[Diki]

So what does all this mean? Who cares about bitshifting? This is too complicated. :(

Let's take a look at a practical example.
Imagine you are given a colour value in the form of hexadecimal. Let's assume that the value is 0xFFE415CC.
This colour value is in the format 0xAARRGGBB.

Now once you pass that hexadecimal value to AS3 it will become an integer. You can no longer individually access the alpha, red, green, and blue values.
That is, you can't, unless you use bitwise operations!

Consider the following AS3 code:

var colour:uint = 0xFFE415CC;
var a:uint = (color >>> 24);
var r:uint = (color >> 16) & 0xFF;
var g:uint = (color >> 8) & 0xFF;
var b:uint = colour & 0xFF;

How are the values being pulled out from the integer?
Well, keep in mind that the format of the value is 0xAARRGGBB. This is very important.
The "blue" value is the simplest operation being performed above, so I will explain it first:

0xFFE415CC & 0xFF equals:
0xFFE415CC
0x000000FF
-----------------
0x000000CC

or in binary:

11111111  11100100  00010101  11001100
00000000  00000000  00000000  11001100
-----------------
00000000  00000000  00000000  11001100

This may appear confusing, but keep in mind that in hexadecimal prefixed zeros are irrelvent.
By this I mean that the number 0xFF is the exact same as 0x0000000000000000FF.

Then, the rest of the values are essentially calculated the same way, but are right shifted into the required position.
Calculating the green value can be explained like so:

(0xFFE415CC >> 8) & 0xFF

Step 1) 0xFFE415CC  (initial value)
Step 2) 0x00FFE415  (first shift)

0x00FF3415 & 0xFF:

0x00FF3415
0x000000FF
-----------------
0x00000015

or in binary:

00000000  11111111  00110100  00010101
00000000  00000000  00000000  11001100
-----------------
00000000  00000000  00000000  00000100

If the above confuses you, you might be thinking of the "15" in the hexadecimal value as "15". Remember, that is "0x15", not "15". There is a big difference.
The value for "red" is calculated the same way. The alpha value is calculated in a slightly different manner:

0xFFE415CC >>> 24 equals:

Step 1) 0xFFE415CC  (initial value)
Step 2) 0x000000FF  (first shift)

The >>> operator is used, opposed to the >> operator, as it is possible for the value to overflow, which would be erroneous.

And, finally, the value is shifted at intervals of "8" because 0xFF is 255, which if the maximum value of 1 byte.
That is, 0xFF/255 can be represented as follows:

11111111

Each color value in 0xAARRGGBB is a 1-byte value. So, therefore, each shift must also be 1-byte.

Hopefully you've learnt something about bitwise operations.
Feel free to ask any questions!

[MCarsten]

Wow pretty good tutorial. Covered everything for bitwise operations. I never got at all how the operations work but now I can see how you calculate it.

I liked a lot the ~ operator. I never saw that before.

I made an experiment with:
var u:uint=(~1);

And it output me:
4294967294

Which is the maximum length from uint, then I took the value and subtracted getting different numbers. Pretty cool.

What I really enjoyed was the explanation of hexademical operators for colors. Nice work.

[Jin]

Excellent tutorial. Maybe you should have given an example to illustrate the difference between arithmetic shift and logical right shift.

Maybe I'm wrong but isn't

0x000000FF
represented in binary like this?
00000000  00000000  00000000  11111111

So the green color value should be calculated like this:
00000000  11111111  00110100  00010101
00000000  00000000  00000000  11111111
-----------------
00000000  00000000  00000000  00010101

And I also noticed you used 2 different spellings for color.

[Diki]

At 10 minutes ago, Jin wrote: Excellent tutorial. Maybe you should have given an example to illustrate the difference between arithmetic shift and logical right shift.

Beyond the >>> operator preserving the positive/negative sign, I honestly don't know how to adequately illustrate the difference.
At least not without just showing that uint(~0) >> 2 and uint(~0) >>> 2 will produce different results.

It's a tricky thing to explain, I find.

At 10 minutes ago, Jin wrote: Maybe I'm wrong but isn't

0x000000FF
represented in binary like this?
00000000 00000000 00000000 11111111

So the green color value should be calculated like this:
00000000 11111111 00110100 00010101
00000000 00000000 00000000 11111111
-----------------
00000000 00000000 00000000 00010101

You are correct. I made a typo there that I missed while proof-reading.
It is times like this that I wish that the Newgrounds BBS had an "edit post" feature.

At 10 minutes ago, Jin wrote: And I also noticed you used 2 different spellings for color.

That's because I'm Canadian and am used to spelling it as colour but try to program using American spelling. As a result I often end up using both accidentally. :)

[MSGhero]

Some bitwise operations are quite faster than their Math. counterparts. A lot faster.

x mod y: x & (y - 1)
if x is an even number: (x & 1) == 0
absolute value: (x ^ (x >> 31)) - (x >> 31)

and other stuff.

Cited from http://lab.polygonal.de/?p=81

[Sandremss128]

In practice people only think about decimal / hexadecimal and binary representations of numbers, so 18 would be binary; 8A9FB would be hexadecimal and 01001011 would be binary. But you have to keep in mind that it is just a way of writing a number with a different base number. You can write a number with any base, not just 2 10 and 16. Of course it would be overkill to indicate this number for each number you write down but if you are talking bout conversion it would be nice to make people aware of this origin.
So for example this is how the number 17 would look like in different systems:

16		11	[0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F]
15		12	[0,1,2,3,4,5,6,7,8,9,A,B,C,D,E]
14		13	[0,1,2,3,4,5,6,7,8,9,A,B,C,D]
13		14	[0,1,2,3,4,5,6,7,8,9,A,B,C]
12		15	[0,1,2,3,4,5,6,7,8,9,A,B]
11		16	[0,1,2,3,4,5,6,7,8,9,A]
10		17	[0,1,2,3,4,5,6,7,8,9]
9		18	[0,1,2,3,4,5,6,7,8]
8		21	[0,1,2,3,4,5,6,7]
7		23	[0,1,2,3,4,5,6]
6		25	[0,1,2,3,4,5]
5		32	[0,1,2,3,4]
4		41	[0,1,2,3]
3		122	[0,1,2]
2		10001	[0,1]

Also a very important thing about bitwise operations is the concept of the Two's complement.
Negative numbers are important if you want to get deeper into this, there are allot of cool little things you can do with this system of representing numbers. This is also the reason that if you have a really large positive number it suddenly can become a really large negative number if you keep increasing.
Great tutorial nevertheless, its good to have an idea how the computer does these things with bits under the hood. Even though many operations can be done with conventional operators and the speed gain for the interpreted language that is actionscript wont benefit from bitwise operations that much, its an important concept for those who want the full package.

[Diki]

At 25 minutes ago, MSGhero wrote: Some bitwise operations are quite faster than their Math. counterparts. A lot faster.

Yeah, I forgot to touch on that in my post.
That's another thing that makes bitwise operations so damn useful.

At 25 minutes ago, MSGhero wrote: x mod y: x & (y - 1)

Note for readers: this is only true if y is a power of 2.
Otherwise you will have to use the modulus operator.