---
tags: fall 2018 cs61b
---
# Bits Notes
[TOC]
## Introduction
1, 100, 15, 3000. These are numbers that we use in everyday life and as wonderful as they are, they are not portrayed in the most efficient way that can be used by computers. This is where binary numbers come in.

The numbers we use everyday are called **decimals** (despite not fitting the conventional definition of a decimal). If we break them down into digits, we realize that every single number is just a **combination of 10 digits**: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. This is why we can refer to decimals as being in **base 10**.

**Binary numbers**, on the other hand, are in **base 2**, meaning they only consist of **only 2 digits**: 0 and 1. Similar to how we can refer to **digits in decimals**, we can refer to **bits in binary numbers**.

## Intuition
To build up some intution about binary numbers, let's look at the following conversions from decimal to binary. Before we go into the details, a quick note about binary numbers.

**How do we portray 0 and 1 in binary?**
Since the digits 0 and 1 already exist in binary, we can simply use 0 and 1 to represent them!

| Decimals | Binary Numbers |
|:------ |:----------- |
| 0 | 0 |
| 1 | 1 |

**Now, how do we portray 2 in binary?**
Think about how we have the **number 10**. In base 10, we're able to have 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 be represented by a single digit. However, once we get to 10, we have to use two digits. What happened? Well, we decided to consider one more digit to the left to represent more numbers. We can apply the same principle to binary numbers by flipping the bit to the left!

| Decimals | Binary Numbers |
|:------ |:----------- |
| 0 | 0 |
| 1 | 1 |
| 2 | 10 |

**What about 3?**
Well, one thing we can notice with 2-bit binary numbers is that we can represent 2 more binary numbers than with a 1-bit binary number. We simply have to flip the rightmost bit to get 3!

| Decimals | Binary Numbers |
|:------ |:----------- |
| 0 | 0 |
| 1 | 1 |
| 2 | 10 |
| 3 | 11 |

Try filling the rest of the table up to 8 by following the same principle!

**Finding a Pattern**
We have our completed conversion table below from 0 to 8.
| Decimals | Binary Numbers |
|------: |-----------: |
| 0 | 0 |
| 1 | 1 |
| 2 | 10 |
| 3 | 11 |
| 4 | 100 |
| 5 | 101 |
| 6 | 110 |
| 7 | 111 |
| 8 | 1000 |

Let's take a close look at the decimal and binary number conversions with **only leading 1's**. What do you notice about the decimals?

| Decimals | Binary Numbers |
|------: |-----------: |
| 1 = $2^0$ | 1 |
| 2 = $2^1$| 10 |
| 4 = $2^2$ | 100 |
| 8 = $2^3$| 1000 |

The decimals are all **powers of 2**! Knowing this, what would the corresponding binary number for $2^4$ be?

The answer is 10000. The takeaway is that each bit in a binary number represents some power of 2. As we increase the number of bits in our binary number, the power of 2 also increases (i.e. the rightmost bit always represents $2^0$ and the leftmost bit represents $2^{n-1}$ with $n =$ number of bits).

**Now, what happens if we try to add up all of the binary numbers in the table above?** We get the binary number: 1111, which is equivalent to the decimal number 15, which comes from $2^0 + 2^ 1 + 2^2 + 2^3 = 1 + 2 + 4 +8 = 15$.


## Decimal to Binary Conversion
To convert a **decimal to a binary number**, we do the following steps:
1. Find the largest power of 2 that is equivalent or less than the decimal we are trying to convert and subtract it from the decimal.
2. Mark a 1 in the corresponding bit to that power of 2.
3. Repeat until the original decimal is reduced down to 0.

**Let's convert 10 to a binary number.**

The largest power of 2 is 8. We subtract it from 10 and get 2. We mark a 1 in the bit representing $2^3$.

| $2^3$ | $2^2$ | $2^1$ | $2^0$ |
|------: |-----------: | ------: |-----------: |
| 1 | 0 | 0 | 0 |

Now, we look at 2 and notice that the largest power of 2 is 2. We subtract and get 0. Then, we mark a 1 in the bit representing $2^1$. We don't repeat the steps because we have reached 0.

