October 5th, 2010, 09:19 PM
Its fast. Really, really, really fast. By understanding how to use binary effectively you can solve problems extremely quickly. Lets take a few examples.
First, a recent Java forum question was how to calculate the power of two greater than the given number. The general advise was to use either an O(n) loop to calculate all powers until found, or to use log2 arithmetic. A simpler and fast answer
is to take advantage of the binary representation. After finding the highest 1 bit, a left shift's property of being a multiple of two was used to find the next power.
Another simple example is to generate a powerset. An easy implementation is to use a bit per element and an integer as a counter. For each permutation, increment the counter and evaluate each bit field to determine membership in the output set. The shift operator is used to create the bit mask to zero out all of the other bit fields.
This use as a bit mask has a lot of power. For example, a bloom filter is a very compact data structure that provides a probabilistic Set. It uses a bit-vector and multiple hashing functions to set bit fields. Membership is determined by seeing if an element's bit indices are set. This allows not storing the actual element itself at the cost of false positives. It is therefore a "filter" because it allows us to remove the negative cases, thereby reducing how often we perform an expensive operation (e.g. I/O call).
Core design principles
when developing software systems.
See my open-source project
as an example of professional code.
The opinions expressed do not represent those of my employer.