(ii) Highest power of 2

The Gateway to Computer Science Excellence

+1 vote

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;

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

0 votes

(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)

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,644 questions

56,503 answers

195,553 comments

101,033 users