| $2^3$ | $2^2$ | $2^1$ | $2^0$ |
|------: |-----------: | ------: |-----------: |
| 1 | 0 | 1 | 0 |

**Our final answer is: 1010**

**Sanity check:** We can quickly check by converting from binary to decimal. We note that there are 1's in the 1st and 3rd bit (from the right), so we add $2^1 + 2^3 = 2 + 8 = 10$.

## Two's Complement
So far, we've discussed positive numbers.

Now, how do we represent negative numbers? We use **two's complement**, another way of portraying binary numbers.

There are two interesting things about two's complement:
1. The **leftmost bit** becomes a **signed bit**, which serves as an indicator of whether the binary number is representing a negative or positive number. **Positive numbers start with a 0 and negative numbers start with a 1.** It does not count towards the calculation of the decimal number anymore. It **only** serves the purpose of being a sign indicator! For example, 1010 normally represents the decimal 10. In two's complement, 1010 represents the negative decimal -6.
2. The range of an $n$ bit binary number becomes limited. Originally, an $n$ bit number represented integers in the range $[0, 2^{n-1}]$. Due to the signed bit, the range is now $[-2^{n-1}, 2^{n-1}-1]$. For example, consider a 4-bit binary number. 1000 no longer represents 8. It represents -8. It is also impossible to portray 8 in terms of 4 bits now. In two's complement, 8 is 01000 (it takes 5 bits because the leftmost bit is the signed bit).

### Positive Decimal/Binary to Negative Binary Counterpart
Suppose we know 2 is 010 in binary form. How do we get -2 in binary form by knowing 010?

Two steps: **Invert all the bits in the binary number and add 1 to the binary number.**

Following the instructions above, we flip 010 to 101. Then, we add 1 to 101 and get 110. **So, -2 is 110 in binary form.**

### Negative decimals to Binary
Now we start at -2. This time, it's difficult to find the binary number off the bat. Instead, what we do is look at the binary number of -2's positive counterpart, 2.

We know the binary number of 2 is 101. Therefore, all we have to do is apply the conversion method from above and obtain 110.

### Negative Binary to Decimal
Suppose we start with 110 and want to convert it to a decimal number. It's not easy to tell which negative number this corresponds to, so we start by **converting it to the binary number of its positive counterpart**.

Therefore, we invert all the bits to get 001 and add 1 to get 010. We know this is 2. Since we're working with the negative counterpart, **the binary number must be -2!**

## Bitwise Operators
**& (bitwise and):** takes 2 binary numbers and performs the logical AND operation on bits in the same position.

Example: 2 & 3 = 010 & 011 = 010 = 2

**| (bitwise or):** takes 2 binary numbers and performs the logical OR operation on bits in the same position.

Example: 2 | 3 = 010 | 011 = 011 = 3

**^ (bitwise xor):** takes 2 binary numbers and performs the logical XOR operation on bits in the same position. XOR stands for **exclusive or** and works the same way as OR, except if the two booleans are the same, it returns 0. (1 ^ 1 = 0 and 0 ^ 0 = 0).

Example: 2 ^ 3 = 010 ^ 011 = 001 = 1

**~ (bitwise not):** flips the bit

Example: ~1 = 0, ~0 = 1

### Shifts
**N << x (left shift)**: shift all bits left x places, adding x 0’s from the right. For integers, it's equivalent to N * 2x.

**N >> x (arithmetic right)**: shift all bits right x places, adding the leading bit from the left. **This preserves the sign!** For integers, equivalent to $\lfloor \frac{N}{2x} \rfloor$ (rounded down)

**N >>> b (logical right)**: shift all bits right b places, adding 0 from the left

## Bit Twiddling Resources
### Bit Masking
Bit masking is the idea of using data in a bitwise operation just to invert certain bits or check what value they are. For example, we can use bit masking to obtain the $i$th bit of a number $N$ with N & (1 << i). The (1 << i) is a bit mask.

[Bit Manipulation Visualizer](https://visualgo.net/en/bitmask)

[BitwiseCMD](http://bitwisecmd.com/)

More bit twiddling tricks [here](https://stackoverflow.com/questions/1533131/what-useful-bitwise-operator-code-tricks-should-a-developer-know-about).