The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
117 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}$?
asked in Algorithms by Veteran (96.2k points) | 117 views
0
(i) 3

(ii) Highest power of 2

1 Answer

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)

answered by Junior (881 points)
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,587 questions
54,197 answers
187,535 comments
71,151 users