Storing Values in Bits

When programming in scripting languages such as JavaScript or ActionScript, we store values directly in a variable or often in an array. While bitwise operations are often relegated for use in higher-level programming languages such as C++, there are advantages to using them in scripting languages as well.

The premise behind storing values at the bit level is quite straightfoward. We simply store each value that we need in a row of bits. Let's say we had four true/false values that we want to keep track of. We could represent this in binary as 1100. Javascript primarily uses base 10 (decimal) or base 16 (hexadecimal) therefore 1100 can be represented in decimal as 12 or in hex as 0xC. If the third value turned into true then the number changes into 1110 or 14/0xE.

You can use the Scientific mode of the calculator in Windows to do conversions between the different bases.

When speed counts

So why would you ever need to store values this way? The largest advantage is its compactness. One hexadecimal character can store 4 true/false values. Being able to store more information in less space means saving bandwidth and faster downloads for your users.

The downside to this technique is it is only effective for storing multiple true/false or multiple choice values. It also obfuscates the application logic as you'll have to document somewhere what each bit actually does. Obfuscation could also be looked at as a plus since someone looking to use your code would have a harder time figuring out what's happening without the documentation.

Here's a quick Javascript example demonstrating the different methods of we store values:

var A1 = true;
var A2 = false;
var B = Array(true, false);
var C = 0x2; // the hexadecimal way of writing 0010

As you can see, C takes up less bytes than options A or B.

Working with our bits

We turn to our bitwise operators. You're probably familiar with the && and the || but now it's time for the & and |. These work much like the && and || operators but they work at the bit level. They go through, compare each bit and spit out the result.

Let's take two binary chunks: 1001 and 1010. First, we need to convert it into a base we can use in Javascript. We'll use hexadecimal in this example. 1001 becomes 0x9 and 1010 becomes 0xA.

var a = 0x9 & 0xA; // a = 0x8 (1000)
var b = 0x9 | 0xA // b = 0xB (1011) 

How to check if a bit is on or off

To pull out one single value, we need to create a bit mask. In the bit mask, any bit that we want to pull out should be set to 1 and the rest would be set to 0. To pull out the second value from the left, our mask would be 0100 or 0x4. Comparing our bit mask against 1011 (using the & operator) for example would give us 0 (in any base!). But comparing the mask against 1111 (again, using the & operator) would give us 0100 or 0x4.

This code example tests a bit:

isBitOn= (bits & mask == mask) ? true : false;

How to turn a bit on

We'll use our trusty | operator for this. When doing an OR comparison, if either value is true then the final value is true. Our bit mask, this time, will have a 1 for each bit that we want to turn on and a 0 for each bit we want to ignore. Let's use our bit mask from the previous example: 0100. If we compare this against 1001 we get 1101. Comparing against 1101, we would be left with the same value: 1101.

0x2 | 0xC = 0xE

How to turn a bit off

To turn a bit off, we'll head back to our & operator. This time we'll put a 1 for each bit we want to leave untouched and a 0 for each bit we want to turn off. If we have 1011 and we want to turn off the first bit from the right then we get the following: 1011 & 1110 = 1010.

0xB & 0xE = 0xA

There's actually a second way we can do this. For this, we can use the bit mask in the traditional way by having each bit that we want to turn off set to 1 and each bit we don't want to touch be set to 0. We use the NOT operator (~), which inverts each bit, before we use the AND operator. Example: 1011 & ~0001 = 1010.

0xB & ~0x1 = 0xA

One thing that I'd like to clarify here is that ~0x1 does not equal 0xE. The reason for this is the NOT operator works on a full byte, which is two hexadecimal characters (Eg: 0xFF). So, ~0x1 actually equals 0xFE. The next thing to mention is that the first bit from the left may be used to determine if the number is signed or not. If it's not signed then the range is from 0 to 255 and 0xFE would be 254. If it is signed and the first bit is turned on then it means that it's a negative number and 0xFE would be -2. In the end, it's a moot point since the bit mathmetics work out the same in the end. You will only have to be careful of this if converting things between bases, especially into decimal.

How fast can I get my value?

Faster than arrays but slower than a variable.

A quick test on my system showed that assigning a value to variable and pulling it back out beat a bit mask about 2:1. But pulling the values out of an array was slower than bit masking at a ratio of about 5:1.

Notes

Bitwise operators should be available in pretty much any language. In fact, most of these operators will likely work in your language. The &, |, ~ will work in JavaScript, Flash ActionScript, Java, PHP and likely others as well. For VBScript users, there's the AND, OR, and NOT operators.

For more information check out: Bitwise AND, OR, XOR and NOT

Published September 14, 2004 · Updated September 17, 2005
Categorized as JavaScript
Short URL: https://snook.ca/s/220