Войти в систему
Войти с помощью соц. сетей:
These are the solutions to the .
Here is one way we can convert a binary string into a decimal number:
| | def decimal(string): |
| | integer = 0 |
| | power = 0 |
| | index = len(string) - 1 |
| | |
| | while index >= 0: |
| | if string[index] == "1": |
| | integer += 2**power |
| | |
| | index -= 1 |
| | power += 1 |
| | |
| | return integer |
This function accepts a string parameter. We expect this to be a binary string such as "000101001010".
We start by initializing an integer at 0. Eventually, this will be the decimal number we return at the end of our function.
We also initialize a power variable, which we’ll use to help us compute what number each digit place of our binary string represents. The right-most digit place will be 2 to the power of 0 (that is, the ones place). The next digit place to the right will be 2 to the power of 1, which is the twos place. The digit place immediately to the right of that is 2 to the power of 2, which is the fours place, and so on.
We then begin a loop which scans our binary string from right to left by tracking an index. We use the current power to compute the number that is represented by the digit place of the current index. If there is a 1 at the current digit place, we take the number represented by the current digit place and add it to integer. For example, if we’re looking at the eights place and there’s a 1 bit there, we add 8 to integer. If there’s a 0 bit there, we simply proceed to the next round of the loop without modifying integer in the current round.
Alternatively, there’s another way we could have computed the value of each digit place without tracking a power variable. Instead, we could compute each digit place by doubling whatever the previous digit place to the right represented:
| | def decimal(string): |
| | integer = 0 |
| | place = 1 |
| | index = len(string) - 1 |
| | |
| | while index >= 0: |
| | if string[index] == "1": |
| | integer += place |
| | |
| | index -= 1 |
| | place *= 2 |
| | |
| | return integer |
When I benchmark both approaches, this second version turns out to be faster. This is because computing powers is slower than performing simple multiplication.
Here is a Python-based approach for converting a decimal number into a binary string:
| | def binary(number): |
| | place = 2147483648 |
| | binary_string = "" |
| | |
| | while place >= 1: |
| | if number >= place: |
| | binary_string += "1" |
| | number -= place |
| | else: |
| | binary_string += "0" |
| | |
| | place //= 2 |
| | |
| | return binary_string |
This function accepts a number parameter; this is the decimal number we will convert into a binary string.
The first thing that will undoubtedly jump out at you is the seemingly random integer of 2147483648 that we initialize our place variable with. However, I’ve chosen this number with careful precision. Because the exercise asks us to return a string containing exactly 32 bits, this means that the right-most bit represents the 2147483648s place. That is, 2 to the power of 31 is 2147483648. (Remember, it’s the second-to-right-most bit that represents 2 to the first power. Accordingly, 30 bits to the right of that will represent 2 to the 31st power.)
We initialize a binary_string as an empty string. By the time our function is complete, this will contain 32 characters that are either "0" or "1", such as "00000000000000000110100110101011". So, this is what we’ll return at the end of our function.
In the meantime, though, we begin a while loop. In the loop’s first round, we check to see if there should be a 1 in the 2147483648 place. This would be the case if our input number is greater than or equal to 2147483648. If we find that number is indeed greater than or equal to 2147483648, we place a "1" in that spot of the binary_string.
As an example, let’s pretend our input number is a smaller number, such as 9. To determine if we should place a 1 bit in the eights place, it all depends on whether 9 is greater than or equal to 8. Since 9 is greater than 8, we’ll put a 1 bit in the eights place. If we put a 0 bit in the eights place, it’s impossible to produce a binary string that can equal 9 with the remaining digit places to the right. That is, the greatest number we can represent with a 0 bit in the eights place is 0111, which is only 7.
If our number is smaller than 8, though, we certainly can’t put a 1 bit in the eights place, since our binary string would then represent a number of 8 or greater.
In any case, if within a particular loop round we do place a "1" into our binary_string, we then reduce number by the place we’re in to determine what the rest of the binary string should look like. Again, dealing with the example number of 9, once we place a 1 bit in the eights place, this means that we need to figure out how to represent what remains of number, specifically 1, as 9 - 8 = 1.
Whether we place a 1 bit or 0 bit in the current place, we then compute the next place to the right by halving place. By the time our loop is complete, binary_string will contain some combination of 32 0 and 1 bits that properly represent our input number.
Here, I’ve added three methods to our BitVector class:
| | def union(self, other_bit_vector): |
| | bv = BitVector(self.range_of_bits) |
| | |
| | for i in range(len(self.integers)): |
| | bv.integers[i] = self.integers[i] | other_bit_vector.integers[i] |
| | |
| | return bv |
| | |
| | def intersection(self, other_bit_vector): |
| | bv = BitVector(self.range_of_bits) |
| | |
| | for i in range(len(self.integers)): |
| | bv.integers[i] = self.integers[i] & other_bit_vector.integers[i] |
| | |
| | return bv |
| | |
| | def difference(self, other_bit_vector): |
| | bv = BitVector(self.range_of_bits) |
| | |
| | for i in range(len(self.integers)): |
| | bv.integers[i] = self.integers[i] & ~other_bit_vector.integers[i] |
| | |
| | return bv |
The union method uses OR as I described in the chapter. However, instead of ORing two integers, we OR two arrays of integers. To do this, we run a loop in which we iterate over each index (i) of both arrays. When i is 0, for example, this means we OR the first integer of the first bit vector with the first integer of the second bit vector. We place the result in a brand-new third bit vector’s underlying array. Finally, we return the new bit vector.
The intersection and difference methods work similarly, except that they use their appropriate bitwise operators.
We could compute the hamming distance by scanning the two integers and comparing the integers’ bits at each digit place. But why do all that work when our good pal XOR can do the heavy lifting for us?
As I mentioned in the chapter, XOR is essentially a litmus test that reveals precisely where two integers have differing bits. Specifically, it does this by placing a 1 bit in each digit place where the two integers have opposite bits.
So, our approach is to XOR the two integers (x and y in my code that follows), producing an integer called difference, and then we count how many 1 bits are in difference:
| | def hamming_distance(x, y): |
| | difference = x ^ y |
| | |
| | bit_count = 0 |
| | |
| | for n in range(0, 32): |
| | mask = 1 << n |
| | if mask & difference != 0: |
| | bit_count += 1 |
| | |
| | return bit_count |
The for loop here counts the 1 bits by using the same mask technique used in the read_bit method of our BitVector class. And so, we read each of the 32 bits of difference and count up the 1 bits.
Did I mention that this is one of my favorite puzzles? The solution isn’t obvious, but it’s super fun. Let me break it down piece by piece.
The hero of this solution is our good pal XOR. Let’s talk about XOR a bit more.
One thing to highlight about XOR is that when we XOR two identical integers, the result will be 0. Think again about XOR being that litmus test for revealing 1 bits wherever two integers have differing bits. It emerges that if we XOR two identical integers (such as 5 and 5), XOR will produce only 0 bits. And, as you know, an integer with only 0 bits is, well, 0.
So, let’s pretend for a moment that our input array is [3, 3, 7, 7, 4, 4, 1]. As you can see, this array has two instances of 3, 7, and 4; however, there’s only one instance of 1. Let’s XOR all these numbers up.
When we XOR the two 3s, we get 0 since the 3s are identical. When we take this resulting 0 and XOR it by the 7, we’ll get some nonzero result. But it’s not going to matter because when we XOR that result by the second 7, the result will be 0 again. The same happens for the two 4s.
By the time we get up to the 1, our result will be 0. When we XOR the 0 with 1, we’ll get 1 since one of the rules of XOR is that when we XOR 0 with some other number, the result will be that other number.
It turns out that the final result of XORing all the numbers will be the very number we’re seeking—that is, the number that only appears once in the array.
Here’s the surprisingly concise solution code:
| | def single_number(array): |
| | running_total = 0 |
| | |
| | for num in array: |
| | running_total ^= num |
| | |
| | return running_total |
Now, you’re probably wondering, “Well, that works if the numbers are ordered that way, where each pair of integers appears together, and the single number is located at the end. But what if the integers aren’t sorted in any particular order?”
That’s a great question; I had it too. The answer, though, is that when you XOR a bunch of numbers together, you’ll always get the same result no matter the order of the numbers. In fancy terms, this is the commutative property. Just as the order of numbers doesn’t matter when you add them or multiply them together, the same applies to XORing.
This isn’t necessarily intuitive, but try it out for yourself and you’ll see it’s true!
So, at the end of the day, the result of XORing all the array’s numbers will be the number we’re looking for—namely, the integer that appears only once in the array. This makes for a great party trick at a nerdy event (but not too nerdy, since you don’t want everyone there to already know the solution before you show them).
Войти с помощью соц. сетей: