ISI2014-PCB-A-1b

1 vote
176 views

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}$?
0
(i) 3

(ii) Highest power of 2

1 vote

(i) 3

(ii) For non negative integers, it counts the number of 1s in the binary representation of the number. Ex: x=13 (1101) will give 3

Edit: It seems this question was also asked in TIFR 2014. (https://gateoverflow.in/27136/tifr2014-b-2?show=27160)

edited by

Related questions

1
218 views
Let $A$ be a 30 40 matrix having 500 non-zero entries. For $1 \leq i \leq 30$, let $r_i$ be the number of non-zero entries in the $i$-th row, and for $1 \leq j \leq 40$, let $m_j$ be the number of non-zero entries in the $j$-th column. Suppose ... top of the stack contains the value $max_{1\leq i \leq 30} r_i$. Write pseudo-code for creating such a stack using a single scan of the matrix $A$.
1 vote
Let $A$ be a $30 \times 40$ matrix having $500$ non-zero entries. For $1 \leq i \leq 30$, let $r_i$ be the number of non-zero entries in the $i$-th row, and for $1 \leq j \leq 40$, let $m_j$ be the number of non-zero entries in the $j$-th column. Show that there is a k such that $1 \leq k \leq 30$, $r_k \geq 17$ and there is an $l$ such that $1 \leq l \leq 40$, $m_l \leq 12$.
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})$.
Let $m$ and $n$ be two integers such that $m \geq n \geq 1.$ Count the number of functions $f : \{1, 2, \ldots , n\} \to \{1, 2, \ldots , m\}$ of the following two types: strictly increasing; i.e., whenever $x < y, f(x) < f(y),$ and non-decreasing; i.e., whenever $x < y, f(x) ≤ f(y).$