Рубрики

Наименьшая степень 2 больше или равна n

Напишите функцию, которая для заданного номера n находит число p, которое больше или равно n и имеет наименьшую степень 2.
Примеры :

    Input : n = 5
    Output: 8     

    Input  : n = 17
    Output : 32     

    Input  : n = 32
    Output : 32     

Есть много решений для этого. Давайте возьмем пример 17, чтобы объяснить некоторые из них.


Способ 1 (Использование журнала номера)

    1.  Calculate Position of set bit in p(next power of 2):
        pos =  ceil(lgn)  (ceiling of log n with base 2)
    2.  Now calculate p:
        p   = pow(2, pos) 

Пример :

    Let us try for 17
            pos = 5
            p   = 32    


Способ 2 (получение позиции только установленного бита в результате)

    /* If n is a power of 2 then return n */
    1  If (n & !(n&(n-1))) then return n 
    2  Else keep right shifting n until it becomes zero 
        and count no of shifts
        a. Initialize: count = 0
        b. While n ! = 0
                n = n>>1
                count = count + 1

     /* Now count has the position of set bit in result */
    3  Return (1 << count)  

Пример :

    Let us try for 17
                 count = 5
                 p     = 32   

C ++

// C ++ программа для поиска
// наименьшая степень 2
// больше или равно n
#include <bits/stdc++.h>

using namespace std;

  

unsigned int nextPowerOf2(unsigned int n) 

    unsigned count = 0; 

      

    // Первый n в следующем условии

    // для случая, когда n равно 0

    if (n && !(n & (n - 1))) 

        return n; 

      

    while( n != 0) 

    

        n >>= 1; 

        count += 1; 

    

      

    return 1 << count; 

  
// Код драйвера

int main() 

    unsigned int n = 0; 

    cout << nextPowerOf2(n); 

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

#include<stdio.h>

  

unsigned int nextPowerOf2(unsigned int n)

{
unsigned count = 0;

  
// Первый n в следующем условии
// для случая, когда n равно 0

if (n && !(n & (n - 1)))

    return n;

  

while( n != 0)

{

    n >>= 1;

    count += 1;

}

  

return 1 << count;

}

  
// Код драйвера

int main()

{

unsigned int n = 0;

printf("%d", nextPowerOf2(n));

return 0;

}

Джава

// Java-программа для поиска
// наименьшая степень 2
// больше или равно n

import java.io.*;

  

class GFG

{

    static int nextPowerOf2(int n)

    {

        int count = 0;

  

        // Первый п ниже

        // условие для

        // случай, когда n равно 0

        if (n > 0 && (n & (n - 1)) == 0)

            return n;

  

        while(n != 0)

        {

            n >>= 1;

            count += 1;

        }

  

        return 1 << count;

    }

  

    // Код драйвера

    public static void main(String args[])

    {

        int n = 0;

        System.out.println(nextPowerOf2(n));

    }

}

  
// Эта статья предоставлена
// Аншика Гоял.

python3

def nextPowerOf2(n):

    count = 0;

  

    # Первый п ниже

    # условие для

    # случай, когда n равно 0

    if (n and not(n & (n - 1))):

        return n

      

    while( n != 0):

        n >>= 1

        count += 1

      

    return 1 << count;

  

  
Код водителя

n = 0

print(nextPowerOf2(n))

# Этот код добавлен
# Смита Динеш Семвал

C #

// C # программа для поиска самых маленьких
// степень 2 больше чем
// или равно n

using System;

  

class GFG

{

    static int nextPowerOf2(int n)

    {

        int count = 0;

  

        // Первый п ниже

        // условие для

        // случай, когда n равно 0

        if (n > 0 && (n & (n - 1)) == 0)

            return n;

  

        while(n != 0)

        {

            n >>= 1;

            count += 1;

        }

  

        return 1 << count;

    }

  

    // Код драйвера

    public static void Main()

