14

Preciso desenvolver um algoritmo em VisuAlg onde eu entro com um número e ele me diz se é potência de 2 ou não. Quais estratégias posso usar?

6 Respostas 6

12

Divide sucessivamente o teu x número por 2.

Se o resto for sempre 0 e chegares ao quociente 1 é porque x é uma potência de 2.

Exemplo:

8192/2 = 4096

4096/2 = 2048

2048/2 = 1024

1024/2 = 512

512/2 = 256

256/2 = 128

128/2 = 64

64/2 = 32

32/2 = 16

16/2 = 8

8/2 = 4

4/2 = 2

2/2 = 1

8192 é uma potência de 2.

0
12

A forma mais eficiente é verificar se o número-1 termina em 1111... em binário. Em JavaScript isto é:

function isPowOf2(v){
    return v && !(v & (v - 1));
}

var test = [0, 1, 2, 4, 6, 8];

for(var i = 0; i < test.length; ++i){
    console.log(test[i] + " - " + isPowOf2(test[i]));
}

Aplicando para 8 pode-se ver o que está acontecendo matematicamente.

v = 8 = b1000 = true

v - 1 = 8 - 1 = 7 = b0111

8 & 7 = b1000 & b0111 = 0

!(8 & 7) = !(0) = true

v && !(8 & 7) = true Q.E.D

7
  • Essa foi a mais simples! +1
    – Marconi
    3/03/2017 às 14:07
  • Eu apreciaria de ver dois exemplos, se você não se importar: 8 e 6, que deveriam retornar verdade e falso respectivamente, em termos das operações de bits realizadas. Não estou conseguindo enxergar a corretude de sua resposta, não consigo simular os bits sem papel ou computador à mão 30/10/2017 às 2:14
  • O pessoal no chat me tirou a dúvida é consegui enxergar. Caso alguém mais esteja com dificuldades: chat.stackexchange.com/transcript/11910/2017/10/30/0-3 30/10/2017 às 2:43
  • @Marconi Só uma correção no código, de acordo com o post no link stackoverflow.com/a/600306/1377664 : se v for 0, irá retornar true, mas 0 não é potência de 2, logo, deveria ser return (x != 0) && ((x & (x - 1)) == 0); @JeffersonQuesado
    – Meu ovo
    30/10/2017 às 12:45
  • 1
    @DvD O meu código faz a mesma coisa. Pelo menos, em javascript, uma vez que se v for 0, o resultado é 0, que é um false value. Isso também foi explicado no chat apontado pelo Jefferson. Já agora essa nao foi a minha fonte da resposta e já me esqueci onde a vi, senao até punha o link. 30/10/2017 às 13:02
10

Para este caso basta aplicar uma única fórmula:

Log Valor / Log 2.

Se o resultado for um número inteiro então o Valor informado tem como base a potência de 2.

EXPLICAÇÃO MATEMÁTICA

Temos que 2 à potência de x é igual a y, onde y é o número que você quer saber se a base é igual a 2, e x é a potência de 2 que resultará em y.

Pelas propriedades da matemática, e em particular a dos logaritmos, a solução abaixo se apresenta.

Atenção: Não arredonde os valores como estão apresentados neste exemplo, senão o resultado não será um valor inteiro!!!

inserir a descrição da imagem aqui

Assim, sem arredondar valores, verifique se o resultado não apresenta casas decimais (número inteiro), e quando não apresentar, saberá que este valor é formado por potência de base 2. Boa sorte!

3
  • 2
    Complexo, porém, muito interessante, ainda mais por ser um conceito envolvendo logaritmo, que por muitos acharem um calculo "chato", é ignorado. +1
    – user28595
    1/06/2016 às 2:47
  • 3
    Apesar de ser complexa a explicação, a solução tem como base uma única fórmula para se verificar se o resultado é um número inteiro, ou seja, não se trata nem de um algoritmo, é uma simples aplicação de fórmula. Veja o que a matemática pode fazer por nós...
    – Leo
    1/06/2016 às 4:02
  • Devido ao cálculo inerentemente inexato do logaritmo em ponto flutuante (como é o caso da maioria das linguagens de programação e eu creio que seja o caso do VisuAlg), essa solução pode vir a ter alguma falha. Devido à representação numérica, claro, não falha matemática 30/10/2017 às 2:11
