\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath, amsfonts}
\usepackage{clrscode}

\begin{document}

\begin{center} \Large
{\scshape 6.851 Advanced Data Structures (Spring'10)} \\[1ex]
{Prof.~Erik Demaine \qquad Dr.\ Andr\'e Schulz \qquad TA: Aleksandar Zlateski} \\[2ex]
\framebox{Problem 7} \quad {Sample Solutions}
\end{center}

\section*{\boldmath Finding the most significant 1 bit.}
\Procname{$\proc{Binomial-Heap-Union}(H_1,H_2)$}
\paragraph{(a)} We define $C_0 = 0^b$, and $(C_1) = 10^{b-1}$
$A_x = \big[x \texttt{ | } (x + \texttt{\textasciitilde}C_1) \big] \texttt{ \& } C_1$
\begin{codebox}
\Procname{$\proc{Step-a}(x)$}
\li $A_x \gets x + 01^{b-1}$
\li $A_x \gets A_x$ \texttt{|} $x$
\li \Return $A_x$ \texttt{\&} $10^{b-1}$
\end{codebox}


\paragraph{(b)}
$B_x = \big ( (A_x\texttt{ >> }(b-1)) \texttt{ * } (0^b1)^{b-1} \texttt{ >> } (w - b) \big ) \texttt{ \& } 1^b$
\begin{codebox}
\Procname{$\proc{Steps-ab}(x)$}
\li $A_x \gets \proc{Step-a}(x)$
\li $B_x \gets A_x$ \texttt{>>} $(b-1)$
\li $B_x \gets (B_x$ \texttt{*} $[0^b1]^{b-1}) $ \texttt{>>} $(w-b)$
\li \Return $B_x$ \texttt{\&} $1^b$
\end{codebox}

\paragraph{(c)} Note that the order of the chunks has changed in part (b).
We need to find the \emph{least} significant 1 bit. Also, not that $-x = \texttt{\textasciitilde} x + 1$.

$C_x = b - (B_x$ \texttt{\&} $-B_x)$
\begin{codebox}
\Procname{$\proc{Steps-abc}(x)$}
\li $B_x \gets \proc{Step-b}(x)$
\li $C_x \gets B_x$ \texttt{\&} $-B_x$
\li \Return $b - C_x$
\end{codebox}

\paragraph{(d)} Let $\alpha = \sum_{i=0}^{b-1} (1$ \texttt{<<} $i)$ \texttt{<<} $i$,
then by setting $y = (x$ \texttt{>>} $C_x)$ \texttt{\&} $1^b$, and
$z = (y$ \texttt{*} $[0^{b-1}1]^b)$ \texttt{\&} $\alpha$, we have reduced the problem to parts (a)-(c).

\paragraph{Full Algorithm}
\begin{codebox}
\Procname{$\proc{Most-Significant}(x)$}
\li $C_x \gets \proc{Steps-abc}(x)$
\li $y \gets (x$ \texttt{>>} $C_x)$ \texttt{\&} $1^b$
\li $z \gets (y$ \texttt{*} $[0^{b-1}1]^b)$ \texttt{\&} $\alpha$
\li $C_z \gets \proc{Steps-abc}(z)$
\li \Return $(C_x$ \texttt{<<} $b + C_z)$
\end{codebox}


\end{document}
