1. Overview
In this tutorial, we’re going to discover how we can convert a positive binary value into the negative equivalent of a signed integer. We’ll start with a binary value held as a String containing 0s and 1s, then define a series of functions to carry out the steps to convert the String into the two’s complement negative, returning a String.
2. What Is Two’s Complement?
In computer systems, the most common method used to represent a signed integer is two’s complement. In two’s complement, the left-most bit is used to denote whether the integer is positive or negative. A positive will start with a 0, and a negative will start with a 1. A positive two’s complement value looks the same as an unsigned binary integer.
It’s worth noting that since the left-most (or most significant) bit is used to denote a signed integer as either positive or negative, signed integers can only represent smaller numbers as compared to unsigned integers.
Negative two’s complement values, which start with a 1, are deciphered by taking the place value of the left-most bit as a negative number to be our starting point and then adding the place values of any subsequent bits that are set to 1 to that negative value.
For example, let’s decipher the negative two’s complement integer represented in binary as 1010. As the left-most bit has a place value of 8, and since we treat it as negative, we start with -8. Then, we can see that the bit representing the place value of two contains a 1, so we add the two to give us a total of -6. So, our binary 1010 is the two’s complement representation of -6.
3. How to Find Two’s Complement
To convert a binary number to the two’s complement negative equivalent, there are two steps:
- Flip each bit in the binary value, so that 1 becomes 0, and 0 becomes 1
- Add one to the resulting value from step 1
For example, if we have the binary value of 6 (0110) and want to convert it to the negative value (-6) in two’s complement, we need to flip every bit:
1001
Then, we add one to that:
1010
As we can see, we end up with the same result as we saw in the previous section, which we know is -6.
Now that we understand the steps involved in converting a number to a negative two’s complement, we can start writing Scala code to solve these two steps.
4. Flip the Bits
The first step we need to solve is to flip every bit in our binary sequence. Here, we’ll hold our binary as a String in the code. Since a String is just a Sequence of Chars, it allows us to call .map() directly on a String.
From there, we can match the value of each Char and return 1 for 0 and vice versa:
binaryString.map {
case '1' => '0'
case '0' => '1'
}
This simple use of .map() combined with a case match successfully flips every bit in our binary sequence and completes step 1. It’s worth noting that in this code, we assume that the String exclusively contains either 1 or 0. In the real world, this may not be the case, so a default case may be required with some error handling if any other Char is found:
binaryString.map {
case '1' => '0'
case '0' => '1'
case _ => //Some error returned here
}
5. Add One
The last step is to add one to the flipped bits from the previous section. This step is slightly more involved as we have to traverse the binary string and change the first zero we find to 1, changing any previous 1s to 0 as we go. For example, adding 1 to 0011 would be 0100.
There are a couple of ways we can solve this problem. Let’s try both and discuss the advantages and disadvantages of each approach.
5.1. Using Recursion
The first approach uses recursion, with a function that calls itself for each bit in the binary sequence. Since we need to evaluate the smallest bit first, it’s easiest to reverse the binary value we pass into the function and then reverse the result again to get it in the correct order:
addOne(bin.reverse).reverse
In our recursive function, we’ll need to provide three arguments:
- needsAdding: Boolean – A boolean that will change to false once a 0 is found and the 1 is added
- acc: String – An accumulator holding the result so far
- binString: String – This will be the rest of the bytes left to traverse from our original binary sequence
Now that we know what our arguments will be, let’s define the signature of the function:
def addOne(needsAdding: Boolean, acc: String)(binString: String): String
The most important thing when creating a recursive function is to come up with a solid base case. We exit the recursive function when the task has finished and remove the chances of an infinite loop. For our function, there are two base cases:
- When we have run out of bits in the traversal of binString
- A 0 has been found, and the 1 has successfully been added; this will be when needsAdding is false
Let’s add these base cases to our function:
def addOne(needsAdding: Boolean, acc: String)(binString: String): String = {
if (needsAdding) {
binString match
case "" => acc
} else {
acc + binString
}
}
If we’ve run out of bits to traverse, we simply return the value stored in acc. Once the 1 has been added, we know the remaining bits on binString will remain unchanged. So, we return the result of the acc plus the remaining bits left in binString.
Finally, we need to implement the bit-swapping logic:
binString match
case "" => acc
case _ => {
val (bit, tail) = binString.splitAt(1)
if (bit == "0") addOne(false, acc + '1')(tail.mkString)
else addOne(true, acc + '0')(tail.mkString)
}
Here, we get the head of binString and use an if condition to evaluate whether it is 0, in which case we replace it with 1 and then pass in needsAdding as false. Or if it’s a 1, we replace it with 0 and carry on with traversal by calling the function again with needsAdding set to true.
Let’s put all these parts together:
def addOneWithRec(bin: String): String = {
def addOne(needsAdding: Boolean, acc: String)(binString: String): String = {
if (needsAdding) {
binString match
case "" => acc
case _ => {
val (bit, tail) = binString.splitAt(1)
if (bit == "0") addOne(false, acc + '1')(tail.mkString)
else addOne(true, acc + '0')(tail.mkString)
}
} else {
acc + binString
}
}
addOne(true, "")(bin.reverse).reverse
}
This function requires a bit of effort as we have to control the traversal through the binString. However, with that additional control, we can include a base case once needsAdding is false and prevent iterating through any more than is required.
5.2. Using .foldleft()
When using recursion in Scala, we can use a .fold() as an alternative in most cases. In this case, we can also use a .foldLeft() to solve this problem. Again, we’ll start with the same initial values, of true for needsAdding and an empty String for acc.
With this approach, it’s also worthwhile to reverse binString so that the bit being evaluated first is at the start:
bin.reverse.foldLeft((true, ""))
Since we’re using a .foldLeft(), we’re unable to exit traversal like we were with recursion. So, the base case is when the .foldLeft() naturally stops after traversing all of binString. Then once needsAdding is false, our code will have to add each bit to the end of the acc:
bin.reverse
.foldLeft((true, ""))((added, bit) => {
val (needsAdding, acc) = added
(false, acc + bit)
})
Finally, let’s apply the same logic as last time to add 1 until a 0 is found:
bin.reverse
.foldLeft((true, ""))((added, bit) => {
val (needsAdding, acc) = added
if (needsAdding) {
if (bit == '0') (false, acc + '1') else (true, acc + '0')
} else {
(false, acc + bit)
}
})
._2
.reverse
As we can see, this approach requires a lot less code. However, since a .foldLeft() has to traverse the whole binString, it’s slightly less efficient as it can’t be exited once the 1 has been added.
6. Combining the Steps
To combine these two steps, we simply pass addOne() to the result of flipBits():
addOne(flipBits(bin))
This will carry out the steps in order and return the binary and a negative two’s complement binary String.
7. Conclusion
In this article, we’ve covered the steps to convert binary into negative two’s complement by flipping the bits and then adding one. We’ve also discussed how to translate these steps into logic and how to utilize the powerful functions in Scala to solve these logic problems. Finally, we explored the options to add one to a binary held in a String and learned both the benefits of having more control using recursion and the ease of using .foldLeft().
As always, the sample code used in this article is available over on GitHub.