0
$\begingroup$

In binary the carry/borrow is 2, in hex the carry is 16. What's the reason for this?

New contributor
Zeeshan is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
0
$\begingroup$

Background

Writing a number in base $r$ means to write it in the form

$$a_0+a_1r+a_2r^2+\ldots+a_nr^n$$

where $0\leq a_i< r$, for all $i=0,1,\ldots,n$. The positional notation that we use consists in just writing the digits $a_i$ from right to left

$$(a_na_{n-1}\ldots a_2a_1a_0)_r$$

Some people write parentheses and maybe the radix as a subscript. Some people write a bar over the digits, and in the decimal positional system, which is the most popular, we just write the digits.

You can think of the digits as buckets that can only be filled up to the value $r-1$.

The carry actually depends on the position of the digit, only that when you compute you imagine that it is the degree zero position, the units. Actually, when you are inside algorithms like adding or converting numbers from one radix to another in each iteration you have already divided enough by $r$ such that the digit that you are treating has become the degree zero position or you are treating it as such.

The carry at the $k$-th position

For example, suppose that you are looking at position $k$ and the digits at that position and the one that follows are

$$a_kr^k+a_{k+1}r^{k+1}$$

You can divide by $r^k$ to get $a_k+a_{k+1}r$, which implicitly is what happened if we just write the two digits $(a_ka_{k+1})_r$.

Now, the maximum carry will happen when $a_k$ is as full as it can be and we add to it the maximum digit that we can add. This is $a_k=r-1$ and we add $r-1$. Then we get

$$\begin{align} (a_k+a_{k+1}r)+(r-1)&=(r-1)+a_{k+1}r+(r-1)\\ &=(r-2)+\mathbf{r}+a_{k+1}r\\ &=(r-2)+(a_{k+1}+1)r \end{align}$$

As you can see, it is $\mathbf{r}$ the amount that we have to move out of the $k$-th position to re-write the number as a sum of powers of $r$ in which the coefficients are all between $0$ and $r-1$. Well, it is really $r\cdot r^k$, because we divided by $r^k$. In terms of the contribution to the next ($k+1$-th) digit the carry contributes $1$, when carry over happens. Otherwise it contributes $0$ to the next digit.

Potentially, $a_{k+1}+1$ is larger than $r-1$, so $(a_{k+1}+1)r$ will have to spit out an $r^2$ (actually $r^2\cdot r^k$), but well that's the carry generated by the $(k+1)$-th position.

| cite | improve this answer | |
$\endgroup$

Your Answer

Zeeshan is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.