5

Divida o número por dois, até que o resto da divisão seja menor ou igual a 1 (use um loop para isso)

  • Se o resto da divisão for igual a 1 o número é potencia de 2
  • Se o resto da divisão for menor que 1 o número não é potencia de 2
2
  • 1
    Pois bem, entendi, até ai, mas agora como vou montar um algoritmo em VisualG que faça isso? pois este ainda é um problema! qual metodo posso utilizar para resolver este problema?
    – AGenaro
    1/06/2016 às 18:10
  • Com o algoritmo e uma apostila de VisualG você poderá resolver o seu problema sem dificuldade alguma... E o que temos aqui: www2.joinville.udesc.br/~alp/arquivos/… 2/06/2016 às 14:06
1

eu criei uma função em c++ que verifica se um número é potência de 2 usando logaritimo de base 2. EXPLICACÃO: calcula-se o logaritmo na base 2 do número dado e tudo que temos que fazer é verificar se o resultado desse cálculo é um número inteiro, para verificar se um numero é interio basta colocar esse numero numa variável inteira X e colocá-lo também numa variável real Y. Se o diferença de X e Y for 0 então o resultado é interio que significa que o número é uma potência de 2, senão então o número não é uma potência de 2.

#include<bits/stdc++.h>
using namespace std;


class Solution{
    public:
    // Function to check if given number n is a power of two.
    bool isPowerofTwo(long long n){
        //declaring variables that will help to check if the result of the log is an integer 
        int i=0;
        long double x=0;
        //then a put the result of the log in an integer and the same result in a long double variable
        i=log2l(n);
        x=log2l(n);
        //now we subtract the two results
        //if the subtraction is 0 then the number is a power of two 
        if(x-i==0)return true;
        //if no, the number is not a power of two
        else return false;
        // real simple.  
        
    }
};
-2
"""
 Ejercicio 5.7.6. Potencias de dos.
a) Escribir una función es_potencia_de_dos que reciba como parámetro un número 
 natural,y devuelva True si el número es una potencia de 2, y False en caso contrario.
b) Escribir una función que, dados dos números naturales pasados como parámetros, devuelva la
 suma de todas las potencias de 2 que hay en el rango formado por esos números
 (0sinohayningunapotenciade2entrelosdos).Utilizarlafunción es_potencia_de_dos ,
 descripta en el punto anterior.
"""
import os


def clear():
    """ cls de windows """
    os.system('cls' if os.name == 'nt' else 'clear')


def pausar():
    """ pausa de windows"""
    os.system('pause')


def es_potencia_de_dos(numero):
    """ Verifica si es potencia de dos, en primera instancia descartamos el 1 , que 
    seria 2 a la 0  luego vemos si podemos componer el numero que tenemos 
    como potencia de dos y de paso devolvemos que potencia de dos es , en caso de 
    serlo """

    if numero == 1:
        return True, 0

    r = 1
    for i in range(1, numero):
        r *= 2
        if r == numero:
            return True, i
        else:
            continue

    return False


def leer_numero():
    return input('\nIngrese el numero que desea verificar (* para salir) ')


x = leer_numero()
while x != '*':
    potencia, cual = es_potencia_de_dos(int(x))
    if potencia:
        print('Es potencia, 2 a la ', cual)
    else:
        print('No es potencia de dos')
    x = leer_numero()

clear()
print('Hasta luego..')
os.system('pause')
1
  • 2
    Olá Lucas, podes traduzir a repsota para português? E já agora explicar qual a ideia de ter ` Ejercicio 5.7.6.` na resposta? Copiaste a resposta de algum lado?
    – Sergio
    23/02/2019 às 20:21

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .