What is Binary?
The binary numeral system is a fundamental way to represent numbers in mathematics, computer science, and digital systems. The positional notation of binary digits, or bits, is base-2 notation, and are typically expressed using 0's and 1's. In a hardware sense, because of its simplicity (on or off), binary is used in computer processors and the rudimentary principle when it comes to computer logic. Binary is a contrast to the more human base-10 decimal system (deci- meaning "ten" while bi- meaning "two"!!) in the way that it might not be as intuitive to perform mathematical operations, much less simply representing numbers. All of this we will discuss!
Decimal and Binary Representations
Below is an example of how the decimal system represents the number 128.
Even more clearly, these digits can be represented as a sum, where n is the representative digit:
$\sum\limits_{i=0}^8 n\cdot10^{i} = 8\cdot10^0 + 2\cdot10^1 + 1\cdot10^2 + 2\cdot10^3 + 0\cdot10^4+0\cdot10^5+0\cdot10^6+0\cdot10^7+0\cdot10^8$
For simplicity's sake, I will represent binary numbers
as bytes, or more basically, I will write eight bits each time we are
representing a number, and then one. Now using the above understanding, let's take a look at binary digits and how the same exact number, 128, is represented.
Okay, so this representation seems odd at first, but when seen the way we thought about the decimal system, it is rather simple. There are zeros everywhere but the column for $2^7$. It also happens to be the case that $2^7 = 128$. From the least significant to the most significant bit, each column is weighted at incrementing magnitudes of 2. Since it is base-2, only one digit of exactly two numbers can be held in any place, those being $\{0,1\}$. There is no conventional naming of these columns, contrasting to the decimal system. One could in theory use "ones", "twos", "fours", "eights"... and so on but instead, it is encouraged that you simply memorize your exponents of 2.
This representation can also be described as a sum, very similarly to decimal, where n is the representative digit:
$\sum\limits_{i=0}^8 n\cdot2^{i} = 0\cdot2^0 + 0\cdot2^1 + 0\cdot2^2
+ 0\cdot2^3 + 0\cdot2^4+0\cdot2^5+0\cdot2^6+1\cdot2^7+0\cdot2^8$
Converting from Decimal to Binary
Now that you understand how numbers are represented in these two numeral systems, it is also important to realize how to convert between them. Well, converting from binary to decimal is easy, since the very definition of "reading" a binary number means converting it to decimal. But what about the other way around? The general strategy is to break the number up into small additions of powers of two. For example, let's see how to break up an arbitrary number like 269:
The breakup in decimal would be intuitive:
$269= 200+ 60 + 9$
$269= 200+ 60 + 9$
But let's think of what powers of two work:
$269= 256+ 8+ 4 + 1$
$269= 256+ 8+ 4 + 1$
After you have found the breakup, you now are ready to plop these 0's and 1's into the correct slots. We know that we need to keep them in order, otherwise the 1's could represent something other that what we expect. The next thing you should do after you have found the breakup is to create the spaces for each power of 2.
| 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|
| $2^8$ | $2^7$ | $2^6$ | $2^5$ | $2^4$ | $2^3$ | $2^2$ | $2^1$ | $2^0$ |
| 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
So, we have found that $269_{10}=100001101_2$. This is also why it's important to know your powers of two. Of course, online converters and even built in methods in programming languages (like Integer.toBinaryString(int) in Java) make life simpler, but just like mathematics, a fundamental understanding is useful for implementation of this critical thinking in the real world.
Bitwise Operations
In many programming languages, bitwise and bit shift operators are useful in manipulating binary numerals at a bit-by-bit level. Because of its primitive nature (you're literally talking computer), the calculations are rather fast and can be directly supported by the processor, and can take up less power due to the shorter instruction set. In older processors, bitwise operations are a much lighter load and can even be several times faster than using unary operators, like $+$, $-$, $*$, or $/$. Though less significant in today's much more advanced processor architecture, it is relevant in describing binary because it's cool and again, it's important to fundamentally understand what is going on under the hood.
We will discuss simple bitwise operations in two languages, C++ and Java, as they use similar syntax. It is possible to create literal binary values in these languages by preceding the assignment value (in binary) by 0b. Below is a table of the manipulation operators, ripped straight off of learncpp.com. We will discuss what these mean, as well as show some examples:
Representing binary in a few bits important to understand conceptually, because it is actually not as simple in programming languages. The examples shown above use 9 bits, and the ones below will not use more than just a few.. When referring to integers and other primitive data types in programming languages, they take up more than just a few bits. An integer holds 32 bits of data, meaning 32 binary digits. So, if an integer is set to 1 in C++, it actually is set to 00000000000000000000000000000001, with all of the preceding 0's, and the first bit reading left to right represents the sign (0 for positive, 1 for negative). The remaining 31 bits are used to represent the number in the way we have learned. Keep this in mind when the coding examples are shown.
bitwise NOT (compliment)
In this operation, when given a binary value, its compliment is the result, meaning any bit that is 0 is changed to a 1, and any bit that is 1 is changed to a 0. There is no third case.
In a programming sense, referring back to 32 bits of data described above, when you perform the bitwise NOT, every single bit is complimented. The result is what's called a two's compliment minus one. The formula for this is given as $NOT x = -x -1$. Below is sample code for this operation.
bitwise AND (logical conjunction)
In this operation, when given two binary values, it checks each corresponding pair of bits, and ensures that they are both 1. Both bits musts be 1 for the result to be 1, otherwise it is 0. This is essentially multiplying corresponding bits.
We will discuss simple bitwise operations in two languages, C++ and Java, as they use similar syntax. It is possible to create literal binary values in these languages by preceding the assignment value (in binary) by 0b. Below is a table of the manipulation operators, ripped straight off of learncpp.com. We will discuss what these mean, as well as show some examples:
Representing binary in a few bits important to understand conceptually, because it is actually not as simple in programming languages. The examples shown above use 9 bits, and the ones below will not use more than just a few.. When referring to integers and other primitive data types in programming languages, they take up more than just a few bits. An integer holds 32 bits of data, meaning 32 binary digits. So, if an integer is set to 1 in C++, it actually is set to 00000000000000000000000000000001, with all of the preceding 0's, and the first bit reading left to right represents the sign (0 for positive, 1 for negative). The remaining 31 bits are used to represent the number in the way we have learned. Keep this in mind when the coding examples are shown.
bitwise NOT (compliment)
In this operation, when given a binary value, its compliment is the result, meaning any bit that is 0 is changed to a 1, and any bit that is 1 is changed to a 0. There is no third case.
/* * NOT 1101 (decimal 13) = * 0010 (decimal 2) */
In a programming sense, referring back to 32 bits of data described above, when you perform the bitwise NOT, every single bit is complimented. The result is what's called a two's compliment minus one. The formula for this is given as $NOT x = -x -1$. Below is sample code for this operation.
int x = 1; // 00000000000000000000000000000001 (decimal 1) int y = ~x; // 11111111111111111111111111111110 cout << y; //prints -2
bitwise AND (logical conjunction)
In this operation, when given two binary values, it checks each corresponding pair of bits, and ensures that they are both 1. Both bits musts be 1 for the result to be 1, otherwise it is 0. This is essentially multiplying corresponding bits.
/* * 0110 (decimal 6) * AND 0010 (decimal 2) * 0010 (decimal 4) */
Using the above as an example, notice that $0\cdot0=0$, $0\cdot1=0$, and $1\cdot1=1$. Although obvious, it is important to keep the bits in the correct order. This operation is especially interesting when it comes to checking for the parity of a number (whether it is even or odd). Notice that the least significant bit has a weight of 1, or $2^0$. Every other bit is an even number, because it is a power of two, hence it is implied that it is also divisible by two. If the $2^0$ column is filled, it means that an even number has one added to it, creating an odd number. The AND operation can check for the parity of numbers by: $x$ $AND$ $1$. If 0 is found, the number is even, otherwise, 1 is found, and the number is odd. Below is an example.
/* * 0110 (decimal 6) * AND 0001 (decimal 1) * 0000 (decimal 0) */ int x = 5; // 00000000000000000000000000000011 (decimal 5) int y = x & 1; // 00000000000000000000000000000001 (decimal 1) cout << y; // prints 1, so x is odd
bitwise OR (logical disjunction)
In this operation, when given two binary values, it checks each corresponding pair of bits, and checks to see if one or the other is 1. If either one or both bits are 1, then the resulting bit will be 1. If both are 0, then the resulting bit is 0. It is logically inclusive, which refers to the property where it does not care if one or both are filled, as long as one of the bits is filled. This is very similar to addition, but not quite, as $1+1=1$ with the aforementioned logic.
/* * 1001 (decimal 9) * OR 0011 (decimal 3) * 1011 (decimal 11) */ int x = 9; //00000000000000000000000000001001 (decimal 9) int y = x | 3; //00000000000000000000000000000011 (decimal 3) cout << y; // = 00000000000000000000000000001011
bitwise XOR (exclusive OR)
In this operation, a similar behavior is exhibited as in the bitwise OR, but instead, XOR is logically exclusive. This means that the resulting corresponding bit will be 1 if and only if one of the corresponding pair of bits is 1... the other must be 0. If both bits are 0, then the resulting bit is also 0. XOR essentially "toggles" bits - any bit that is "on" will be turned "off" and vice versa.
/* * 1111 (decimal 15) * XOR 1010 (decimal 10) * 0101 (decimal 5) */ int x = 15; //00000000000000000000000000001111 (decimal 15) int y = x ^ 10; //00000000000000000000000000001010 (decimal 10) cout << y; // = 00000000000000000000000000000101
Bit Shifts: C++ and Java
The two remaining operators that have not been shown are the bit shift operators. These are very straightforward, but have proven useful when it comes to efficient calculations. When shifting bits, one essentially takes the binary representation, and moves it over by the given number of places in the given direction. The bit shift operators for left and right are << and >>, respectively. On the left side of the operand, the number to be shifted is placed, and on the right side of the operand, the number of places to be shifted is placed. The syntax is as follows: a = b >> 3; where this is saying assign to a the value of b when it is shifted 3 bits to the right.
When reaching the limits, or ends, the digits are destroyed if moved "past". This means that when shifting to the right, the $2^0$ column will always be destroyed if the argument is greater than 0. For integers, the $2^{32}$ column is the "limit", so any shift to the left will destroy that value. In the above example, we are shifting to the right by 1. We take 6 and shift it to the right by 1 bit, resulting in 3. Shifting to the right by one is especially interesting, because it is essentially dividing by 2. Similarly, shifting a value left by one is equivalent to multiplying by 2. Go ahead, try it!
Resources
https://www.youtube.com/watch?v=UvI-AMAtrvE
/*
* >>1 0110 (decimal 6)
* >>>>
* 0011 (decimal 3)
*/
int x = 6; //00000000000000000000000000000110 (decimal 6)
int y = x >> 1; //00000000000000000000000000000011 (decimal 3)
cout << y; // = 3
When reaching the limits, or ends, the digits are destroyed if moved "past". This means that when shifting to the right, the $2^0$ column will always be destroyed if the argument is greater than 0. For integers, the $2^{32}$ column is the "limit", so any shift to the left will destroy that value. In the above example, we are shifting to the right by 1. We take 6 and shift it to the right by 1 bit, resulting in 3. Shifting to the right by one is especially interesting, because it is essentially dividing by 2. Similarly, shifting a value left by one is equivalent to multiplying by 2. Go ahead, try it!
Resources
https://www.youtube.com/watch?v=UvI-AMAtrvE
