ISRO2018-3

Question

If a variable can take only integral values from $0$ to $n$, where $n$ is an integer, then the variable can be represented as a bit-field whose width is $($the log in the answer are to the base $2$, and $\left \lceil \log_{}{n} \right \rceil$ means the floor of $\log_{}{n}\ )$

1. $\left \lceil \log (n) \right \rceil + 1 \text{ bits}$
2. $\left \lceil \log (n-1) \right \rceil  + 1 \text{ bits}$
3. $\left \lceil \log (n+1) \right \rceil + 1\text{ bits}$
4.  None of the above

Comments

@rajatmyname FInal answer key still says option A is the answer.

---

Can't understand how option A is correct.

suppose I have to represent 0 to 17.

to represent 17, we can use 5 bits( 4 bits upto 15 & then 1 more bit required).

but according to option A, it gives 6 bits to represent 17.

---

@MRINMOY_HALDER, No, see its clearly written in question to take the floor and not ceil. 

so floor(log2 17) + 1 = 4 + 1 = 5. 

Answer 1

Option D is correct.

log 0 is $-\infty$ but a variable having value 0 requires 1 bit to store.

This eliminates option A and B.

For option C take n=3, it will give 3 bits to store value 3. This is false, 3 requires 2 bits only(11 in binary).

Thus, option C is also incorrect.

Comments

Option B with n=0 will give complex values. With approximation(see image) and floor, it will give us 4+1=5 bits to represent 0, which is wrong.

---

We can't put n=0 in option A as domain of logn don't allow that .... So dis formula is valid for n>0... So A) shud be correct for n>0....!!We can't say it is wrong for n=0 as we have not defined it....

---

its given from 0 to n , which means n should be greater than 0 . one cant say from 0 to 0 . and 0 and n both are included ,if its saying from 0 to n .. Just you cant take log 0 ,because minimum it will be from 0 to 1 . so option A is only satisfied

Answer 2

Here we have to choose a variable from the interval (0,n]

Note that a number of the form 2^m has m+1 bits.

If 2^m<=n<=2^(m+1)

then n should also have m+1 bits.

Thus any number chosen in between (0,n] should have [log (n)]+1 bits.

So,option A is correct.

Comments

surajumang08, what if we take 0. than log(0) is negative infinity so all 3 option are not following that property

---

In the question it is given that the variable n is taking only integral values from 0 to n which means that it is taking integral values in the open interval (0,n) So, it cant take the value 0 or the value n. If n=16 it cant take that value. @suraj

---

in question nothing like open interval is mentioned,

Answer 3

Let n=8,  (i.e variable take value from 0 to 8) (take worst case)

in binary:  x = log8(base to 2)  = 3

But for representing the 8, we need at least  (x+1) bit,

similarly for n bit, [log n(base to 2) + 1] bit required.

Answer 4

its given from 0 to n , which means n should be greater than 0 . one cant say from 0 to 0 . and 0 and n both are included ,if its saying from 0 to n . Just you cant take log 0 ,because minimum it will be from 0 to 1 . so option A is only satisfied

Comments

yeah i thought the same.Hence answer should be A