Exercises

The following exercises provide you with the opportunity to practice with bit vectors and bit manipulation. The solutions to these exercises are found in the section .

1. Write a function that accepts a binary string and returns the decimal number that the string represents. For example, if the function receives the string "100101", the function should return the integer 37. (Note that this is essentially the functionality of the Python expression 0b. However, this exercise is to build the same functionality from scratch.)

2. This exercise is the inverse of the previous exercise. Here, you are to write a function that receives a decimal number and returns a binary string. This binary string should always contain 32 bits, even if that means that there will be many 0 bits on the left-most side. So, if the function receives the integer 37, the function should return "0000000000000000000000000100101". (This is essentially the same functionality as Python’s bin command, but again, you are to build this function from scratch.)

3. Toward the end of this chapter, I explained how the set operations union, intersection, and difference work. However, I only demonstrated how they operate on two single integers. Let’s get our BitVector class to perform these operations as well.

   Specifically, add three new methods to our BitVector class. The union method should allow a BitVector instance to accept a second BitVector instance and return a third BitVector instance that represents the union of the first two bit vectors. The intersection and difference methods should work similarly, except that they return a bit vector representing the intersection and difference, respectively. To keep things simple, you can assume that the two bit vectors we’re operating on are of the same size.

4. Write a function that accepts two integers and returns their hamming distance. The hamming distance of two integers is the number of digit places in which the two integers have different bits. For example, take the integers 1 and 8. Their hamming distance is 2, and here’s why:

   ​	1: 0001
   ​	8: 1000
   ​	^ ^

   You can see that in two different digit places (the right-most and left-most places), the 1 and the 8 have different bits. Because the bits are different in two places, we say that 1 and 8 have a hamming distance of 2.

   The integers 7 and 8 have a hamming distance of 4 since they have different bits in four digit places:

   ​	7: 0111
   ​	8: 1000
   ​	^^^^

   The key is figuring out what bitwise operations to utilize within your function.

5. Puzzle: This is one of my all-time favorite computer science problems. You are given an unsorted array that contains integers. It’s guaranteed that in this array, each integer appears exactly twice—except for one integer that appears only once. For example, the array might be [5, 9, 9, 3, 5]. The 3 only appears once, but the 5 and 9 both appear twice.

   Write a function that returns the integer that only appears once in the array. For this example, your function should return the integer 3.

   This may sound simple enough, but there’s a catch. Your function should run in O(N) time and take up no extra space. This rules out using a hash table or even a bit vector since those both take up space. It also rules out sorting since that takes O(N log N) time.

   Once again, bitwise operators will be your friend. In fact, you may need one bitwise operator. Hint hint.