Bitwise, Byte Foolish?

 

To avoid Carnival, Logan is trying to get some plastic surgery from Farrah Fawcett.

To avoid Carnival, Logan is trying to get some plastic surgery from Farrah Fawcett.

In the post-apocalyptic world of Logan’s Run, humans live out cramped lives in a bunker. Because of the crowded conditions, all citizens must submit to Carnival on their 30th birthdays. What do you do on your Carnival day? You and all the other 30 year olds spiral up into the air and get zapped to death.

Sound like a bad deal? It gets worse. The radiation outside has long since subsided, and the rules being enforced are no longer necessary.

I’ve been immersed in JavaScript for the last few years. Every time I’ve read about JavaScript’s bit operations (and it has a very nice set of ops), I’ve been warned that they are “a hack,” and “slow.” This has always bummed me out. I love bits.

But I got to thinking the other day, all these warnings sound like a sort of a Logan’s Run passed-down message from days gone by. With all the cool things that have been going on with JavaScript lately (thanks to Google’s V8 and the various JIT subsystems going into browsers), maybe, just maybe, bitwise operations have sped up enough to be worthwhile. Since some of the JIT compilers are doing type inference, a series of bit operations could, in theory, be done at full speed, without costly implicit type conversions.

Who Needs Bits?

When I started programming (on 8-bit processors), I mostly worked with integers. When floating point numbers became available, I avoided them for years because they were slow. We did as much math as we could with integers and bit operations. Shift left once, and that’s a multiplication by 2. If you wanted to multiply by 10, you’d do a shift left by one (times two) and a shift left by 3 (times eight) and add those results together.

You wouldn’t do math like that any more, but bits are still good as flags. A single JavaScript number (when treated bitwise) can hold 32 boolean flags!

Here’s what I found out. Just about everything I tried was faster with bitwise operations than with other solutions (even in Internet Explorer). No, you can’t usefully replace one multiplication with a series of adds and shifts, but by no means are bitwise operators too slow to be useful.

        k=~~i; //this is much faster
        k=Math.floor(i); //than this

You can lop off the decimal part of a number not just with ~~, but with ^0 and <<0, too. And they are ALL significantly faster, in all modern major browsers, than calling Math.floor().

//break a number in the range 0-65535 into
// low and high bytes

// this is significantly faster
    lo = i & 255;
    hi = i >> 8;

//than this
    lo = i % 256;
    hi = (i-lo)/256;

Don’t discriminate against JavaScript’s bitwise operators. But keep these things in mind…

  1. You have 32 bits to work with when you treat a JavaScript variable as bits. And that top bit is a sign bit (meaning any number with that top bit set is a negative number).
  2. Don’t mistake bitwise for logical operators.
  3. Learn the difference between “-” and “~”.
  4. Remember that >> shifts the sign bit down while >>> shifts a zero into the top bit.

My favorite place to learn about JavaScript bitwise facilities is here: Bitwise Operators.

When should you be using bitwise operators? Obviously, when you want to pack a bunch of flags into one variable. That should be much faster than having an array of flags.

Dealing with the red, blue, and green parts of a color call out for bitwise operators.

And think about using a shift when you want to multiply or divide by a power of 2, while at the same time converting a floating point number into an integer. Two operations for the price of one!

Advertisements

Combinations and Permutations in JavaScript

Range

In JavaScript Numbers Can Bite, I talked about a problem that can crop up in JavaScript when you’re doing calculations with integers.

At the end of the post I hinted at a better way to write the combination function. Let’s go ahead and implement it. I’ll throw a permutation function in as well.

Let’s look at combinations. The formula is:

n!/(k!*(n-k)!)

That’s for n items, taken k at a time. In my mom’s family, there were seven children. How many combinations of them are there if you take 4 at a time?

7!/(4!*3!)

Now, if we write out the factorials, we immediately see a simplification (not in notation, but in floating point operations).

(7*6*5*4*3*2*1)/(4*3*2*1*3*2*1) = (7*6*5)/(3*2*1)

What we need here is a function that multiplies a range of numbers. Then we have:

productRange(5,7)/productRange(1,3)

or more generally,

productRange(k+1,n)/productRange(1,n-k)
function productRange(a,b) {
  var product=a,i=a;

  while (i++<b) {
    product*=i;
  }
  return product;
}

function combinations(n,k) {
  if (n==k) {
    return 1;
  } else {
    k=Math.max(k,n-k);
    return productRange(k+1,n)/productRange(1,n-k);
  }
}

So that’s combinations, where the order of the items doesn’t matter. What about permutations, where the order does matter? The formula is:

n!/(n-k)!

That one is simple…

function permutations(n,k) {
  return productRange(k+1,n);
}

JavaScript Numbers Can Bite

Sooner or later, JavaScript’s numbers will bite you. They bit me in a probability function, and I didn’t even see it coming.

Maybe you took a probability and statistics class and learned about combinations and permutations. You may remember that the formulas for those involve factorials. Let’s take a look at my combination routine.

    //---------------------------------------------------------
    // Function: combinations
    //   returns the combinations of k objects from a set of n objects
    combinations=function(n,k) {
        function factorial(a) {
            return a<2 ? 1 : a*factorial(a-1);
        }
        return Math.round(factorial(n)/(factorial(k)*factorial(n-k)));
    }

Kind of an interesting looking function, isn’t it? When you find the number of possible ways that you can put together a k objects from a set of n objects, you need to do three factorial functions. Since I didn’t need factorial anywhere else, I stuffed it inside the combinations function.

But what’s the Math.round doing there? Aren’t we dealing with whole numbers here? Yep. In most languages, we’d explicitly declare the variables for this function to be integers, but that’s just not an option in JavaScript–all numbers in JavaScript are floating point numbers.

Trouble Ahead

So where do we run into trouble? If n is 23 and k is 2, combinations returns 253.00000000000003.

Even more frustrating is this answer because it’s one we can come up with off the top of our heads: If n is 24 and k is 23, we get 23.999999999999996.

What’s happening? Our numbers are growing so large in factorial that they can no longer be represented exactly in JavaScript. The solution? In this case, I fix the result with Math.round().

Playing Computer

But we can do better if we play computer with even a small case. Let’s take n=5, k=2;

combinations=(5*4*3*2*1) / ((3*2*1) * (2*1));
//largest number calculated is 120

That could be changed to

combinations=(5*4) / (2*1);
//largest number calculated is 20

A huge change. Much better. Three floating point operations rather than nine. Less chance for mischief.

Factorial is a well known function, and the combination formula is easy to write in terms of factorial, but that ease of representation comes at a huge computational cost, and in the case of JavaScript, sometimes a cost of precision.

If we rewrite the function to take advantage of this insight, we’ll be able to support much larger parameters before we run into trouble.

The General Idea

The solution to most of these problems is to rearrange the math so intermediate results don’t get as big.

This was a nasty problem to catch, because many results were calculated correctly. But it didn’t take long to come up with a couple solutions.