0

Let x, y and z be three integers. Suppose that the binary representation of x uses n bits, the binary representation of y uses n bits and the binary representation of z uses n bits. How many bits does the binary representation of the product xyz use? Note: Provide all details of your solution and give your final answer using Θ-notation.

I figured out if x y and z are all the maximal bit number then x=y=z=2^n-1

Not sure how to proceed or deliver the answer in Θ-notation

Student54125
  • 68
  • Thanks so much would you know how to deliver the answer in Θ-notation as thats a bonus part of that question. – Student54125 Oct 11 '16 at 23:48
  • From the other question you know that it’s $O(n)$, since it’s bounded above by $3n$. On the other hand, its clearly bounded below by $n$, so it’s also $\Omega(n)$. Therefore ... ? – Brian M. Scott Oct 11 '16 at 23:49
  • Hi, sorry for all the questions but your solution is kind of complicated how did you convert the equation into binary. I understand your end result but im having trouble getting there. – Student54125 Oct 12 '16 at 00:03
  • $2^n$ in binary is a $1$ followed by $n$ zeroes; that gives you the first expression in the chain of equalities. Alternatively, think of it this way: if you multiply a binary number by $2$, you just tack add a $0$ on the righthand end — it’s like multiplying a number base ten by ten. If you multiply $3$ (binary $11$) by two $2n$ times, you end up tacking on $2n$ zeroes to get $11\underbrace{00\ldots 00}_{2n}$. I’ll add a little color to the answer to show what I did next; it’s just basic arithmetic the way you’d do it with pencil and paper, but in base two instead of base ten. – Brian M. Scott Oct 12 '16 at 00:08
  • That makes sense thanks so much for the help. – Student54125 Oct 12 '16 at 00:15
  • You’re very welcome. – Brian M. Scott Oct 12 '16 at 00:16

0 Answers0