It is necessary to create an algorithm that accepts strictly positive n as input and outputs k such that 2 ^ k ≤ n and 2 ^ k + 1> n

Help to make the algorithm, studying in the first year of undergraduate computer science.

The easiest way with If and / or While functions. Not the very first week we were asked this. I do not understand which side to approach to the solution of this issue. Please explain in accessible language, step by step.

  • one
    For starters, you would formulate a task. 2^k ≤ n and 2^k+1 > n , I am afraid to upset you, a clear description is not. Then, my crystal ball tells you that you need the logarithm function for base 2. And for an explanation why you should contact the lecturer, he probably explained this in the very first lecture (the topic was probably “binary number system”, yes?) - VladD
  • There is no need to do without logarithms, they didn’t even go through this and there was no question about this at the lecture. You can even build an algorithm separately for each left and right side. And let's say k = 2 n = 7 - Edgar Kiljak
  • You need to calculate k or 2 ^ k - Mirdin
  • I like this: 2 ^ k ≤ n and 2 ^ k + 1> n I apologize for English, I study in England - Edgar Kiljak
  • 2
    According to community rules, questions should not be reduced to completing tasks for students. Give an example of your implementation describing specific problems. - Nicolas Chabanovsky ♦

5 answers 5

  1. Numbers are stored in computer in binary form (as a sequence of zeros and ones), so for example, 13 will look like 1101.
  2. The division by 2 corresponds to the operation of the shift to the right (>>) according to the multiplication of the shift to the left (<<).
  3. The powers of 2 thus correspond to the digit 1 in position k (the power of the number) and 0 in the remaining positions.
  4. To obtain k, we need to shift the number n to the right until it exceeds 0, while incrementing k from (-1).

CODE

 unsigned int n = 1223456789; int k = -1; for (unsigned int i = n; i > 0; k++, i >>= 1);

Step by Step:

 1. Задаете число n=[ваше число] и k = -1 2. Проверяете n>0 3. True 3.1 Увеличиваем k на 1 3.2 Делим n на 2 (целочислено) или, что то же самое, применяем операцию сдвига на 1 3.3 Переходим к шагу 2 4. False Конец алгоритма. Выводим данные.
  • What will your algorithm give when N = 1? The answer in this case will be the set of integers from -INF to 0 inclusive. - Vitalii Obideiko September
  • @ VitaliyObideiko 0 (which is the correct answer), n ^ 0 = 1 - Mirdin
  • n ^ -1 = 0.5 0.5 + 1> 1 0.5 <= 1 - Vitalii Obideiko
  • @ VitaliyObideiko - you have read the algorithm, -1 it will give out only if n <= 0 which are impossible according to the condition - Mirdin September
  • when N = 1, our restrictions turn into 2 ^ k ≤ 1 and 2 ^ k + 1> 1. Then, after the substitution, K = -1 => 2 ^ (- 1) ≤ 1 and 2 ^ (- 1) +1> 1 => 0.5 ≤ 1 and 0.5 + 1> 1. That's right, after that. K = -1 is also the right answer. - Vitalii Obideiko

For conditions 2^k ≤ n and 2^(k+1) > n it suffices to find the leading nonzero bit (its position) in the binary notation of the number n .

Algorithm : we move from high bits to low bits, until we stumble upon the first unit.

  1. set the initial value of the bit position - the highest, which allows the language and system - 64-1 or 32-1 (or 30, if the 32-bit system and signed integers);
  2. in the cycle, to compare with zero the value of the bit operation "AND" between the specified number and the number whose binary record consists of one unit in the current position;
  3. if zero - we have not yet reached the senior unit. Decrease current position by 1. Repeat loop.
  4. if not zero, the first (senior) unit is found in the current position. The current position is the answer.

An example of a JavaScript function, which, unfortunately, is limited to 31 bits for bit operations:

 function MSB(n) { var bit = 31; // 30..0 while( bit > 0 && !( n & (1<<--bit))); return bit; }

Working example

    For 2 ^ K ≤ N and (2 ^ K) +1> N, the algorithm is very simple. We take a positive integer as an input. The output must be an integer K. So, if N is not a power of 2, then there is no answer, and if N is a power of 2, then the answer is a power itself. You need only to check whether N is a power of 2, and if it is, then find which one. Algorithms of such checks are many and easy to find. An example of checking whether a number is a power of 2 per c ++:

     int isPow2(int a) { return !(a&(a-1)); }

    Find exactly what degree you can divide the number in the loop:

     int k=0; while(n!=1){ k++; n/=2; }

    upd

    Since by assumption N is integer and not negative, i.e. N> = 1, then for N = 1 answers there will be an infinite set of -INF <K <= 0, and in all other cases it will be as I wrote above.

    • Your code is basically correct, but in my opinion you are solving the wrong task. Why do you need the isPow2 function? Re-read the condition - something you have not screwed up in a simple moaning task. - Mirdin
    • This is an example of the following: 2 ^ k ≤ n and 2 ^ k + 1> n. The task is simple, but you gave the wrong answer to it. The whole point is that the condition is satisfied only by those K for which 2 ^ K = N for N> 1, and for N = 1 I have already described in the answer. - Vitalii Obideiko September
    • one
      The first week of studying computer science - you seriously think that students will be confused, in fact they are asked to find the power of two closest to the number n - Mirdin
    • one
      We simply solve different problems, I personally see 2 ^ (k + 1)> n, because in the first week there is no special meaning in (2 ^ k) +1> n. But yes, the vehicle should clarify this with its teacher - Mirdin
    • 2
      @Mirdin here you are right, I personally see 2 ^ (k + 1)> n - Edgar Kiljak

    We clear nonzero bits from the end until they run out. If you run out, we return the previous value (with one single bit).

     function f(n) { while (n & n-1) n &= n - 1; return n; }

      We look for k from condition 2 k <= n <2 k + 1 for k <32.
      At each iteration, the position of the most significant bit is specified to the half-word, byte, tetrad, dyad and position:

       k = (n > 65535) ? 16 : 0; if ((n>>k) > 255) k += 8; if ((n>>k) > 15) k += 4; if ((n>>k) > 3) k += 2; if ((n>>k) > 1) k += 1;