diff options
Diffstat (limited to 'ps1/main.tex')
| -rw-r--r-- | ps1/main.tex | 13 |
1 files changed, 6 insertions, 7 deletions
diff --git a/ps1/main.tex b/ps1/main.tex index b04d730..b773275 100644 --- a/ps1/main.tex +++ b/ps1/main.tex @@ -155,13 +155,6 @@ t = w} \section*{Problem 3} -\paragraph{First solution \emph{(too easy, feels like cheating).}} We saw in -class how to compute the most signigicant bit set to one. But observe that -\texttt{x \& $\sim$(x-1)} will clear all the bits of $x$ except for the least -significant bit set to one. Assuming access to a procedure \texttt{msb} to -compute the most significant bit set to one, we can simply define -\texttt{lsb(x) $:=$ msb(x \& $\sim$(x-1))}. - \paragraph{Second solution.} Using Problem 2 and what we did in class, we assume that we have access to the following procedures: @@ -242,5 +235,11 @@ Note that the above code only requires a constant number of multiplications and bitwise operations once the constants $m$, $a$, $b$ and $c$ have been pre-computed. +\paragraph{Alternative solution \emph{(too easy, felt like cheating).}} We saw in +class how to compute the most signigicant bit set to one. But observe that +\texttt{x \& $\sim$(x-1)} will clear all the bits of $x$ except for the least +significant bit set to one. Assuming access to a procedure \texttt{msb} to +compute the most significant bit set to one, we can simply define +\texttt{lsb(x) $:=$ msb(x \& $\sim$(x-1))}. \end{document} |