March 2, 2015

Bitwise Operations Part 3: The Logic Operators

Check here for Part 2, Binary and Two’s Complement.

In this post I’ll be covering all the logical bitwise operators in Javascript, but the principle is the same across all languages. There are so many cool and exciting things we can do with them, but that’ll be saved for later.

What Do You Mean, Bitwise? #

A bit is the smallest unit we can represent data in: ON/OFF, true/false, 0/1. If we string together 8 bits of data, we can call it a byte (though 1 byte doesn’t always mean 8 bits!). It’s practically unheard of nowadays to address units of memory in single bits, instead we use bytes for our needs. A byte is defined in C as an “addressable unit of data storage large enough to hold any member of the basic character set of the execution environment”. From hear on out, we will refer to a byte as 8 bits.

A byte can store up to 256 different values. Let’s take a look at an example byte, 00110101. We can evaluate this either as the binary value for 53, or simply 8 on’s and off’s. If we think about each digits as a bit for representing on or off, we can logically reason with the individual bits, hence bitwise operations.

Reasoning with Bits #

When we use bitwise operators, we are directly comparing the individual bits of two values and return a single value. The operators will work much the same way as the logical operators you’re used to, like && and ||. We’ll even introduce some new ones!

NOT #

First off we have NOT. The logical not, !, returns the invert boolean of the expression. True to false, false to true. The bitwise operator does the same thing, except we will look at the individual bits. Example:

console.log(~6); //prints out -7

As decimals, the inverse relationship between 6 and -7 is not immediately obvious. But once we look at the binary of the two numbers, we’ll see exactly why the NOT operator returns -7. Take a look at part 2 if you need a refresher on Two’s Complement. Now, let’s see what’s going on with the code above.

 6 = 00000110
-7 = 11111001

We can now see that -7 is just the inverse of 6 in binary. Normally, integer values are stored in 32-bits, so 6 and 7 might look something like this:

6 = 00000000000000000000000000000110
7 = 11111111111111111111111111111001

Pretty neat, eh? Strap in because we’re going to look at all the logical operators. From this point on, we’ll only be showing the smallest 8-bits of the integer, effectively just dealing with unsigned integers. Just remember that there still will be 24 more bits in front!

AND #

Ever wondered why the AND logic operator is two ampersands instead of just one? Perhaps it’s because the single ampersand, &, is already reserved for the bitwise AND operator. We know that a logical AND takes in two expressions and returns true if both of the values evaluate to true, otherwise it returns false. Here’s its truth table, a combination of all the different inputs and result of AND.

a b a & b

0 0 0

0 1 0

1 0 0

1 1 1

a	b	a & b
0	0	0
0	1	0
1	0	0
1	1	1

Now, let’s do this bitwise.

11111111 AND
00001111 
--------
00001111

//Let's see it in decimal.
console.log(255 & 15); //prints "15"

OR #

Since two pipes are used for the logical OR, we can now see how a single pipe would be reserved for the bitwise OR. As the following truth table describes, OR will return true when either of the values are true.

a b a | b

0 0 0

0 1 1

1 0 1

1 1 1

a	b	a \| b
0	0	0
0	1	1
1	0	1
1	1	1

An example:

10101100 OR
01100110 
--------
11101110

console.log(172 | 102); //prints out "238"

XOR #

Ready for one you might not have encountered? The XOR operator returns true only when the two values are different, and returns false when they are the same. The operator for XOR is a single caret.

a b a ^ b

0 0 0

0 1 1

1 0 1

1 1 0

a	b	a ^ b
0	0	0
0	1	1
1	0	1
1	1	0

01010101 XOR
11110000
-------
10100101

console.log(85^ 240); //prints "165"

As you may have noticed by now, the order of the two inputs does not matter for AND, OR, or XOR. Even if we switch the inputs around, the result will be the same. We can exploit this and do some cool things with it:

//Given an input array of numbers, find the number that appears in the array only once. 
//All other numbers appear in the array twice. 
//Example: findSingleInt([1,1,2,2,3,3,4,5,5]) returns 4.

function findSingleInt(array){
  var result = array[0];
  for(var i = 1; i < array.length; i++){
    result = result ^ array[i];
  }
  return result;
}

What’s going on above? We are exploiting the fact that any number XOR itself will return 0. Multiple XOR’s will be “remembered”, i.e. 2^7^7 = 2. Why? If we map out the bits, the answer will become much more clear.

0010 XOR
0111 
----
0101 XOR
0111 
----
0010

There’s so much more we can do with bitwise operators, I hope this has given you a small taste of how powerful these simple operators are. Check back later for part 4: The Shift Operators!

Kudos