Bitwise Operations

 When I was in 9th grade, I once spent the day going to school with my cousin.  At lunchtime, one of her friends was showing off a newfound skill:

"I can count to ten in German! Eins, zwei, drei, vier, funf, sechs, sieben, acht, neun, zehn!"

"That's nothing," I said, "I can count to ten in binary.  1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010!"

No one got it.  And unfortunately, it seems like binary is also foreign to a lot of software developers as well.

What is Binary?

Binary is the two-digit radix (or base) system.  In the decimal system - what most people use on a daily basis - we use ten different digits (the Arabic numerals 0, 1, 2, 3, 4, 5, 6, 7, 8, 9) to represent number values.  Numbers in the rightmost position before the decimal point represent that digit's value multiplied by ten to the zeroth power, and each position to the right increases the power of ten by one.  So 12 is actually another way of saying 1*10^1 + 2*10^0; 433 is equivalent to 4*10^2 + 3*10^1 + 3*10^0; and -82 is equivalent to -8*10^1 + -2*10^0.

    In binary, we use only two digits - the Arabic numerals 1 and 0.  So in order to represent values greater than 1, we use the same system of digit position representing the base raised to a certain power as a coefficient for each digit.  1 in binary is another way of writing 1*2^0, while 10 is equivalent to 1*2^1, and 1001 is equivalent to 1*2^3 + 0*2^2 + 0*2^1 + 1*2^0.  If you calculate that last expression, we can see that 1001 in binary is equal to nine.

What does this matter?

The short answer?  For most programming purposes, it doesn't - a binary number has a different symbolic representation than a decimal number, but it has the exact same mathematical properties.  In binary, 101 (i.e., five) * 10 (i.e., two) = 1010 (i.e., ten), just like in the decimal system.  And in fact, higher-level languages like JavaScript convert all of their mathematical operations on decimal numbers to binary before doing their calculations.  Using my speedtest comparison code from my previous post, we can even see that the difference in speed using bitwise operations (i.e., special binary operations, which we'll go over later) like << perform basically equivalently to their corresponding decimal operations:



The long answer? Because computer code is ultimately written is bits of 0 and 1, when your computer executes code, it's doing mathematical operations in binary.  So, at a base level it's often easier to think about and use code that actually states those operations outright.  For instance, in my post on pseudorandom number generators I linked to a ruby program that used bitwise operations:




In the first highlighted line, "x >> 1" is a bitwise operation that means "shift the binary representation of x to the right one place and remove the leftmost bit".  So we could calculate 5 >> 1 as follows: 5 is written as 101 in binary.  Moving every digit over one would leave us with 10.1, and we would remove the rightmost 1 and be left with 10, which is two.  So 5 >> 1 equals 2.

What the >> operation actually is doing is you are finding the number to the left of the operator's value modulo 2 to the power of the number to the right of the operator's value (in elementary math terms, modulo basically means divide and find the remainder), subtracting it from the number, and then dividing the result by two to the power of the number to the right.  Which is sort of complicated to say and a bit wordy in code as well, so we just use >> instead.

But it's the the ^ symbol in the second highlighted line where the rubber really hits the road. ^ is the XOR operation, which is also known as the nim-sum.  When you XOR two numbers, you take their binary representations and, for each bit position, you see if there is exactly one 1 between the two representations.  And if there is, the XOR sum gets a 1 in that position, and if not, it gets a 0.  For example:

   10101

+11101

---------

  01000

Figuring out how to do this in actual code can be a bit complicated.  Here's one way I wrote up:


In addition to being much, much longer than just writing (x ^ y), this implementation is much, much slower than the native bitwise function:



To be fair, this time difference is due to the fact that we're calling a function, defining variables and performing various operations on them...but that's also the point.  Bitwise operations like XOR can easily be accomplished at the assembly level with your regular logic gates; there's no need to spell these things out at a higher level of abstraction.

On top of simplicity and speed, there's lots of neat things you can do with bitwise operators like the XOR (for instance, cryptography applications).  Stay tuned for part 2, where we'll go into more detail on various bitwise operators and their applications!

Comments

Post a Comment

Popular posts from this blog

The Sorting Hat

Image
Here's a lesson about the difference between theory and practical applications. Everyone knows about  bubble Sort  and  merge Sort  - they're probably the first two sorting algorithms you learned.  Everyone also knows that (1) bubble sort sucks and (2) this is due to the fact that its average time complexity is O(n^2), aka the worst time complexity.  It even generally performs worse than things like insertion sort and  selection sort , the "a D- is still a passing grade" of sorting algorithms. While all these things are true, there's a more important truth: always test your code. While reading  The Imposter's Handbook by Rob Conery  the other day and flipping through the comparison sort algorithms he provides, I decided, Why not actually test out this code?   And, the  speed test demon  that I am, my test involved sorting out his [23,4,42,15,16,8] array one million times with bubble sort and with merge sort, and I got this res...
Read more

Kadane's Algorithm

Imagine it is 1977.  You do not have a degree in computer science.  You have not spent months grinding leetcode.  You are given a algorithm problem that a decorated mathematician has already created what looks like an optimal solution. And then in less than a minute you come up with a better answer. You are  Jay Kadane , and the problem that you have solved is the maximum subarray problem. The maximum subarray problem gives you an array of numbers and asks you to pick out the subarray with the largest sum.  The problem is trivial if all the numbers are positive: [ 1 , 5 , 1 , 3 , 2 ] <- the largest subarray is obviously the entire array But what if you've got some negative numbers thrown in there? [ 1 , 5 , -1, 3 , - 2 ] <- sure, you don't want the negatives. But isn't taking the -1 worth the +3? A brute-force solution materializes pretty easily: just create every subarray and find the biggest sum: [ 1 ] = 1 [ 1 , 5 ] = 6 [ 1 , 5 , - 1 ] = 5 ...
Read more

Loose Equality, the Null Operator, and Other Oddities

 Here's a fun bit of code to run: console . log ( '0.5' == 0.5 ) //evaluates to true console . log ( '0.5' === 0.5 ) //evaluates to false The first equality statement is what's known in JavaScript as "abstract equality comparison", which people usually refer to as "loose equality."  Loose equality compares objects only after doing a type conversion - so even though '0.5' is a string and 0.5 is a number, JavaScript sort of jams them together and says "sure, good enough."  It's weird, but convenient sometimes when dealing with data that's really (in an abstract sense) numbers but could come through the pipes as either a number or a string. People have written surprisingly long algorithms to precisely define what  abstract equality  and  strict equality (aka, normal equality)  mean in JavaScript and other languages that adhere to the ECMAScript standards.  But for our regular usage, things that are to people the same ...
Read more