Something a bit different
During a follow-up technical phone interview with Houzz today, I was asked to write a function that takes two integers and calculates the number of bits at which they differ.
For example, given 2 and 7, which are 010 and 111 in binary, return 2 because they differ at 2 bits (the 1's place and the 4's place). Here was my initial thought:
def bit_difference(int1, int2) xor_int = int1 ^ int2 (xor_int.to_s(2)).split('').map(&:to_i).reduce(:+) end
I knew I wanted to use bitwise operations, and xor (^) was a logical choice because by definition it returns 1 at bits where the two inputs differ, and 0 where they do not. E.g., for 2 and 7:
010 ^ 111 ------ 101
At which point I just needed to count how many ones were in the resulting binary integer, which is trivial if you're willing to play a little code golf. Poor style notwithstanding, it gets the job done. The time and space complexity here are both O(k), where k is the number of bits in the larger of the two inputs.
My interviewer was interested to see if there was a more elegant way to calculate this, which forced me to think about what other bitwise operations I could make use of. I'd never coded with bitwise operators other than xor before, and in fact my only knowledge of the existence of the other operations was thanks to Scott Chenier sharing some recently acquired knowledge during an impromptu pairboarding session. (Thanks, Scott!)
So I didn't fully code up this solution during the interview, but I attempted to talk through it and later wrote it up after refreshing my memory on bitwise operations with Kat, Melissa and Matt Corley:
def bit_difference(int1, int2) xor_int = int1 ^ int2 bit_detector = 1 count = 0 until bit_detector > xor_int digit = bit_detector & xor_int count +=1 if digit != 0 bit_detector = bit_detector << 1 // abbr <<= also works! end count end
The big picture here is that we increment a counter each time we come across a bit in xor_int that has a value of 1. We acccomplish this by using the & ('and') bitwise operator, which returns 1 at bits where the two inputs are both 1, and 0 otherwise. If we take xor_int & 1, we will get back a nonzero number if and only if xor_int has a 1 in the 1s place. Then we need to check the 2's place, the 4's place, and so on, potentially incrementing our counter each time. To do this, we use the left shift operator, <<, which moves all bits left (adding a zero to the 1's place)*. Now, when we take xor_int & 1, we will be checking the 2's place. We keep checking bits until bit_detector is larger than xor itself, meaning we've checked all of xor_int's bits. Finally, we return our count.
This solution is O(1) space and O(k) time, where, as before, k is the number of bits in the larger of the inputs. It's more lines of code, but it's more space-efficent, and technically a bit more time-efficient too, even though they both come out to O(k) in the end. Most of all, it's more elegant and makes use of some cool operations that, granted, we may never need to know outside of an interview setting but are fun to know about!
*Note this has the effect of multiplying bit_detector by 2. Conversely, shift right by 1 (>> 1) has the effect of dividing by 2 (and flooring). (Thanks Jordan for the correction!)