Being able to whiteboard a solution to an algorithm problem is still a prevalent gate-keeping strategy for a lot of tech companies, and knowing how to solve them is crucial to getting that job you want.
But for those like me who didn't go through a traditional computer-science or technical degree route, there might be some gaps in knowledge that make solving some of those problems a real struggle.
Binary and 'x'-bit integers is one of those struggles for me. Or, it was. Hopefully, I can give an overview explanation that will help others understand what they are and why they matter.
What does it all mean?
First of all, when you see 'bits' or 'binary,' they're essentially talking about the same thing. 'Bit' is short for 'binary digit.' Bits are the smallest unit of data in a computer and represent a single binary value: a 1 or 0. So that long string of zeroes and ones you see? That's binary. And every single one (or zero) is a binary digit or bit.
So what's a binary integer? It's the binary representation of a decimal integer. And what's a decimal integer, I hear you shouting? Don't worry, it's simply the technical term for the everyday integers we work with. Decimal numbers are base-10 (base_{10}) numbers, meaning they're represented in chunks of ten with numbers 0 through 9. Binary numbers, on the other hand, are base-2 (base_{2}) numbers, represented with 0 and 1.
So taking all that information together:
Decimal_{10} Number | Binary_{2} Number |
---|---|
14 | 1100 |
125 | 1111101 |
2 | 10 |
Most computers support integers that are 8, 16, 32, or 64 bits. (Notice that they're all 2 at different exponentials: 2^{3}, 2^{4}, 2^{5}, and 2^{6}, respectively.) If someone says that only 32-bit integers are supported, it means that only integers that can be represented with 32 individual bits (32 zeroes and ones) can be used.
But how do you know what numbers are what bits?
Translating binary numbers
Each zero and one in a binary integer represents a 2 at exponential powers. Starting from right to left, it starts with 2^{0} then continues with 2^{1}, then 2^{2}, 2^{3}, and so on. It could go on forever but let's look at only 8 bits for now. It'll look like this:
2^{7} | 2^{6} | 2^{5} | 2^{4} | 2^{3} | 2^{2} | 2^{1} | 2^{0} |
---|
But because we'll be dealing with math soon let's simplify it to:
128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
---|
From binary to decimal
Say we have a binary number of 1100010 that we want to translate to a decimal number. We're going to plug in the ones and zeroes starting from the far right.
128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
---|---|---|---|---|---|---|---|
0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
Technically there is a zero in the far left, but, like with decimals, you only really care about that first not-nothing value, which is the 1 at the 64 position.
Here we'll be doing math by multiplying each bit value with its corresponding 2 exponential then adding it all together.
2^{x} | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | Total |
---|---|---|---|---|---|---|---|---|---|
bit-value | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | |
2^{x} x bit-val = | 0 | 64 | 32 | 0 | 0 | 0 | 2 | 0 | 98 |
The number's 98!
From decimal to binary
There are a few different ways of doing the math for this one but the one that feels easiest for me is a check-and-subtract strategy.
Say we have a decimal integer (X_{10}) of 112 to translate into a binary integer (X_{2}). Since we know we're working with 8-bit integers (or smaller), we can start from the left and see if we can subtract by the 2^{x} exponential without getting negative. If you can, that's a bit value of one.
X_{10} remainder | 112 | 112 | 48 | 16 | 0 | 0 | 0 | 0 |
---|---|---|---|---|---|---|---|---|
2^{x} | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
X_{10} - 2^{x} = | -neg | 48 | 16 | 0 | - | - | - | - |
bit-value | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Your binary integer is 1110000!
If you want to play around and try to translate between binary and decimal integers, this nifty calculator helps!
Why does it matter?
It's important to get a basic understanding of bits because they are the basis for all data on a computer. All data takes up storage space but using less space when programming is always ideal.
When you're dealing with integers, you want to make sure you have enough space to store any integers you're working with. At the same time, you want to make sure you're not using more space than you need. Efficiency!
If you're working with integers that are never going to go past 100, you won't need anything larger than an 8-bit storage space.
When solving algorithm problems, it's good to know what the time and space complexities are of the algorithm. When you know that, you'll know how fast or slow your program might run and how much space it will need to run.
Because of this, you'll come across problems where you'll have to take into account space restrictions, which might mean you'll want to restrict the bit-size of your integers.
This only really scratches the surface of binary integers. But for those without any background knowledge, this is a good start. To account for space and the bit size of integers when solving algorithms, you'll have to go a little deeper. But with this in your pocket, it should make it a little easier to understand.
I go deeper into bit integers in my next blog: x-Bit Integers: Solving With A Range
Discussion