Day 03: Binary and Recursion - [Homepage](http://gddh.github.io/)
==========================
# Binary
## Base 10 Representation of Numbers
A binary representation of number is simply another way of representing number. In our usual numerical representation, base 10, we represent numbers using the digits 0-9, however we can also represent the exact same set fo numbers only using digits 0 and 1. For more intuition, let's consider counting in base 10. (The following explanation is a simplified version of the link. Read it for a complete explanation: https://betterexplained.com/articles/numbers-and-bases/ )
```
357 = 3 5 7
^ ^ ^------the one's place : 10^0 * 7
| L---------the ten's place: 10^1 * 5
-------------the hundred's place: 100 * 3 = 10 ^2 * 3
```
Let us count up starting from 0. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. We've used up all the digits! At this point to count past 9, we will need to move to the tens place and flip back to zero in the ones place, thus we get 10. A nice visualization is the odometer. After running out of digits to represent the original base, we flip back to 0 and restart, while adding one to a higher power of the base.
```
9 + 1 = 10 = 10 + 0 = 10^1 * 1 + 10^0 * 0
10 + 1 = 11 = 10 + 1 = 10^1 * 1 + 10^0 * 1
11 + 1 = 12 = 10 + 2 = 10^1 * 1 + 10^0 * 2
12 + 1 = 13 = 10 + 3 = 10^1 * 1 + 10^0 * 3
13 + 1 = 14 = 10 + 4 = 10^1 * 1 + 10^0 * 4
14 + 1 = 15 = 10 + 5 = 10^1 * 1 + 10^0 * 5
```
Notice, we can represent any number as a sum of products of the power of ten. I believe the reason why we call the places tens, hundreds, thousands, ..., is because when we take ten to some power, we get tens, hundreds, thousands, ...
```
10^(x) * d_(x) + 10^(x-1) * d_(x_1) + ... + 10^1 * d_1 + 10^0 * d_0
```
## Binary Representation of Numbers
Binary representation actually follows the same logic as the base 10 representation, except now instead of using the digits 0 - 9, we use the digits 0 and 1. As we did with base 10, let's count up.
```
0 = 2^0 * 0 ------------------------> 0
1 = 2^0 * 1 ------------------------> 1
```
At this point, we've used up all the digits. We will need to move to the "tens place" and flip back to zero in the "ones place".
```
2 = 2^1 * 1 + 2^0 * 0 -------------> 10
3 = 2^1 * 1 + 2^0 * 1 -------------> 11
```
Again flip over.
```
4 = 2^2 * 1 + 2^1 * 0 + 2^0 * 0 ----> 100
5 = 2^2 * 1 + 2^1 * 0 + 2^0 * 1 ----> 101
6 = 2^2 * 1 + 2^1 * 1 + 2^0 * 0 ----> 110
7 = 2^2 * 1 + 2^1 * 1 + 2^0 * 1 ----> 111
```
Feel free to continue to get a better understanding.
So what is ```101010``` in base 10?
```
1 0 1 0 1 0
^ ^ ^ ^ ^ ^------------ 2^0 * 0 = 0
| | | | L-------------- 2^1 * 1 = 2
| | | L---------------- 2^2 * 0 = 0
| | L------------------ 2^3 * 1 = 8
| L-------------------- 2^4 * 0 = 0
L---------------------- 2^5 * 1 = +32
-----
42
101010 in base 10 is 42
```
By now you should see that we can represent any number with binary numbers because we can essentially count in binary representation. In fact, we can even represent decimal and negative numbers! However, we can cover that on another day.
## Hexadecimal
Hexadecimal representation is the same idea, except we have base 16, rather than the base 2 in binary and the base 10.
The hexadecimal representation will use digits: ``` 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15```. You may have noticed a problem. Let's consider:
```
241 = 16^1 * 15 + 16^0 + 1
```
So, how do we represent ```241```? 151? This seems kind of odd because 15 is taking up two digits, whereas in the past, our numbers always took up 1. By having it as one digit, it made conversion easier. We could use could use some delimiter such as ```15:1``` or ```15,1```, but we might as well represent the two digit numbers with different symbols.
```
10 = A
11 = B
12 = C
13 = D
14 = E
15 = F
```
The logic described in binary and decimal will then still hold.
## How to Convert From Base 10 to Arbitrary Base
This is a very clear answer. I will be using their explanation. https://math.stackexchange.com/questions/111150/changing-a-number-between-arbitrary-bases
Let's say we wanted to convert 45 to base 3
```
x x mod 3
45 0
15 0 (integer divide x by 3)
5 2
1 1
```
We see that 45 = 1200 in base 3. Read up the last column to get the base-3 expansion you seek. Let us check.
```
1⋅3^3 + 2⋅3^2 + 0 + 0 = 27 + 18 = 45.
```
## Bit Manipulation
Let's focus on binary representation of numbers because that's what computers actually use. If we get into the very low level of computers, what's actually happening is actually a bunch of logic gates that check if there is an electric pulse going through it at the current moment. That means at any moment there are only two possibilities, True or False. We can also represent these two possibilities as 0 or 1, thus the need for binary numbers and representation.
We've already seen that binary representation is as flexible as our base 10 representation, so what's left?
For the Piscine, we must also understand some basic binary operations: &, |, >>, <<. We will also cover ~ and ^.
<table>
<tr>
<th>Operator</th>
<th>Description</th>
<th>Example</th>
</tr>
<tr>
<td>&</td>
<td>Will evaluate to 1 iff **both** operands are 1</td>
<td>011 & 001 = 001</td>
</tr>
<tr>
<td> | </td>
<td>Will evaluate to 1 if **either** operands is 1</td>
<td>011 | 001 = 011</td>
</tr>
<tr>
<td>^</td>
<td>Will evaluate to 1 iff **only 1** operand is 1</td>
<td>011 ^ 001 = 010</td>
</tr>
<tr>
<td>~</td>
<td>Will "flip" the bits</td>
<td>~01 = 10</td>
</tr>
<tr>
<td> << </td>
<td>Will shift the bits left by amount specified. Also means multiply by 2 by amount specified.</td>
<td>001 << 2 = 100</td>
</tr>
<tr>
<td>>></td>
<td>Will shift the bits right by the amount specified. Also means divide by 2 by amount specified.</td>
<td>100 >> 2 = 001</td>
</tr>
</table>
# Recursion
(Originally developed from CS61A Berkeley Course Material! I proceed to butcher their explanation. Credits go to the talented 61A staff and Prof. Denero)
A function is called **recursive** if the body of that function calls itself, either directly or indirectly.
Recursion works well when we can break down a problem into smaller instances of the same problem.
Let's consider a simplified ```void ft_putnbr(int n)``` where we are concerned with only positive base 10 integers. For example, if our input is 2018, then we will need to print 2018.
Let's consider a hypothetical scenario. If we've printed 2 already, all we need to do is print 018. If we've printed 20 already, all we need to print is 18. If we've printed 201 already, all we need to print is 8. Notice how I'm breaking down the problem of printing 2018 into subproblems, with the simplest subproblem presenting the task of printing 2, a single digit number.
## Base Case
This is our **base case**. We ask ourselves, "What is the simplest argument we could possibly get?" Well in this case, it's a single digit number, because when we get a single digit number, we just print. Let's translate that to code.
```
if (n >= 0 && n <= 9) /* If it is a single digit. */
ft_putchar(n + '0'); /* Add '0' b/c we want the char repr of n */
```
(You could argue that no number is the simplest case, but then the function isn't really doing anything. It is possible to have a base case with no number, but it doesn't really make sense for this case)
## Breaking the Problem Down
I propose that we can solve the problem by breaking it into the subproblems 2, 20, 201, and 2018 and then at each step, we print the right most digit.
Since our base case is a single digit, we have to break down all other inputs such as, 2018. We break need to somehow break it into 2, 20, 201, and 2018. We can break this down by dividing 2018 continuously. Because C uses floor division (meaning we truncate the decimal value), we can keep dividing by 10.
```
2018 / 10 = 201
201 / 10 = 20
20 / 10 = 2
2 <-- This is a base case!
```
At each subproblem, we also need to print the rightmost digit, otherwise we will end up only printing 2! In other words:
```
Base Case : 2 ---> print 2
Subproblem: 20 ---> print 0
Subproblem: 201 ---> print 1
Subproblem: 2018 ---> print 8
```
## Recursive Case
With that logic, let's proceed to the second part of recursion, the **recursive case**. We can think about the recursive case as how to break down the problem into smaller subproblems.
We need make a **recursive leap of faith**, where we simply *trust* that the function call will solve the subproblem. In our case, we trust that our function call will have already printed all previous numbers. Let's write code first and use it to get a better understanding.
```
ft_putnbr(n / 10) <-- recursive leap of faith
last_digit = n % 10; <-- To be clear this is the last digit
ft_putchar(last_digit + '0'); <-- print the last digit.
```
The implications of our leap of faith is that it will take care and print the rest of the number. For example, let's say in our current (sub)problem, n = 2018. We will pass 2018 / 10 = 201 into the recursive call and trust that the function will print 2 followed by a 0 followed by a 1. Then we all we need to do is print the last digit.
## Putting it all together
Our final function looks like this:
```
void ft_putnbr(int n)
{
if (n >= 0 && n <= 9)
ft_putchar(n + '0');
else
{
ft_putnbr(n / 10);
ft_putchar((n % 10) + '0');
}
}
```
To see clearly how it is possible to print all 4 digits, please run the above in Python tutor for C.
http://www.pythontutor.com/visualize.html#mode=edit
Don't forget the other ```ft_putchar(char c)``` and the ```main```
```
#include <unistd.h>
void ft_putchar(char c)
{
write(1, &c, 1);
}
int main(void)
{
ft_putnbr(2018);
}
```
## Multiple Recursive Cases
Now let's implement ```ft_putnbr``` so that it takes care of negative cases.
Notice that when we get a negative number, we can simply print the negative sign and multiply the negative number by a negative 1. The problem will be reduced to the problem of printing the number as explained above.
To clarify, we can deal with an input such as `-214542` by printing `-` and then doing a recursive call on `214542`.
Let's translate that to code.
```
void ft_putnbr(int n)
{
if (n >= 0 && n <= 9)
ft_putchar(n + '0');
else if (n < 0)
{
ft_putchar('-');
ft_putnbr(n * -1);
}
else
{
ft_putnbr(n / 10);
ft_putchar((n % 10) + '0');
}
}
```
Notice what we did. We figured out that our original method of breaking our problem down to subproblems is not valid for all inputs, so we changed the way to break down our problem slighlty. We are still taking our problem of printing numbers and breaking it down.
## Multiple Base Cases
We are almost done. As of now, our function will not be able to print the ```MIN_INT```, -2147483648. This is because the maximum integer that a ```signed int``` can hold is ```+2147483647```, and when we multiply -2147483648 by -1, we get 2147483648, which is more than the maximum integer can hold.
One way of taking care of this special case is to treat it as a base case.
We simply say if we get -2147483648, we will ft_putstr("-2147483648") and be done.
```
void ft_putnbr(int n)
{
if (n >= 0 && n <= 9)
ft_putchar(n + '0');
else if (n == -2147483648)
ft_putstr("-2147483648");
else if (n < 0)
{
ft_putchar('-');
ft_putnbr(n * -1);
}
else
{
ft_putnbr(n / 10);
ft_putchar((n % 10) + '0');
}
}
```
The take away is that we can have multiple base cases.
## Tree Recursion
A function that requires more than one recursive call. An example is the fibonacci function.
The Fibonnaci Sequence is characterized by the fact that every number after the first two is the sum of the two preceding ones. The Fibonnaci Sequence starts at 0 and 1.
```
int ft_fib(int n)
{
if (n == 0)
return (0);
else if (n == 1)
return (1);
else
return (ft_fib(n - 1) + ft_fib(n - 2));
}
```
----------------------------------------
-----------------------------------------
-----------------------------------------
# Problem Sets Binary and Base
1. Write a function that takes a byte, and prints it in binary WITHOUT A NEWLINE AT THE END. You are allowed to use ```write```. Your function must be declared as follows: ```void print_bits(unsigned char octet)```;
- Example, if you pass 2 to print_bits, it will print "00000010"
2. Write a function that takes a byte, reverses it, bit by bit (like the example) and returns the result. Your function must be declared as follows: ```unsigned char reverse_bits(unsigned char octet);```
- Example: 1 byte
0100 0001 ---> 1000 0010
3. Write a function that takes a byte, swaps its halves (like the example) and returns the result. Your function must be declared as follows:``` unsigned char swap_bits(unsigned char octet) ```
- Example: 1 byte
0100 | 0001 ---> 0001 | 0100
4. Convert F4E (base 16) to base 10
5. Convert 3834 (base 10) to hex (base 16)
6. Convert 10110110 (base 2) to base 10
7. Convert 124 (base 10) to base 2
8. Write ft_atoi.
9. Write a function that converts the string argument str (base N <= 16) to an integer (base 10) and returns it. The characters recognized in the input are: 0123456789abcdef. Those are, of course, to be trimmed according to the requested base. For example, base 4 recognizes "0123" and base 16 recognizes "0123456789abcdef". Uppercase letters must also be recognized: "12fdb3" is the same as "12FDB3". Minus signs ('-') are interpreted only if they are the first character of the string. Your function must be declared as follows:
- ```int ft_atoi_base(const char *str, int str_base);```
10. Write a program that takes a positive (or zero) number expressed in base 10, and displays it in base 16 (lowercase letters) followed by a newline. If the number of parameters is not 1, the program displays a newline.
- Examples:
```
$> ./print_hex "10" | cat -e
a$
$> ./print_hex "255" | cat -e
ff$
$> ./print_hex "5156454" | cat -e
4eae66$
$\> ./print_hex | cat -e
$
```
# Problem Sets Recursion
1. Write a function that sums the digits of the input. You can assume that your input will not be negative. ```int sum_digits(int n)```
2. Write a function that calculates the factorial of a given number. ```int ft_factorial(int n)```
3. Write a function that calculates the power applied to a number ```int ft_power(int n, int pow)```. You can assume that all powers will be nonnegative.
4. Write ```ft_putnbr``` without referring to the above.
5. Write ```ft_fib(n)```
6. CS61A problem: I want to go up a flight of stairs that has n steps. I can either take 1 or 2 steps each time. How many different ways can I go up this flight of stairs? Write a function stairs that solves this problem for me. Assume n is positive. Assume that you have the following main and all necessary libraries are included.
```
int main(int argc, char **argv)
{
if (argc == 2)
{
printf("%d\n", stairs(atoi(argv[1])));
}
}
```
- Examples:
```
$> ./stairs 2 | cat -e
2$
$> ./stairs 4 | cat -e
5$
$> ./stairs 1 | cat -e
1$
$\> ./stairs 3 | cat -e
3$
```
7. Write ```pgcd(n)``` using recursion. Do so by using Euclid's Algorithm.
- the smaller value if it evenly divides the larger value, or
- the greatest common divisor of the smaller value and the remainder of the larger value divided by the smaller value
- In other words, if `a` is greater than `b` and `a` is not divisible by `b`, then ```gcd(a, b) = gcd(b, a % b)```
# Solution to Binary and Bits
1. print_bits
```
#include <unistd.h>
void ft_putchar(char c)
{
write(1, &c, 1);
}
void print_bits(unsigned char octet)
{
unsigned char mask;
mask = 128;
while (mask > 0)
{
if ((mask & octet) != 0)
ft_putchar('1');
else
ft_putchar('0');
mask = mask >> 1;
}
}
```
2. reverse_bits
```
unsigned char reverse_bits(unsigned char octet)
{
unsigned char r;
unsigned byte_len;
r = 0;
byte_len = 8;
while (byte_len > 0)
{
r = (r << 1) | (octet & 1);
b >>= 1;
byte_len = byte_len - 1;
}
return (r);
}
```
3. swap_bits
```
unsigned char swap_bits(unsigned char octet)
{
unsigned char left;
unsigned char right;
left = (octet && 0x0F) << 4;
right = octet >> 4;
octet = left | right;
return (octet);
}
```
4. Convert from hex to decimal
```
F4E
E = 14 * 16^0 = 14
4 = 4 * 16^1 = 64
F = 15 * 16^2 =+3840
-----
3918
```
5. Convert decimal to hex
```
x x % 16
3834 10 = A
239 15 = F
14 14 = E
EFA
To check our work:
14 * 16^2 + 15 * 16 + 10
3584 + 240 + 10 = 3834
```
6. Convert 1011 0110 (base 2) to base 10
```
2^0 * 0 = 0
2^1 * 1 = 2
2^2 * 1 = 4
2^3 * 0 = 0
2^4 * 1 = 16
2^5 * 1 = 32
2^6 * 0 = 0
2^7 * 1 =+128
------
182
```
7. Convert 124 (base 10) to base 2
```
x x % 2
124 0
62 0
31 1
15 1
7 1
3 1
1 1
1111100
```
8. ft_atoi
```
int is_whitespace(char c)
{
return ((c > 8 && c < 14) || (c == ' '));
}
int is_nbr(char c)
{
return (c >= '0' && c <= '9');
}
int convert_num(char c)
{
return (c - '0');
}
int ft_atoi(char *str)
{
int i;
int neg;
int total;
i = 0;
neg = 1;
total = 0;
while (str[i] != '\0' && is_whitespace(str[i]))
i = i + 1;
if (str[i] == '+' || str[i] == '-')
{
if (str[i] == '-')
neg = -1;
i = i + 1;
}
while (str[i] != '\0' && is_nbr(str[i]))
{
total = total * 10 + convert_num(str[i]);
i = i + 1;
}
return (total * neg);
}
```
9. ft_atoi_base
```
int convert_num(char c, int str_base)
{
if (c >= '0' && c <= '9')
return c - '0';
else if (c >= 'a' && c <= 'f')
return c - 'a' + 10;
else if (c >= 'A' && c <= 'F')
return c - 'A' + 10;
else
return -1;
}
int is_valid_num(char c, int str_base)
{
int n;
n = convert_num(c, str_base);
if (n != -1 && n < str_base)
return 1;
return 0;
}
int is_whitespace(char c)
{
return ((c > 8 && c < 14) || c == ' ');
}
int ft_atoi_base(const char *str, int str_base)
{
int i;
int neg;
int total;
i = 0;
neg = 1;
total = 0;
while (str[i] != '\0' && is_whitespace(str[i]))
i = i + 1;
if (str[i] == '+' || str[i] == '-')
{
if (str[i] == '-')
neg = -1;
i = i + 1;
}
while (str[i] != '\0' && is_valid_num(str[i], str_base))
{
total = total * str_base + convert_num(str[i], str_base);
i = i + 1;
}
return (neg * total);
}
```
10. print_hex
```
#include <unistd.h>
void ft_putchar(char c)
{
write(1, &c, 1);
}
int is_valid_num(char c)
{
return (c >= '0' && c <= '9');
}
int convert_num(char c)
{
return (c - '0');
}
int is_whitespace(char c)
{
return ((c > 8 && c < 14) || c == ' ');
}
int ft_atoi(char *str)
{
int i;
int neg;
int total;
i = 0;
neg = 1;
total = 0;
while (is_whitespace(str[i]) && str[i] != '\0')
i = i + 1;
if (str[i] == '-' || str[i] == '+')
{
if (str[i] == '-')
neg = -1;
i = i + 1;
}
while(str[i] != '\0' && is_valid_num(str[i]))
{
total = total * 10 + convert_num(str[i]);
i = i + 1;
}
return (total * neg);
}
void print_hex(long n)
{
if (n >= 0 && n <= 9)
ft_putchar(n + '0');
else if (n >= 10 && n <=15)
ft_putchar(n - 10 + 'a');
else if (n < 0)
{
ft_putchar('-');
print_hex(n * -1);
}
else
{
print_hex(n / 16);
print_hex(n % 16);
}
}
```
# Solution to Recursion
1.sumdigits
```
int sum_digits(int n)
{
if (n >= 0 && n <= 9)
return (n);
else
return (sum_digits(n / 10) + n % 10);
}
```
2. ft_factorial
```
int ft_factorial(int n)
{
if (n == 0)
return 1;
return n * ft_factorial(n - 1);
}
```
3. ft_power.
```
int ft_pow(int n, int pow)
{
if (pow == 0)
return 1;
else if (pow % 2 == 0)
return ft_pow(n * n, pow / 2);
else
return ft_pow(n, pow - 1) * n;
}
```
4. ft_put
```
void ft_putnbr(int n)
{
if (n >= 0 && n <= 9)
ft_putchar(n + '0');
else if (n == -2147483648)
ft_putstr("-2147483648");
else if (n < 0)
{
ft_putchar('-');
ft_putnbr(n * -1);
}
else
{
ft_putnbr(n / 10);
ft_putchar((n % 10) + '0');
}
}
```
5. ft_fib
```
int ft_fib(int n)
{
if (n == 0)
return (0);
else if (n == 1)
return (1);
else
return (ft_fib(n - 1) + ft_fib(n - 2));
}
```
6.stairs.
```
#include <stdlib.h>
#include <stdio.h>
int stairs(int n)
{
if (n <= 0)
return (0);
else if (n == 1 || n == 2)
return (n);
else
return (stairs(n - 1) + stairs(n - 2));
}
int main(int argc, char **argv)
{
if (argc == 2)
{
printf("%d\n", stairs(atoi(argv[1])));
}
}
```
7. pgcd
```
void swap(int *v1, int *v2)
{
int tmp;
tmp = *v1;
*v1 = *v2;
*v2 = tmp;
}
int gcd_recursive(int v1, int v2)
{
if (v2 < v1)
swap(&v1, &v2);
if (v2 % v1 == 0)
return v1;
else
return gcd_recursive(v1, v2 % v1);
}
```
Sign in with Wallet
Connect another wallet