right cyclic shift

0

Witam. Mam drobny problem. Poniżej jest kod sprawdzający po którym przesunięciu bitów w prawo liczby 30-bitowej uzyskamy największą liczbę. Jak dla mnie działa on dobrze ale ponoć jest w nim jakiś błąd. Proszę o wskazanie tego błędu. Z góry dziękuję.

#include <iostream>
using namespace std;

int main(int argc, char** argv) {
    int N;
    cin >> N;

    int lar = 0;
    int shift = 0;
    int temp = N;
    for (int i = 1; i < 30; i++)
    {
        int index = (temp & 1);
        temp = ((temp >> 1) | (index << 29));
        if (temp > lar)
        {
            lar = temp;
            shift = i;
        }
    }
    return shift;
} 
1

a co z ujemnymi?

1

W standardzie C i C++ masz gwarancję że int będzie zajmował nie mniej niż 16 bitów.
Nie możesz być pewien że int będzie na 32 bitach (co niejawnie założyłeś). Do takich prac lepiej użyć <cstdint>
Następna sprawa to traktowanie liczb ujemnych. Nic z tym nie robisz.
Dalej pytanie czy osoba która Ci powiedziała "że źle", miała na myśli także wprowadzone niepoprawne dane ("nie liczba").

Już nie będę otwierał nowej odpowiedzi. Jeszcze zamaskuj temp bo "łapiesz" górne bity.. w operacji temp = ((temp >> 1) | (index << 29));

1

Zamień:

int lar = 0;

Na:

int lar = N;
0

Przepraszam ale zapomniałem dodać, że N jest liczbą dodatnią trzydziesto bitową, nie mam takiej gwarancji ale możemy tak założyć. Błąd dotyczy wyniku, założenie jest takie, że dane wprowadzana zawsze są poprawne. Do tego ten błąd należy poprawić zmieniając nie więcej niż 2 linijki kodu.

Wibowit, wielkie dzięki. W sumie to może być to.

0

Mimo zamknięcia tematu.. wydaje mi się że to jest poprawne:

#include <iostream>
#include <cstdint>

using namespace std;

int main(void) {
    uint32_t N;
    cin >> N;

    uint32_t lar = 0;
    uint32_t shift = 0;
    uint32_t temp = N & ((1 << 30) - 1);
    for (int i = 1; i < 30; i++)
    {
        uint32_t index = (temp & 1);
        temp = ((temp >> 1) | (index << 29));
        if (temp > lar)
        {
            lar = temp;
            shift = i;
        }
    }
    return shift;
}

Ale jak nie.. to chętnie się przychylę...

0

Znalazłem jeszcze inny błąd (tzn tak myślę, że to jest błąd). Zamiast:

return shift;

Daj:

cout << shift;

;)

@Mokrowski:
Twój kod z przykładem na którym się wywala: http://ideone.com/3iiXzi Dało wynik 1, a powinno dać 0. Z moją poprawką daje poprawny wynik: http://ideone.com/rT3BlM

0

No ja to widzę tak.. na szybko i bez dodawania zewnętrznych bibliotek testujących.. Kod jest poprawny składniowo i ideone wyrzuca na nim błąd.. jeśli nie jest uruchomiona C++14

#include <iostream>
#include <cstdint>
#include <cassert>
#include <cmath>

using namespace std;

uint8_t shifted(uint32_t value, uint8_t bits) {
    // Zamienić na samo value i sprawdzić... 
    uint32_t lar = value & ((1 << bits) - 1);
    uint32_t shift = 0;
    uint32_t temp = lar;
    for (int i = 1; i < bits; i++)
    {
        uint32_t index = (temp & 1);
        temp = ((temp >> 1) | (index << (bits - 1)));
        if (temp > lar)
        {
            lar = temp;
            shift = i;
        }
    }
    return shift;
}

int main(void) {
    uint32_t value = pow(2, 30) + 7;
    assert(3 == shifted(value, 30));
    value = pow(2, 29) + 7;
    assert(3 == shifted(value, 30));
    value = pow(2, 30) - 1;
    assert(0 == shifted(value, 30));
    value = (pow(2, 30) - 1) - pow(2, 29);
    assert(29 == shifted(value, 30));
}

Okazuje się że obaj mamy rację... Ja zakładając że maska jest potrzebna i ty co do lar. Ale w tym lar ma być maska.

1
  1. Kombinowanie z maską jest zupełnie niepotrzebne. Dane wejściowe mają być poprawne, więc po co je poprawiać?
  2. W komentarzu napisałem, że testowe liczby mają być postaci pow(2, 30) - pow(2, X) dla X > 0, a ty dajesz pow(2, 30) + 7.
  3. Widzę, że w końcu zaaplikowałeś moją poprawkę. Z nią procedura działa prawidłowo.
  4. Błąd jest dokładnie opisany przez kompilator: error: #error This file requires compiler and library support for the ISO C++ 2011 standard. Stąd włączenie C++14 samo się narzuca (bo C++11 nie jest dostępne, a standardy są wstecznie kompatybilne).
  5. pow(2, 30) + 7 przekracza zakres poprawnych wartości wejściowych.
0

Ogólnie wielkie dzięki za zaangażowanie się w temat.

Return nie jest problemem, to jest bardziej formalność.

Co do kodu, to błąd, który w nim jest został specjalny stworzony przez autora gdyż było to zadanie na poprawę kodu. Wniosek z tego taki, że po poprawie maks. dwóch linijek musi działać poprawnie. Wydaje mi się, że chodzi tu tylko o tą poprawkę Wibowita.

Mam jeszcze tylko pytanie co sądzicie, o tym żeby zamiast zmieniać z

 lar = 0; 

na lar = N;

 zrobić <code class="cpp">for (int i = 1; i < 31; i++) 

zamiast for (int i = 1; i < 30; i++)

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