Zbliżenie 'n' do najbliższej potęgi 2.

0

Jak stworzyć program, który będzie pobierał n i następnie zamieni ją na najbliższą potęgę dwójki, większą od 'n'? Bardzo proszę o podawanie rozwiązań w CPP.

PS: Jeżeli ktoś nie wie o co chodzi to pokażę na przykładzie:
Jeżeli n = 9 to po "zbliżeniu" n = 16 (bo to najbliższa potęga 2, większa od 2)
Jeżeli n = 63 to po "zbliżeniu" n = 64

4

Możesz zastosować różne sztuczki opisane tutaj: http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2Float

Matematycznie: n_c = 2^{\lceil \log_2{n}\rceil} i ten wzór można sobie normalnie zaimplementować.

1

Najprostsze do zrozumienia:
int sh=0;
while(n>>=1) ++sh;
n=1<<sh;

0

Najbardziej wydajne, ale czy na pewno najłatwiejsze do zrozumienia?

int sh = 1;
while(sh<=n)
  sh = sh*2;
0

większą od 'n'?
to jest chyba zły warunek, raczej powinno być „większą lub równą”.

1
bogdans napisał(a):

Najbardziej wydajne ...
Otóż nie jest to najbardziej wydajne, bo jest bardziej wydajne:

int p=1;
while(n) { p=n<<1; n&=n-1; }

Akurat tu jest spełniony warunek - "większa od n", dla warunku "nie mniejsza od n" potrzebny dodatkowy licznik kroków. Jeżeli pętla zrobiła tylko 1 krok to wynikiem jest samo p, jeżeli więcej to wynikiem jest p<<1. Czyli:

int p=1;
if(n) { p=n; n&=n-1; }
while(n) { p=n<<1; n&=n-1; }
1

szybsze będzie (b zawsze równa się 1 na początku, a 'a' to nasza liczba do zaokrąglenia)

while(a) {a>>=1; b<<=1;};

bo nie ma jednego odejmowania

  1. żeby uniknąć tego, że np 16 po zaokrągleniu to 32 to wystarczy przed pętlą wykonać
--a

cały kod

    int a = 5, b = 1;
    --a;
    while(a) {a>>=1; b<<=1;};

problemem jest wtedy tylko zaokrąglanie zera.

0

Dzięki za pomoc :). Miło by było gdybyście jeszcze wyjaśnili mi dlaczego całe rozwiązanie wygląda właśnie tak (bo jestem średni w posługiwaniu się operatorami bitowymi). Aha, no i jeszcze jedno. Co oznacza "while(a)..."? To jest chyba pętla nieskończona.

1

pętla while wykonuje się dopóki wartość wyrażenia w nawiasach jest niezerowa. mój algorytm używa przesunięć bitowych z przypisaniem o jedno miejsce w lewo lub w prawo. To chyba wiesz. Teraz sobie wyciągnij kartkę, długopis i rozpisz poszczególne kroki algorytmu. Wtedy zrozumiesz lepiej niż jak Ci ktokolwiek by wytłumaczył

0

'a' to jest liczba do zbliżenia, prawda? Po wykonaniu programu dla a = 9 zwraca mi 0, kiedy poprawnie powinno zwracać 16.

0
  int a = 9, b = 1; //a to wartość do zbliżenia. b zawsze równa się jeden na początku
    --a;
    while(a) {a>>=1; b<<=1;};

to jest ten kod, kiedy zero spowoduje nieskończoną pętle.
Możesz zrobić zamiast --a;
if(a) --a

u mnie działa bez zarzutów, musiałeś coś namieszać

0

@Sopelek, twoja pętla wykona się n razy, gdzie n to pozycja najstarszego zapalonego bitu.
Pętla @_13th_Dragon wykona się k razy, gdzie k jest ilością zapalonych bitów.

Co będzie szybsze? Zależy...

Natomiast szybsze od jednego i drugiego będą obydwa algorytmy zawarte w linku od @Endrju (Bit Twiddling Hacks)

0

Program wykonuje się już dobrze i zwraca 16. Jako wynik wypisywałem 'a' i dlatego zwracało 0 :D.

1 użytkowników online, w tym zalogowanych: 0, gości: 1