Potęgi liczby 2

Witam, przerabiam kolejne zadanie z pętli, ale ciągle nie czuje się na siłach by dobrze napisać do końca program. Treść zadania brzmi. Napisać program, który wczytuje od użytkownika liczbę całkowitą dodatnią n, a następnie wyświetla na ekranie wszystkie potęgi liczby 2 nie większe, niż podana liczba. Mam problem z warunkiem wykonania pętli, np dla liczby 71 wyświetla mi 128, zamiast 64. Teoretycznie mogę zadeklarować warunek jako potęga*2<n, ale wolałbym znaleźć inny sposób na to zadanie :)

import java.util.Scanner;

public class petla2{
    public static void main(String[] args){
        Scanner num = new Scanner(System.in);
        System.out.println("Podaj liczbe: ");
        int n = num.nextInt();
        int potega= 1;
        while(n<0){
            System.out.println("podaj liczbe jeszcze raz");
            n=num.nextInt();
        }
        for(int i=1;potega<=n;i++){
            potega=potega*2;
            System.out.println(potega);
        }
    }
}

do {
  potega *= 2
} while (potega <= n)

nie sprawdzalem, ale chyba zadziala
no i nie jestem pewny składni pętli do.. while, bo ostatnio używałem z 5 lat temu :D

Tak wiem, że tak można, ale ja chciałem wykonać to forem :D

Tyle że taki for nie ma sensu, bo nawet nie używasz tego i

Trochę schematycznie to zrobiłem i wyszło bez sensu.

Zamiast

jasper93 napisał(a):

Kopiuj

            potega=potega*2;

użyj:

potega<<=1;

Lub ewentualnie:

        for(int i=0;potega<=n;++i) System.out.println(potega=(1<<i));

Doprawdy?

lookacode1 napisał(a):

Kopiuj

            long x = (long) Math.pow(2, i);

czy wiesz że tak naprawdę robisz

Math.exp(i*Math.ln(2)) 

?
Czy zdajesz sobie sprawy jaki jest koszt czasowy w porównywaniu do równoważnika (przy założeniu i>=0 oraz i jest całkowita)

1<<i

?

_13th_Dragon napisał(a):

Zamiast

jasper93 napisał(a):

Kopiuj

            potega=potega*2;

użyj:

Kopiuj

potega<<=1;

Jeszcze lepiej tak. Wtedy będzie ultra szybko.

public class App {
  static final int[] potęgi = new int[]{
      1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,
      2048, 4096, 8192, 16384, 32768, 65536, 131072,
      262144, 524288, 1048576, 2097152, 4194304, 8388608,
      16777216, 33554432, 67108864, 134217728, 268435456,
      536870912, 1073741824
  };

  public static void main(String[] args) {
    Scanner num = new Scanner(System.in);
    System.out.println("Podaj liczbe: ");
    int n = num.nextInt();
    while (n < 0) {
      System.out.println("podaj liczbe jeszcze raz");
      n = num.nextInt();
    }
    for (int i = 0; i < 1; i++) {
      System.out.println(potęgi[n]);
    }
  }
}

@_13th_Dragon: Wiem, że to nie jest optymalne :). Wybrałem w moim mniemaniu najprostsze rozwiązanie.
Program jest rozwiązaniem zadania, w którym nie jest nic wspomniane o złożoności czasowej jaką ma spełniać.

lookacode1 napisał(a):

@_13th_Dragon: Wiem, że to nie jest optymalne :). Wybrałem w moim mniemaniu najprostsze rozwiązanie.
Program jest rozwiązaniem zadania, w którym nie jest nic wspomniane o złożoności czasowej jaką ma spełniać.

Doprawdy?
Czyli iloczyn A i B będziesz szukać:

int iloczyn=0;
for(int i=1;i<=a;++i) iloczyn+=b;

Czy może jednak:

int iloczyn=a*b;

Skoro wybierasz dłuższy kod z większą złożonością to podejrzewam że wybierzesz wariant pierwszy!

@_13th_Dragon: Wybiorę wariant

int iloczyn=a*b

bo jest prostszy :)

lookacode1 napisał(a):

@_13th_Dragon: Wybiorę wariant

Kopiuj

int iloczyn=a*b

bo jest prostszy :)

To czemu wybierasz:

long x = (long) Math.pow(2, i);

zamiast:

long x = 1<<i;

_13th_Dragon napisał(a):

lookacode1 napisał(a):

@_13th_Dragon: Wybiorę wariant

Kopiuj

int iloczyn=a*b

bo jest prostszy :)

To czemu wybierasz:

Kopiuj

long x = (long) Math.pow(2, i);

zamiast:

Kopiuj

long x = 1<<i;

Za pierwszym razem na to nie wpadłem robiłem na szybko, twoje rozwiązanie jest lepsze, teraz wybrałbym

long x = 1<<i;

;)

Jednak myślę, że autorowi pytania przydadzą się różne podejścia do tematu.

To chyba bardziej problem matematyczny:). A i rodzaj pętli while czy for nie ma znaczenia.

class Main {

  static void powerOfTwoLessThan(int n) {
    for (int i = 0; i <= Math.floor(Math.log(n)/ Math.log(2)); i++)
      System.out.println((long)Math.pow(2, i));
  }

  public static void main(String[] args) {
    powerOfTwoLessThan(71);
  }
}

EDIT: Zoptymalizowana wersja, zgodnie z sugestiami komentatorów:

class Main {

  static void powerOfTwoLessThan(int n) {
    double limit = Math.floor(Math.log(n)/ Math.log(2));
    for (int i = 0; i <= limit; i++)
      System.out.println(1 << i);
  }

  public static void main(String[] args) {
    powerOfTwoLessThan(71);
  }
}

    for(int i=1;potega<=n;i++){
        potega=potega*2;
        System.out.println(potega);
    }

Problem tutaj leży w tym, że sprawdzasz, czy zmienna 'potega' jest mniejsza lub równa zminnej 'n', potem ją mnożysz, a potem wyświetlasz. Zamień linijki potega=potega*2 i printa, i nie będzie Ci wyświetlać tej ostatniej niechcianej wartości.
A poza tym jeżeli chcesz użyć pętli for to możesz zrobić tak:

for(int potega = 1; potega <= n; potega *= 2) {
    System.out.println(potega);
}

Bo Twoja obecna pętla działa jak while, tylko z niepotrzebną zmienną i.