A given positive integer n has binary expansion coefficients

A given positive integer n has binary expansion coefficients a_k-1,...,a_2, a_1, a_0. Express the binary expansions of the lowing number in terms of these coefficients. For example, the binary expansion of 2n is (a_k-1 ... a_2 a_1 a_0 0)_2. a. 8n b. n DIV 4 c. n MOD 4 Teachers in the Middle Ages supposedly tested the teal-time propositional logic ability of a student via a technique known as an obligato game. In an obligate game, a number of rounds is set and in each round the teacher gives the student successive assertions that the student must either accept or reject

Solution

Given binary (a_k-1a_{k-2............}a₃a₂a₁a₀ )

Lets take example and then Go over the question
1. Binary of 2 is (10) , 2*2 = 4 (Binary of 4 is 100 ) so whenever we multiply a number by 2 a zero is appended to its right. 4*2 = 8 (1000). So Its like Any Number x 2ⁿ = (AnyNumber00000..n times)
2*8 = (10)*2³ = (10000) ..So It works this way results in 16. [Multiplicatiion by 2ⁿ appends n bit at the end to output]

2. [Division by 2ⁿ removes n bit from the end of input and gives us the output]

8/2 = 1000/2¹   = 100 , removes last one bit [4 is the answer ]
16/4 = 10000/2² = 100 , removes last two bit [4 is the answer ]

3. Modulus (%) means the remainder like 4 %2 = 0 & 4%3 = 1
So it works this way 10%4 = 2 , So 10 & (4-1) = > 10 &3 = > 1010 & 0011 =>0010 [2]
So any P modulo Q is [ P & (Q-1) ] where & is bitwise AND operator


Now coming to our question.
1. 8n : As we know multiplication of binary number by 8 added 2³ i.e 3 zeros at the end of that number
Our binary number is (a_k-1a_{k-2............}a₃a₂a₁a₀ )
So 8n = (a_{k-1............}a₃a₂a₁a₀ 000)₂

2. n DIV 4: As we know when we divide a number n by any binary number of 2^k .It removes k number of digits starting from LSB. For us its 2^k So k =2 here.
Our binary number is (a_k-1a_{k-2............}a₃a₂a₁a₀ ).
So n DIV 4 = (a_{k-1............}a₃a₂)₂ => (00a_{k-1............}a₃a₂)₂ As we can see two LSB a₁a₀ are removed .

3. n MOD 4: As we know when we modulus a number n by any binary number of k. It does a bit wise AND of num n and k-1
Our binary number is (a_k-1a_{k-2............}a₃a₂a₁a₀ ) and k =4 = > (a_k-1a_{k-2............}a₃a₂a₁a₀ ) & (3)
So (a_k-1a_{k-2............}a₃a₂a₁a₀ ) & (0_k-1.......0011) = (0_k-10_k-2............a₁a₀ )
So n MOD 4 = (0_k-10_k-2............a₁a₀ )₂ is the answer .


Thanks, I hope it clarifies. Let me know if there is anything.