475 views
1 votes
1 votes

Let $x, y$ be two non-negative integers $< 2^{32}$. By $x \wedge y$ we mean the integer represented by the bitwise logical $AND$ of the 32- bit binary representations of $x$ and $y$. For example, if $x = 13$ and $y = 6$, then $x \wedge y$ is the bitwise $AND$ of 0$^{28}$1101 and 0$^{28}$0110, resulting in 0$^{28}$0100, which is 4 in decimal. (Here 0$^{28}$1101 means twenty-eight 0’s followed by the 4-bit string 1101.) Now consider the following pseudo-code:
integer x, n = 0;
while (x $\neq$ 0){
x $\leftarrow$ x $\wedge$ (x − 1);
n $\leftarrow$ n + 1;
}
print n;

  1. What will be the output of the pseudo-code for the input $x = 13$?
  2. What will be the output of the pseudo-code for an arbitrary non-negative integer $x < 2^{32}$?

1 Answer

Related questions

1 votes
1 votes
0 answers
3
go_editor asked May 30, 2016
341 views
Let $x=(x_1, x_2, \dots x_n) \in \{0,1\}^n$ By $H(x)$ we mean the number of 1's in $(x_1, x_2, \dots x_n)$. Prove that $H(x) = \frac{1}{2} (n-\Sigma^n_{i=1} (-1)^{x_i})$....
3 votes
3 votes
2 answers
4