8
$\begingroup$

So I’m currently working on something and I have converted all decimal digits 0-9 into binary. But now I want to take say 6 in binary and increase its order of magnitude by base 10 (turning 6 into 60) without converting back to base 10. Is this possible and if so is there a way to do it with any number, X --> X0 ?

EDIT 1: sorry the first part of the question was super vague and I forgot to mention I’m trying to do this with logic gates.

$\endgroup$
  • $\begingroup$ Do you know how multiplication circuits work? $\endgroup$ – rus9384 Aug 31 '17 at 16:51
  • 2
    $\begingroup$ Of course it's possible -- CPUs can do all kinds of arithmetic, so why not this? It won't be as easy as adding a trailing 0; that's called a left shift in CPU lingo, which in binary clearly multiplies with (powers of) two. $\endgroup$ – Raphael Aug 31 '17 at 16:55
  • $\begingroup$ No I don't please explain $\endgroup$ – user76675 Aug 31 '17 at 16:56
  • 7
    $\begingroup$ It would be weird if most of us happened to have the number of fingers that was the only(?) base in which there was a multiplication algorithm. (Or would this be an amazing evolutionary advantage?) $\endgroup$ – PJTraill Aug 31 '17 at 19:50
  • 1
    $\begingroup$ @rus9384: Sorry, my comment was meant to insinuate ironically what you state explicitly. $\endgroup$ – PJTraill Aug 31 '17 at 20:05
47
$\begingroup$

I assume that the task is to compute $mul(10, a)= 10a$. You don't need to do multiplication. A single binary adder is enough since $$10a = 2^3a + 2a$$ meaning you add one-time left-shifted $a$ to 3-time left-shifted $a$. For general multiplication $mul(x,y)$ please see this article.

$\endgroup$
  • 10
    $\begingroup$ +1 for recognizing that 10 is a constant, so we don't need the general purpose multiplier. It also helps that you used wordings which are easy to translate into logic-gates, since the OP mentioned that was their end goal. $\endgroup$ – Cort Ammon Aug 31 '17 at 19:39
  • 6
    $\begingroup$ Fun fact: in x86 assembly, you (or a smart compiler) can use this trick multiply by 10 with (slightly) lower latency than an imul instruction. (godbolt.org/g/uSUSHu for x86, ARM, and MIPS asm compiler output for a trivial *10 function that you can probably read even if you don't know asm). Actually for x86, compilers typically use a = a + a*4; a+=a; because that's more efficient: stackoverflow.com/questions/6120207/imul-or-shift-instruction. $\endgroup$ – Peter Cordes Sep 1 '17 at 0:28
11
$\begingroup$

Multiplying by 10 is the same as multiplying by $(1010)_2$. To multiply a binary number $x$ by 10, we thus just have to add $x0$ and $x000$. For example, $6 \times 10 = 60$ is implemented by $$ \begin{array}{ccccccc} &0&0&1&1&0&0 \\ +&1&1&0&0&0&0 \\\hline &1&1&1&1&0&0 \end{array} $$ The input is $(6)_{10} = (110)_2$, and the output is $(111100)_2 = (60)_{10}$.

$\endgroup$
6
$\begingroup$

Sure. You just compute $1010_\mathrm{b}\times 110_\mathrm{b}$ using the binary version of long multiplication (or some other algorithm). The nice thing about long multiplication in binary is that you never have to carry anything, except when you're adding things up at the end.

   1010
    110 x
  ------
    000
   110
  000
 110
--------
 111100
--------

and note that $11100_\mathrm{b}=60_\mathrm{d}$, as expected.

$\endgroup$
-2
$\begingroup$

Multiply by 8 (left shift 3) then add to it a multiply by two (left shift 1).

$\endgroup$
  • $\begingroup$ Which would be multipliying it by 16 -- which is what the OP needs how? $\endgroup$ – Raphael Sep 1 '17 at 16:30
  • 9
    $\begingroup$ @Raphael I think you've misunderstood: this answer suggests computing $10x$ by computing $8x$ and $2x$ and adding them together. So it's just a dupe of the accepted answer. Reed, please only add new answers if they say something that hasn't already been said. $\endgroup$ – David Richerby Sep 1 '17 at 16:39

Your Answer

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.