14
I need to develop an algorithm in Visualg where I enter with a number and it tells me if it’s power of 2 or not. What strategies can I use?
14
I need to develop an algorithm in Visualg where I enter with a number and it tells me if it’s power of 2 or not. What strategies can I use?
12
Successively divide your x number by 2.
If the rest is always 0 and you reach the quotient 1 is because x is a power of 2.
Example:
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 is a power of 2.
12
The most efficient way is to verify that the number-1 ends in 1111...
binary. In Javascript this is:
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]));
}
Applying for 8 you can see what is happening mathematically.
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
10
For this case just apply a single formula:
Log Value / Log 2.
If the result is a integer then Reported value is based on power of 2.
MATHEMATICAL EXPLANATION
We have to 2 to the power of x is equal to y, where y is the number you want to know if the base is equal to 2, and x is the power of 2 that will result in y.
By the properties of mathematics, and in particular that of logarithms, the following solution is presented.
Heed: Do not set the values as shown in this example, otherwise the result will not be an integer value!!!
Thus, without rounding up, check that the result does not display decimal places (integer), and when not displayed, you will know that this value is formed by base power 2. Good luck!
Complex, however, very interesting, especially because it is a concept involving logarithm, which many find a "boring" calculation, is ignored. + 1
Although the explanation is complex, the solution is based on a single formula to verify if the result is an integer, that is, it is not even an algorithm, it is a simple formula application. See what math can do for us...
Due to the inherently inaccurate calculation of the floating point logarithm (as is the case with most programming languages and I believe is the case with Visualg), this solution may have some flaw. Due to numerical representation, of course, no mathematical flaw
5
Divide the number by two until the rest of the division is less than or equal to 1 (use a loop for this)
Well, I get it, so far, but now how am I going to put together a Visualg algorithm that does that? Because this is still a problem! what method I can use to solve this problem?
With the algorithm and a Visualg booklet you can solve your problem without any difficulty... And what we have here: http://www2.joinville.udesc.br/~Alp/arquivos/Udesc_apostila_sobre_visualg_2011.pdf
1
i created a c++ function that checks if a number is power 2 using base 2 logarithms. EXPLANATION: the logarithm is calculated in base 2 of the given number and all we have to do is check if the result of that calculation is an integer, to check if a number is an interim one just put that number in an integer variable X and put itlo also in a real variable Y. If the difference of X and Y is 0 then the result is interim which means that the number is a power of 2, otherwise the number is not a power of 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')
Hello Lucas, can you translate the repsota into Portuguese? And while you’re at it explain what the idea of having Ejercicio 5.7.6.
in response? You copied the answer from somewhere?
Browser other questions tagged algorithm mathematics visualg
You are not signed in. Login or sign up in order to post.
That was the simplest! + 1
– Marconi
I would like to see two examples, if you don’t mind: 8 and 6, which should return true and false respectively, in terms of the bit operations performed. I can’t see the correctness of your answer, I can’t simulate the bits without paper or computer at hand
– Jefferson Quesado
The people in the chat room took away my doubt and I could see. If anyone else is experiencing difficulties: https://chat.stackexchange.com/transcript/11910/2017/10/30/0-3
– Jefferson Quesado
@Marconi Only one correction in the code, according to the post on the link https://stackoverflow.com/a/600306/1377664 if
v
for0
, will return true, but0
is not power of2
, therefore, it should bereturn (x != 0) && ((x & (x - 1)) == 0);
@Jeffersonquesado– Sam
@DVD My code does the same thing. At least, in javascript, since if v is 0, the result is 0, which is a false value. This was also explained in the chat pointed out by Jefferson. By the way that wasn’t my source of the answer and I’ve forgotten where I saw it, or I’d even put the link.
– Bruno Costa
@Brunocosta One change I suggest to make is to put
return Boolean(v && !(v & (v - 1)))
so that, instead of returning 0, integer, returnsfalse
, boolean, increasing consistency of function (https://repl.it/N1In/0).– Woss
@Andersoncarloswoss To keep the spirit of the code the thickest would be even
return !!(v && !(v & (v - 1)))
– Bruno Costa