    {

        int n = 0;

        Console.WriteLine(nextPowerOf2(n));

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// PHP программа для поиска самых маленьких
// степень 2 больше или
// равно n

  

function nextPowerOf2($n)

{

$count = 0;

  
// Первый n в следующем условии
// для случая, когда n равно 0

if ($n && !($n&($n - 1)))

    return $n;

  

while($n != 0)

{

    $n >>= 1;

    $count += 1;

}

  

return 1 << $count;

}

  
// Код драйвера

$n = 0;

echo (nextPowerOf2($n));

  
// Этот код предоставлен vt_m
?>


Выход :

1


Метод 3 (сдвиг результата по одному)

Спасибо coderyogi за предложение этого метода. Этот метод является вариацией метода 2, где вместо получения количества мы сдвигаем результат по одному в цикле.

C ++

// C ++ программа для поиска самых маленьких
// степень 2 больше или
// равно n
#include<bits/stdc++.h>

using namespace std;

unsigned int nextPowerOf2(unsigned int n) 

    unsigned int p = 1; 

    if (n && !(n & (n - 1))) 

        return n; 

  

    while (p < n) 

        p <<= 1; 

      

    return p; 

  
// Код драйвера

int main() 

    unsigned int n = 5; 

    cout << nextPowerOf2(n); 

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

#include<stdio.h>

unsigned int nextPowerOf2(unsigned int n)

{

    unsigned int p = 1;

    if (n && !(n & (n - 1)))

        return n;

  

    while (p < n) 

        p <<= 1;

      

    return p;

}

  
// Код драйвера

int main()

{

unsigned int n = 5;

printf("%d", nextPowerOf2(n));

return 0;

}

Джава

// Java программа для поиска самых маленьких
// степень 2 больше или
// равно n

import java.io.*;

  

class GFG

{

    static int nextPowerOf2(int n)

    {

        int p = 1;

        if (n > 0 && (n & (n - 1)) == 0)

            return n;

  

        while (p < n) 

            p <<= 1;

      

        return p;

    }

  

    // Код драйвера

    public static void main(String args[])

    {

        int n = 5;

        System.out.println(nextPowerOf2(n));

    }

}

  
// Эта статья предоставлена
// Аншика Гоял.

python3

def nextPowerOf2(n):

  

    p = 1

    if (n and not(n & (n - 1))):

        return n

  

    while (p < n) :

        p <<= 1

          

    return p;

  

  
Код водителя

n = 5

print(nextPowerOf2(n));

  
# Этот код предоставлен
# Смита Динеш Семвал

C #

// C # программа для поиска самых маленьких
// степень 2 больше или
// равно n

using System;

  

class GFG 

{

  

    static int nextPowerOf2(int n)

    {

        int p = 1;

        if (n > 0 && (n & (n - 1)) == 0)

            return n;

  

        while (p < n) 

            p <<= 1;

      

        return p;

    }

  

    // Код драйвера

    public static void Main()

    {

        int n = 5;

        Console.Write(nextPowerOf2(n));

    }

}

  
// Этот код предоставлен Smitha.

PHP

<?php

  

function nextPowerOf2($n)

{

    $p = 1;

    if ($n && !($n & ($n - 1)))

        return $n;

  

    while ($p < $n

        $p <<= 1;

      

    return $p;

}

  
// Код драйвера

$n = 5;

echo ( nextPowerOf2($n));

  
// Этот код предоставлен vt_m.
?>


Выход :

8

Сложность времени: O (lgn)


Метод 4 (индивидуальный и быстрый)

    1. Subtract n by 1
       n = n -1

    2. Set all bits after the leftmost set bit.

    /* Below solution works only if integer is 32 bits */
                n = n | (n >> 1);
                n = n | (n >> 2);
                n = n | (n >> 4);
                n = n | (n >> 8);
                n = n | (n >> 16);
    3. Return n + 1

Пример :

Steps 1 & 3 of above algorithm are to handle cases 
of power of 2 numbers e.g., 1, 2, 4, 8, 16,

    Let us try for 17(10001)
    step 1
       n = n - 1 = 16 (10000)  
    step 2
       n = n | n >> 1
       n = 10000 | 01000
       n = 11000
       n = n | n >> 2
       n = 11000 | 00110
       n = 11110
       n = n | n >> 4
       n = 11110 | 00001
       n = 11111
       n = n | n >> 8
       n = 11111 | 00000
       n = 11111
       n = n | n >> 16
       n = 11110 | 00000
       n = 11111    

    step 3: Return n+1
     We get n + 1 as 100000 (32)

Программа:

C ++

// C ++ программа для
// Находит следующую степень двух
// для п. Если п сам по себе является
// Степень двойки возвращает n
#include <bits/stdc++.h> 

using namespace std; 

    

unsigned int nextPowerOf2(unsigned int n)  

{

    n--;

    n |= n >> 1;

    n |= n >> 2;

    n |= n >> 4;

    n |= n >> 8;

    n |= n >> 16;

    n++;

    return n;

    
// Код драйвера

int main()  

{  

    unsigned int n = 5;  

    cout << nextPowerOf2(n);  

    return 0;  

}  

    
// Этот код предоставлен SHUBHAMSINGH10

С

#include <stdio.h>
// Находит следующую степень двух
// для п. Если п сам по себе является
// Степень двойки возвращает n

unsigned int nextPowerOf2(unsigned int n)

{

    n--;

    n |= n >> 1;

    n |= n >> 2;

    n |= n >> 4;

    n |= n >> 8;

    n |= n >> 16;

    n++;

    return n;

}

  
// Код драйвера

int main()

{

    unsigned int n = 5;

    printf("%d", nextPowerOf2(n));

    return 0;

}     

Джава

// Java программа для поиска самых маленьких
// степень 2 больше или
// равно n

import java.io.*;

  

class GFG

{

    // Находит следующую степень двух

    // для п. Если п сам по себе является

    // Степень двойки возвращает n

    static int nextPowerOf2(int n)

    {

        n--;

        n |= n >> 1;

        n |= n >> 2;

        n |= n >> 4;

        n |= n >> 8;

        n |= n >> 16;

        n++;

          

        return n;

    }

  

    // Код драйвера

    public static void main(String args[])

    {

        int n = 5;

        System.out.println(nextPowerOf2(n));

    }

  
// Эта статья предоставлена
// Аншика Гоял.

Python 3

# Находит следующую степень двух
# для п. Если п сам по себе является
# Степень два затем возвращает n

def nextPowerOf2(n):

  

    n -= 1

    n |= n >> 1

    n |= n >> 2

    n |= n >> 4

    n |= n >> 8

    n |= n >> 16

    n += 1

    return n

  
# Драйвер программы для тестирования
# над функцией

n = 5

print(nextPowerOf2(n))

  
# Этот код добавлен
# от Smitha

C #

// C # программа для поиска самых маленьких
// степень 2 больше или
// равно n

using System;

  

class GFG

{

  

    // Находит следующую степень двух

    // для п. Если п сам по себе является

    // Степень двойки возвращает n

    static int nextPowerOf2(int n)

    {

        n--;

        n |= n >> 1;

        n |= n >> 2;

        n |= n >> 4;

        n |= n >> 8;

        n |= n >> 16;

        n++;

          

        return n;

    }

  

    // Код драйвера

    public static void Main()

    {

        int n = 5;

        Console.WriteLine(nextPowerOf2(n));

    }

  
// Этот код предоставлен anuj_67.

PHP

<?php
// PHP программа для поиска самых маленьких
// степень 2 больше или
// равно n

  
// Находит следующую степень
// два для п. Если п сам
// это степень двух тогда
// возвращает n

function nextPowerOf2($n)

{

    $n--;

    $n |= $n >> 1;

    $n |= $n >> 2;

    $n |= $n >> 4;

    $n |= $n >> 8;

    $n |= $n >> 16;

    $n++;

    return $n;

}

  

    // Код драйвера

    $n = 5;

    echo nextPowerOf2($n);

  
// Этот код предоставлен Ajit
?>


Выход :

8

Сложность времени: O (lgn)

Похожие сообщения:
Наибольшая сила 2 меньше или равна данному числу

Ссылки :
http://en.wikipedia.org/wiki/Power_of_2

Рекомендуемые посты:

Наименьшая степень 2 больше или равна n

0.00 (0%) 0 votes