In my previous blogs, I gave an overview of what it means to work with an 8-bit, 16-bit, 32-bit, etc., number, or binary number, and how you would solve an algorithm problem that requires a certain sized bit integer without the computer science background knowledge to help make sense of it all. This post specifically tackles what exactly it means to have a signed or unsigned binary number. It won't change much the way integers are restricted when solving algorithm sets, but it will change the range you can work with dramatically. Then I'll use the same problem solved previously but accommodated to help solve for a signed binary integer instead of one that isn't.
What Does It Mean?
The biggest difference between a signed and unsigned binary number is that the far left bit is used to denote whether or not the number has a negative sign. The rest of the bits are then used to denote the value normally.
This first bit, the sign bit, is used to denote whether it's positive (with a 0) or negative (with a 1). If you want to get technical, a sign bit of 0 denotes that the number is a non-negative, which means it can equal to the decimal zero or a positive number.
| (-/+) | 26 | 25 | 24 | 23 | 22 | 21 | 20 |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
010011012 = +7710
Note: I'm using the X2 notation for binary integers and the X10 notation for decimal integers.
Most importantly, the first bit used to denote sign means that we have one less bit to denote value. So if we have an 8-bit signed integer, the first bit tells us whether it's a negative or not, and the other seven bits will tell us what the actual number is. Because of this, we're technically working with a more limited range of numbers that can be represented; 7 bits can't store numbers as big as 8 bits could.
What's the difference?
Unsigned binary numbers
To review binary numbers, the ones and zeroes act like switches that metaphorically turn powers of 2 on, and then it's added up to create the decimal value. Normally, we'd "mark" a bit value with a one.
Example 1a:
Unsigned 01012 = 510
| 23 | 22 | 21 | 20 |
|---|---|---|---|
| 0 | 1 | 0 | 1 |
Example 2a:
Unsigned 10012 = 910
| 23 | 22 | 21 | 20 |
|---|---|---|---|
| 1 | 0 | 0 | 1 |
Signed binary numbers
Example 1b:
Signed 01012 = +510
| (-/+) | 22 | 21 | 20 |
|---|---|---|---|
| 0 | 1 | 0 | 1 |
When a signed binary number is positive or negative it's 'marked' with a 0 or 1 respectively at the first far-left bit, the sign bit. The number above doesn't change at all. It's just more explicitly a positive number.
Example 2b:
Signed 10012 = -710
| (-/+) | 22 | 21 | 20 |
|---|---|---|---|
| 1 | 0 | 0 | 1 |
But the above binary number completely changes. And we're now representing a negative!
Negative binary integers
When a binary integer is negative, the zeroes will now act as a "marker", instead of the ones. You would then calculate the negative binary number in the same way you would with a positive or unsigned integer, but using zeroes as markers to turn bit values "on" instead of ones and then adding the negative sign at the end of your calculation.
| (-/+) | 22 | 21 | 20 |
|---|---|---|---|
| 1 | 0 | 0 | 1 |
Signed 10012 = -710
Going from an unsigned binary to a signed binary integer changes your end value in a couple of different ways. The first is the more obvious change in value when the first bit is used to denote sign instead of value. You can see between example 2a and 2b above that it means if you had a one at the first bit of your 4-bit integer, you're losing a value of 23 that would've been added to your end value with an unsigned bit, but is now instead used to represent a negative. With a larger bit integer, that could be an extremely larger value that you lose the ability to represent.
Something else that isn't obvious right away is that you calculate a negative binary integer's value starting at 1, not 0. Because the decimal zero is not included in a negatively signed bit integer, we don't start counting at zero as we would when it's a positively signed bit integer.
To explain that quirk let's compare positively and negatively signed integers. Working with a 4-bit integer, if we had four bits with a value of zero, the number would equal to 0. That's the lowest value we can have. Because a non-negative signed bit means we can have a positive integer, or a 0.
| 0 | 0 | 0 | 0 | = 010 |
|---|
A 4-bit negative integer of four bits of one values (the ones now being the "off switch"), the number would not equal 0, but -1. Which makes sense, since that's the highest decimal number we can represent while still having a negative.
| 1 | 1 | 1 | 1 | = -110 |
|---|
But that means, when we're adding up our values to get our final decimal number, we start our counting from 1, not from 0.
| 2x | (-/+) | 22 | 21 | 20 | Total |
|---|---|---|---|---|---|
| bit-value | 0 | 1 | 1 | 0 | |
| 2x x bit-val = | + | 4 | 2 | 0 | = 610 |
So even if I were to perfectly flip the "switches" from the positively signed binary number above into its negative counterpart, it would not perfectly switch to its negative decimal counterpart value in the way one might expect:
| 2x | (-/+) | 22 | 21 | 20 | Total |
|---|---|---|---|---|---|
| bit-value | 1 | 0 | 0 | 1 | |
| 2x x bit-val = | - | 4 | 2 | = -710 |
Why??
Because we're adding starting with a value of 1! And we're adding up the values that are represented in our bits before adding a negative sign at the very end of our calculation.
Here's a visual comparison of the decimal and binary equivalents that show how a 0 signed bit integer is the decimal 010 or larger, while a 1 signed bit integer is decimal -110 or smaller.
Alternatively:
Another way to calculate the negative is to keep using the ones as 'markers' and use the sign bit as a marker for the value at its corresponding power of two at a negative value. This also illustrates a different way to understand what's going on in binary negative representations.
| 2x | (-/+)23 | 22 | 21 | 20 | Total |
|---|---|---|---|---|---|
| bit-value | 1 | 0 | 0 | 1 | |
| 2x x bit-val = | -8 | 0 | 0 | 1 | = -710 |
This way of calculating the decimal value might be a little easier when working with smaller decimal numbers, but then becomes a little more complicated to do some mental math when you're working with bigger decimal numbers:
| 2x | (-/+)27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | Total |
|---|---|---|---|---|---|---|---|---|---|
| bit-value | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | |
| 2x x bit-val = | -128 | 64 | 32 | 16 | 0 | 0 | 2 | 1 | = -1410 |
Thankfully, there aren't a lot of situations I can think of where you'd have to interpret between the two without a calculator handy!
Finding the max and min with signed binary numbers
The range of positive decimal numbers that can be stored in any sized bit integer is shortened by the fact that the first bit is used to denote sign. This means that, in the case of a 32-bit signed integer, we are actually working with 31 value bits instead of 32, and that last bit could have stored an exponentially bigger integer. In fact, this completely halves the range of positive integers we can work with compared to a 32-bit unsigned integer. That one extra bit would have doubled our max possible integer, and without it, we lose the ability to store as many positive integers.
On the other hand, we gain the ability to store a bunch of negative integers that we couldn't have before with an unsigned bit integer. In the end, the size of the range we work with is kept the same, but the range moves to account for being able to store both positive and negative numbers.
Let's look at a 4-bit unsigned vs signed integer. Our range might move, but the amount of integers that can be stored don't actually change.
Because of this loss of a bit, our maximum is calculated by 2bits - 1 - 1, or, if working with 32-bit integers 231 - 1.
I explained why we have to subtract the one last time, which we still have to do since we're including the zero in the range and not subtracting would cause one extra bit to be needed to store that number.
Our minimum in the range is the inverse, -2bits - 1, or, if working with 32-bit integers, -231. We don't subtract one for our minimum range because the zero is not included and we start counting from -1. This gives us that one extra negative number in our range that can be represented.
Seeing the range above might help visualize why there isn't a subtraction from the lower range while there is for the upper range. Zero is included in the green range, but not in the red range of signed bits. We start at -1 and can have the same amount of numbers represented as non-negatives.
| * | * | * | * | * | * | * | * | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| -8 | -7 | -6 | -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Here we have 8 positive integers.
| * | * | * | * | * | * | * | * | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| -8 | -7 | -6 | -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Here we have 8 positive and negative integers. But still only 8 total integers.
The problem
Going back to the problem solved in the last post, this time the solution will involve creating a restricted range for a signed integer.
Given a 32-bit signed integer, reverse digits of an integer.
We know this is a 32-bit integer with 32 zeroes and ones, the very first of which is denoting the sign.
Working with 31 bits that could represent the value of the number, the biggest positive binary integer we could have would be 31 ones after the first, sign bit of zero, which gives us a positive sign.
This means the largest decimal number we could deal with would be 231 - 1, or 2,147,483,647
The largest negative binary integer (and by largest I mean smallest?) would be 31 zeroes with the sign bit being a one, telling us it's negative.
This means the smallest decimal number we could deal with would be -231 or -2,147,483,648
The solution
const reverseInteger = (x) => {
let reversed = "";
strx = x.toString();
for(let num of strx){
reversed = num + reversed
}
reversed = parseInt(reversed, 10);
if(x<0){
reversed = reversed * -1;
}
//Setting the range!
if (reversed > Math.pow(2, 31) - 1 || reversed < Math.pow(-2, 31)) return 0;
return reversed;
};
The problem is essentially asking to make sure we don't return a number that can't be stored as a 32-bit signed integer. Here we're skipping how to actually solve this problem and focusing on the range since I've walked through the solution previously.
The line right before the return checks whether the end integer contained in reversed is within range. If reversed is greater than 231 - 1 OR less than -231, it returns 0.
If this were an unsigned 32-bit integer, there would've been a range from 0 to 232-1, or 4,294,967,295. That upper range is twice the range of 231. You can think of that missing "half" of the range that would have stored those positive numbers as being used to store your negative numbers instead. Same-sized range, just different start and endpoints in that range.
Fin!
That finishes my series on binary numbers for the average non-computer science degree holders!
This was a really fun (and frustrating) learning process. I fully expect there to be holes in my overview as there's just way too much to cover without going unnecessarily in-depth.
I want this to be a good jumping-off point for those who want to know the basics so if there's anything that wasn't clear (or I assumed you knew something that you didn't), let me know!
Happy Coding!
Resources:
Reverse Integer LeetCode Problem
Signed Binary Numbers
Decimal to Binary Converter
Signed Numbers - Watson
Rounding Algorithms 101 Redux - EETimes
Bits, Bytes, and Integers - Carnegie Mellon
Top comments (1)
thanks...