$3.(20$ points$)$

Recall from class that BCD stands for Binary Coded Decimal. It is a representation of decimal integers by encoding each digit with a $4-$bit string. In some more advanced calculating devices, the calculations are done in binary and then they are converted to BCD in order to print the result in decimal. There is an algorithm called Double Dabble that converts binary into BCD$.$ Here is a summary of the algorithm and an example:

$$ You first initialize your binary number to the right of a divider.

$$ Shift the number to the left one bit at a time, filling in $4$ bit registers.

If at any point in the shifting, the number in one of the $4$ bit registers is greater than or equal to $5,$ add three to that register, then continue.

$$ Terminate when the entire binary number has been shifted to the left of the divider.

Consider the example with the initial binary number: $(1101011010)2858$:

$1101011010$

$1$

$11$

$101011010$

$01011010$

Initialize

Shift

Shift

Since $(1102)-65,$ we add $3.$

$+11$

$1001$

$1$

$1011010$

Shift.

Shift..

$100110$

$1101$O

Since $(1102)65,$ we add $3.$

$+11$

$101001$

$1010011$

$+11$

$11010$

$1010$

Shift.

Since $(1012)-55,$ we add $3.$

$10000$

$0111$

$010$

Since $(1112)-7>5,$ we add $3.$

Shift.

$1$

$10$

$+11$

Shift.

Shift.

$10010$

Since $(10012)-95,$ we add $3.$

$+11$

$1000$

$5$

$8$

Shift. Terminate.

$8$

$($a$)(8$ points$)$ Perform this algorithm on the binary number: $(11110101)2.$

$($b$)(6$ points$)$ If a straight binary number n is $32$ bits long, what is the maximum number of bits required for the BCD representation of n$?$

$($c$)(6$ points$)$ Why do you add $3?($Hint: every time you shift to the left, you essentially double the integer to the left of the divider. What is the result of adding $3,$ then doubling?$)$