Bitwise Operators Part 2: Binary and Two’s Complement

Check here for Part 1, a quick introduction to numeric bases.

 Everything is a power of two

In this article, we’ll explore deeper into base 2, or binary, and prepare us for the groundworks of bitwise operations. Let’s start by counting to 10 in binary.

decimal binary decimal binary
1 0001 6 0110
2 0010 7 0111
3 0011 8 1000
4 0100 9 1001
5 0101 10 1010

In binary, each digit is no longer calculated in powers of ten. Instead, we have to think of each digit as a different power of two. Let’s see take a look at an example: 101 in decimal is 1*10^2 + 0*10^1 + 1*10^0. In binary, 101 is 1*2^2 + 0*2^1 + 1*2^0 = 5. It’s not important to be able to count in binary. As long as you understand the relationship between decimal and binary integers, we’ll be able to continue onward with bitwise operators.

 n-bit integers

When we say n-bit, what exactly do we mean by that? In addition to numeric values, we can also think of each digit in a binary number as a single slot of memory, or bit. Then, a 8-bit integer might look something like this 00100110. We can image it having 8 slots and a total of 28 different combination of values. Notice that so far, we’ve been using a 4-bit integer. 4-bit unsigned integers can have a maximum value of 15, or 1111. An n-bit unsigned integer may store up any numeric value from 0 to 2n - 1. But what happens when we want to store negative integers in binary? There’s a couple of different way we might do so, but the most common method is to use Two’s Complement.

Notice above I had mentioned the word unsigned. It just means that this integer holds zero and positive numbers. Signed means this integer can also hold negative values. How, then, do we store negative values in a signed integer? Basically, in adding up the values, the first and largest bit of the binary will be negative, and the rest will still be positive. This way, for the any binary number of length n, we can represent values from -2n-1 to 2n-1 - 1. Let’s see all the numeric values a 4-bit signed integers can represent.

decimal binary decimal binary
0 0000 -1 1111
1 0001 -2 1110
2 0010 -3 1101
3 0011 -4 1100
4 0100 -5 1011
5 0101 -6 1010
6 0110 -7 1001
7 0111 -8 1000

Why is binary so important to understand? As you may know, computers store only 1’s and 0’s, or ON’s and OFF’s, in their flip flops and capacitors. Understanding how our computer sees decimals can aid us in implementing the best version of our algorithms, and understanding binary is the first step in mastering boolean logic.

 
17
Kudos
 
17
Kudos

Now read this

Javascript Floating Point (im)Precision and Solution

In an exercise to re-implement Javascript’s parseFloat(), I came across a common gotcha. Go ahead, try it yourself: var pointThree = 0.1 + 0.2; console.log(pointThree === 0.3); No, your console isn’t broken. 0.1 + 0.2 ==... Continue →