Jak sprawdzić, czy liczba całkowita jest parzysta czy nieparzysta? [Zamknięte]


193

Jak mogę sprawdzić, czy podana liczba jest parzysta czy nieparzysta w C?


5
Wersja, która używa bitowego i (&) jest znacznie wydajniejsza niż wersja modulo (%). Powinieneś zmienić ten, który wybrałeś jako poprawną odpowiedź.
Stefan Rusek

6
Mało prawdopodobne - argument jest stały. Łatwo dla optymalizatora
MSalters

2
Na to również wpływa czytelność.
Brian G

2
W aplikacjach wbudowanych (świecie, w którym spędzam większość czasu na programowaniu), niektóre procesory mają bardzo prymitywne jednostki arytmetyczne i nie mogą łatwo wykonywać operacji dzielenia / modułu. Z tego powodu zwykle używam zamiast tego metody bitowej i. Jednak w przypadku procesora nowoczesnego komputera stacjonarnego tak nie będzie.
bta

3
Nigdy nie uważałem, że działanie modułu jest łatwiejsze do zrozumienia. Kiedy po raz pierwszy musiałem określić parzysty lub nieparzysty, bitowa maska ​​była pierwszą rzeczą, jaka przyszła mi do głowy. Jest to dość naturalne, ponieważ zwykle robimy to ręcznie, patrząc na najmniej znaczącą cyfrę, aby zobaczyć, czy jest w {0 2 4 6 8} lub {1 3 5 7 9}. To przekłada się bezpośrednio na spojrzenie na najmniej znaczący element, aby sprawdzić, czy jest to 0, czy 1.
P Daddy

Odpowiedzi:


449

Użyj operatora modulo (%), aby sprawdzić, czy pozostała część przy dzieleniu przez 2:

if (x % 2) { /* x is odd */ }

Kilka osób skrytykowało moją odpowiedź powyżej stwierdzając, że użycie x i 1 jest „szybsze” lub „bardziej wydajne”. Nie wierzę, żeby tak było.

Z ciekawości stworzyłem dwa trywialne programy przypadków testowych:

/* modulo.c */
#include <stdio.h>

int main(void)
{
    int x;
    for (x = 0; x < 10; x++)
        if (x % 2)
            printf("%d is odd\n", x);
    return 0;
}

/* and.c */
#include <stdio.h>

int main(void)
{
    int x;
    for (x = 0; x < 10; x++)
        if (x & 1)
            printf("%d is odd\n", x);
    return 0;
}

Następnie skompilowałem je z gcc 4.1.3 na jednym z moich komputerów 5 razy:

  • Bez flag optymalizacji.
  • Z -O
  • Z -Os
  • Z -O2
  • Z -O3

Przeanalizowałem dane wyjściowe asemblera każdego kompilacji (używając gcc -S) i stwierdziłem, że w każdym przypadku dane wyjściowe dla and.c i modulo.c były identyczne (oba używały instrukcji andl $ 1,% eax). Wątpię, aby była to „nowa” funkcja i podejrzewam, że pochodzi ona ze starożytnych wersji. Wątpię również, aby jakikolwiek nowoczesny (wyprodukowany w ciągu ostatnich 20 lat) nie-magiczny kompilator, komercyjny lub open source, nie miałby takiej optymalizacji. Testowałbym na innych kompilatorach, ale w tej chwili nie mam żadnych dostępnych.

Jeśli ktoś chciałby przetestować inne kompilatory i / lub cele platformy i uzyskałby inny wynik, byłbym bardzo zainteresowany.

Wreszcie, wersja modulo jest gwarantowana przez standard do działania niezależnie od tego, czy liczba całkowita jest dodatnia, ujemna czy zerowa, niezależnie od reprezentacji implementacji podpisanych liczb całkowitych. Wersja bitowa i wersja nie jest. Tak, zdaję sobie sprawę, że uzupełnienie dwóch jest dość wszechobecne, więc to nie jest tak naprawdę problem.


11
Pytanie konkretnie dotyczyło tego, jak to zrobić w C, więc odpowiedziałem na nie w C, mimo że chustar wspomniał, że nie potrafią tego zrobić w Javie. Nie twierdziłem ani nie sugerowałem, że to była odpowiedź Java, nie znam Java. Myślę, że właśnie dostałem swój pierwszy głos i jestem zdezorientowany, dlaczego. No cóż.
Chris Young,

33
Powiedziałbym, że jeśli (x% 2! = 0) {/ * x jest nieparzysty * /}, ale kto wie. Nie znam też java.
eugensk

9
Otrzymuje się wiele pozytywnych opinii, aby odróżnić go od kretynów operatora bitowego, bez konieczności wydawania naszej karmy na ich głosowanie.
wnoise

13
Zgadzam się ze wszystkim, z wyjątkiem jednej rzeczy: lubię trzymać liczby całkowite i wartości prawdy osobno, koncepcyjnie, więc wolę pisać „if (x% 2 == 1)”. To samo dotyczy kompilatora, ale być może jest nieco jaśniejsze dla ludzi. Ponadto możesz używać tego samego kodu w językach, które nie interpretują wartości niezerowej jako prawdziwej.
Thomas Padron-McCarthy

46
Mój punkt odniesienia? Jaki punkt odniesienia? Nie przeprowadziłem żadnych testów porównawczych. Sprawdziłem wygenerowany język asemblera. Nie ma to absolutnie nic wspólnego z printf.
Chris Young,

207

Jesteście zbyt skuteczni. Naprawdę chcesz:

public boolean isOdd(int num) {
  int i = 0;
  boolean odd = false;

  while (i != num) {
    odd = !odd;
    i = i + 1;
  }

  return odd;
}

Powtórz dla isEven.

Oczywiście nie działa to dla liczb ujemnych. Ale z blaskiem przychodzi poświęcenie ...


17
Jeśli rzuciłeś wyjątek argumentu na wartości ujemne i zauważyłeś w dokumentacji, że ta funkcja to O (N), to dobrze by mi było.
Jeffrey L Whitledge

7
Wersja korporacyjna musiałaby korzystać z XML. Oczywiście w dzisiejszych czasach będziesz mieć usługę internetową, którą możesz zapytać
Martin Beckett

58
Powinieneś to zoptymalizować za pomocą tabeli przeglądowej.
Weeble

1
Jestem takim mnichem, musiałem dać +1 6999 powtórzeniom w nowe tysiąclecie
Eran Medan

7
To jest genialne! Mój szef powiedział mi, że mamy wściekłego klienta, ponieważ uważał, że jego licencja dla przedsiębiorstw nie daje nic więcej niż licencja standardowa. Teraz dodaliśmy tę funkcję do naszego programu i tylko dlatego, że działa ona wolniej, uważa, że ​​jego oprogramowanie wykonuje O WIELE więcej pracy !!!
Phil

97

Użyj arytmetyki bitów:

if((x & 1) == 0)
    printf("EVEN!\n");
else
    printf("ODD!\n");

Jest to szybsze niż stosowanie podziału lub modułu.


43
Nie sądzę, że można powiedzieć, że jest szybszy niż użycie podziału lub modułu. Standard C nie mówi nic o wydajności operatorów, a każdy przyzwoity kompilator wygeneruje szybki kod dla obu. Osobiście wybrałbym idiom, który przekazuje moją intencję, a% wydaje się tutaj bardziej odpowiedni
Chris Young,

21
Bardziej lubię (x i 1), ponieważ sprawdza, czy liczba jest taka sama, jak ludzie: sprawdź, czy ostatnia cyfra jest parzysta czy nieparzysta. Moim zdaniem przekazuje swoje zamiary bardziej niż metodę modulo. (Nie żeby to miało znaczenie.)
Jeremy Ruten

2
Masz rację, myślę, że to subiektywne. Chociaż zwykła definicja „parzystej” to „liczba całkowita, którą można podzielić przez 2”, a nie „liczba całkowita, która kończy się na 0, 2, 4, 6 lub 8”. :-)
Chris Young,

4
@TraumaPony - dla ANSI standard C i wczesnej Java, zależy od systemu komputerowego. Nie jest określone, jaką reprezentację stosuje się dla liczb podpisanych - komplement 2, komplement 1, kod szary itp. Ale moduł jest zawsze modułem
Aaron

9
Nie działa uniwersalnie dla liczb ujemnych. Zobacz Sprawdź tę odpowiedź, aby uzyskać więcej szczegółów: stackoverflow.com/questions/160930/... w celu uzyskania szczegółowych informacji.
Andrew Edgecombe

36

[Joke mode = "on"]

public enum Evenness
{
  Unknown = 0,
  Even = 1,
  Odd = 2
}

public static Evenness AnalyzeEvenness(object o)
{

  if (o == null)
    return Evenness.Unknown;

  string foo = o.ToString();

  if (String.IsNullOrEmpty(foo))
    return Evenness.Unknown;

  char bar = foo[foo.Length - 1];

  switch (bar)
  {
     case '0':
     case '2':
     case '4':
     case '6':
     case '8':
       return Evenness.Even;
     case '1':
     case '3':
     case '5':
     case '7':
     case '9':
       return Evenness.Odd;
     default:
       return Evenness.Unknown;
  }
}

[Joke mode = „off”]

EDYCJA: Dodano mylące wartości do wyliczenia.


2
Wow ... to jest bardziej szalone niż rozwiązanie SCdF! Sława! Ale nie ma głosowania ... nie mogę tego polecić. Ale dzięki za śmieszne!
Wes P

1
Zaletą tego podejścia jest to, że działa z więcej niż tylko liczbami. Ponadto, jeśli zastąpisz ten wiersz: char bar = foo [foo.Length - 1]; z tym: double bar = Char.GetNumericValue (foo [foo.Length - 1]); Wtedy będzie działać z dowolnym systemem liczbowym.
Jeffrey L Whitledge

5
raport o błędzie: 14.65 jest zgłaszany jako nieparzysty, kiedy powinien być nieznany.
TheSoftwareJedi

4
Oprogramowanie Jedi, to „funkcja”. ;)
Sklivvz

31
TheSoftwareJedi: 14.65 jest jedną z najdziwniejszych liczb całkowitych, jakie kiedykolwiek widziałem.
Bruce Alderman,

16

W odpowiedzi na ffpf - przed laty miałem dokładnie taki sam argument z kolegą, a odpowiedź brzmi: nie , to nie działa z liczbami ujemnymi.

Norma C stanowi, że liczby ujemne można przedstawić na 3 sposoby:

  • Uzupełnienie 2
  • Uzupełnienie 1
  • znak i wielkość

Sprawdzanie w ten sposób:

isEven = (x & 1);

będzie działać dla uzupełnienia 2 i reprezentacji znaku i wielkości, ale nie będzie dla uzupełnienia 2.

Uważam jednak, że następujące elementy będą działać we wszystkich przypadkach:

isEven = (x & 1) ^ ((-1 & 1) | ((x < 0) ? 0 : 1)));

Dzięki ffpf za wskazanie, że pole tekstowe zjadło wszystko po mojej mniejszej niż postać!


Myślę, że w twoim drugim przykładzie kodu brakuje tekstu.
Jeff Yates

3
Uzupełnijmy te liczby!
thejh

14

Fajny to:

/*forward declaration, C compiles in one pass*/
bool isOdd(unsigned int n);

bool isEven(unsigned int n)
{
  if (n == 0) 
    return true ;  // I know 0 is even
  else
    return isOdd(n-1) ; // n is even if n-1 is odd
}

bool isOdd(unsigned int n)
{
  if (n == 0)
    return false ;
  else
    return isEven(n-1) ; // n is odd if n-1 is even
}

Zauważ, że ta metoda wykorzystuje rekurencję ogona obejmującą dwie funkcje. Może być efektywnie zaimplementowany (zamieniony w rodzaj pętli while / till), jeśli twój kompilator obsługuje rekurencję ogona jak kompilator Scheme. W takim przypadku stos nie powinien się przepełnić!


1
To nie obsługuje dobrze isOdd (0).
Steve McLeod

1
Myślę, że masz nieskończoną pętlę (z rekurencją ogona) lub przepełnienie stosu (bez rekurencji ogona) dla isOdd () z dowolnymi wartościami parzystymi lub isEven () z dowolnymi wartościami nieparzystymi. Kończy się tylko z prawdą. To znowu problem zatrzymania.
Jeffrey L. Whitledge

7
Och, jasne, napraw to bez komentarza i spraw, żebym wyglądał jak idiota. W porządku.
Jeffrey L Whitledge

1
Wystąpił błąd kompilacji: w isEven nie wszystkie ścieżki kodu zwracają wartość. Nie, tak naprawdę nie próbowałem tego kodu, to kompilator w mojej głowie narzeka.
Jeffrey L Whitledge

5
błąd kompilacji: nie wszystkie ścieżki zwracają wartość nienawiści do bombardowania cię komentarzami do twojego przykładowego kodu, ale to, co dzieje się, gdy wywołujesz, to Even (5)
Kevin

11

Liczba jest nawet wtedy, gdy podzielona przez dwa, reszta wynosi 0. Liczba jest nieparzysta, jeśli podzielona przez 2, reszta to 1.

// Java
public static boolean isOdd(int num){
    return num % 2 != 0;
}

/* C */
int isOdd(int num){
    return num % 2;
}

Metody są świetne!


Twoja metoda Java jest zepsuta, ponieważ num% 2 == -1 dla ujemnych liczb nieparzystych.
WMR

Czy dlatego mnie głosowałeś?
jjnguy

3
Zanotowałem to, ponieważ twoja funkcja w C zajmuje więcej znaków niż to, co robi. IE num% I ma 7 znaków, w tym spacje IsOdd (I) to 8 znaków. Dlaczego miałbyś stworzyć funkcję, która będzie dłuższa niż sama operacja?
Kevin

13
@Kevin moim zdaniem kod nie jest mierzony przez znaki, ale raczej przez czas, jaki zajmuje napisanie go, włączając myślenie + czas debugowania. num% 2 zajmuje milisekundę więcej niż isOdd. teraz dodaj liczby globalnie, a stracisz rok zbiorowy. również isOdd może być testowany i weryfikowany, a ostatecznie certyfikowany bezbłędnie (np. obsługa liczb ujemnych), gdzie jako num% 2 - niektórzy programiści zawsze będą mieli wątpliwości i będą eksperymentować. dobry kod to kod, którego nie piszesz, wystarczy ponownie użyć ... tylko moje 2 centy.
Eran Medan

2
@EranMedan, Ta sama logika dotyczyłaby zastąpienia i ++ przez IncrementByOne (i) i jest to równie zły pomysł. Jeśli programista ma wątpliwości co do tego, co robi num% 2, nie chcę, aby był on blisko mojego kodu.
Kevin


7

Powiedziałbym, po prostu podziel go przez 2, a jeśli pozostała 0, to jest parzysta, w przeciwnym razie jest nieparzysta.

Użycie modułu (%) ułatwia to.

na przykład. 4% 2 = 0, więc 4 to parzyste 5% 2 = 1, więc 5 jest nieparzyste


6

Jeszcze jedno rozwiązanie problemu
(dzieci mogą głosować)

bool isEven(unsigned int x)
{
  unsigned int half1 = 0, half2 = 0;
  while (x)
  {
     if (x) { half1++; x--; }
     if (x) { half2++; x--; }

  }
  return half1 == half2;
}

Nie, nie jesteś rodzajem dziecka, na które
liczyłem

Chciałem to poprzeć, ale przy liczbach ujemnych jest to trochę powolne. :)
Chris Young,

3
Wszystkie liczby są jasne i dodatnie. Czy jesteś uprzedzony wobec niektórych? :))
eugensk

3
W komputerach wszystkie liczby raz ujemne, ostatecznie stają się dodatnie. Nazywamy to rolowaniem szczęścia (nie dotyczy BIGNUMS, YMMY, nie obowiązuje we wszystkich stanach).
Will Hartung,

@WillHartung „kumulacja szczęścia” jest świetna! : D
thejh

6

Zbudowałbym tabelę parzystości (0, jeśli nawet 1, jeśli nieparzysta) liczb całkowitych (aby można było sprawdzić: D), ale gcc nie pozwala mi tworzyć tablic o takich rozmiarach:

typedef unsigned int uint;

char parity_uint [UINT_MAX];
char parity_sint_shifted [((uint) INT_MAX) + ((uint) abs (INT_MIN))];
char* parity_sint = parity_sint_shifted - INT_MIN;

void build_parity_tables () {
    char parity = 0;
    unsigned int ui;
    for (ui = 1; ui <= UINT_MAX; ++ui) {
        parity_uint [ui - 1] = parity;
        parity = !parity;
    }
    parity = 0;
    int si;
    for (si = 1; si <= INT_MAX; ++si) {
        parity_sint [si - 1] = parity;
        parity = !parity;
    }
    parity = 1;
    for (si = -1; si >= INT_MIN; --si) {
        parity_sint [si] = parity;
        parity = !parity;
    }
}

char uparity (unsigned int n) {
    if (n == 0) {
        return 0;
    }
    return parity_uint [n - 1];
}

char sparity (int n) {
    if (n == 0) {
        return 0;
    }
    if (n < 0) {
        ++n;
    }
    return parity_sint [n - 1];
}

Zamiast tego skorzystajmy z matematycznej definicji parzystej i nieparzystej.

Liczba całkowita n jest nawet wtedy, gdy istnieje liczba całkowita k taka, że ​​n = 2k.

Liczba całkowita n jest nieparzysta, jeśli istnieje liczba całkowita k taka, że ​​n = 2k + 1.

Oto jego kod:

char even (int n) {
    int k;
    for (k = INT_MIN; k <= INT_MAX; ++k) {
        if (n == 2 * k) {
            return 1;
        }
    }
    return 0;
}

char odd (int n) {
    int k;
    for (k = INT_MIN; k <= INT_MAX; ++k) {
        if (n == 2 * k + 1) {
            return 1;
        }
    }
    return 0;
}

Niech liczby całkowite C oznaczają możliwe wartości intw danej kompilacji C. (Zauważ, że liczby całkowite C to podzbiór liczb całkowitych.)

Teraz można się martwić, że dla danego n liczb całkowitych C odpowiednia liczba całkowita k może nie istnieć w liczbach całkowitych C. Ale z niewielkim dowodem można wykazać, że dla wszystkich liczb całkowitych n, | n | <= | 2n | (*), gdzie | n | oznacza „n, jeśli n jest dodatnie, a -n w przeciwnym razie”. Innymi słowy, dla wszystkich n liczb całkowitych przynajmniej jeden z następujących bloków (dokładnie albo przypadki (1 i 2) albo przypadki (3 i 4) w rzeczywistości, ale nie udowodnię tego tutaj):

Przypadek 1: n <= 2n.

Przypadek 2: -n <= -2n.

Przypadek 3: -n <= 2n.

Przypadek 4: n <= -2n.

Teraz weź 2k = n. (Taki ak istnieje, jeśli n jest parzyste, ale nie udowodnię tego tutaj. Jeśli n nie jest nawet, to i tak pętla evennie wraca wcześniej, więc to nie ma znaczenia.) Ale to implikuje k <n, jeśli n nie 0 przez (*), a fakt (ponownie tutaj nie udowodniony), że dla wszystkich m, z w liczbach całkowitych 2m = z oznacza, że ​​z nie równe m dane m nie wynosi 0. W przypadku, gdy n wynosi 0, 2 * 0 = 0 więc 0 jest nawet skończone (jeśli n = 0, wówczas 0 jest w liczbach całkowitych C, ponieważ n jest w liczbie całkowitej C w funkcji even, stąd k = 0 jest w liczbach całkowitych C). Zatem taki ak w liczbach całkowitych C istnieje dla nw liczbach całkowitych C, jeśli n jest parzyste.

Podobny argument pokazuje, że jeśli n jest nieparzyste, to w liczbach całkowitych C istnieje ak, że n = 2k + 1.

Dlatego funkcje eveni oddprzedstawione tutaj będą działać poprawnie dla wszystkich liczb całkowitych C.


1
Nie chodzi mi o obrazę, ale jaki jest sens tej odpowiedzi? i % 2jest znacznie mniejszy i prawdopodobnie bardziej wydajny.
GManNickG

2
@GMan: Ale to jest zdecydowanie bardziej deterministyczne! Działa to poprawnie wykrywając wszystkie przypadki krawędzi.
P Daddy

1
... I (!!!) jest poprawne !!!
Thomas Eding

Nie wiem, czy żartujesz, czy nie. : X %2działa dla wszystkich liczb całkowitych.
GManNickG

1
+1: Chciałem powiedzieć „dobra odpowiedź”, ale myślę, że „interesująca odpowiedź” jest bardziej odpowiednia.
James Webster

5
// C#
bool isEven = ((i % 2) == 0);

2
Co? To nie jest C #! To czyste C! :-P
asterite

8
Rzucę wokół niego WinForm, aby był czysty C # ...
Michael Petrotta

@mateusza: Zwykle, gdy widzisz „bool” W niektórych liter lub innych w C, to jest typedefalbo #defineczy coś.
David Thornley,

2
@mateusza @Didid Thornley W C99 bool jest standardową funkcją ( en.wikipedia.org/wiki/Stdbool.h )
fortran

1
Mów o ogromnie niepotrzebnych nawiasach ...
Thomas Eding

4

Oto odpowiedź w Javie:

public static boolean isEven (Integer Number) {
    Pattern number = Pattern.compile("^.*?(?:[02]|8|(?:6|4))$");
    String num = Number.toString(Number);
    Boolean numbr = new Boolean(number.matcher(num).matches());
    return numbr.booleanValue();
}

4

Spróbuj tego: return (((a>>1)<<1) == a)

Przykład:

a     =  10101011
-----------------
a>>1 --> 01010101
a<<1 --> 10101010

b     =  10011100
-----------------
b>>1 --> 01001110
b<<1 --> 10011100

Czy możesz to wyjaśnić? Bardzo nie znam operatorów bitowych
Abdul,

Przesunięcie w prawo, a następnie w lewo wyzeruje twój ostatni bit (najbardziej prawy). Jeśli nowy numer jest taki sam jak oryginał, oznacza to, że ostatni bit oryginalnego numeru wynosił 0. Więc jest parzysty. Spójrz na moją zaktualizowaną odpowiedź.
Kiril Aleksandrov,

dzięki, rozumiem teraz
Abdul,

Nie jestem pewien, które podejście jest szybsze. Nie próbowałem ich porównywać.
Kiril Aleksandrov,

Czy to również nie zeruje twojego najważniejszego bitu? Problem z niepodpisanymi intami w niektórych językach i negatywnymi intami w większości ...
Troyseph,

4

Czytając tę ​​raczej zabawną dyskusję, przypomniałem sobie, że miałem rzeczywistą funkcję wrażliwą na czas, która testowała nieparzyste i parzyste liczby w głównej pętli. Jest to funkcja zasilania liczb całkowitych, opublikowana w innym miejscu na StackOverflow, w następujący sposób. Testy były dość zaskakujące. Przynajmniej w tej funkcji w świecie rzeczywistym modulo działa wolniej i to znacznie. Zwycięzca, z dużym marginesem, wymagający 67% czasu modulo, jest podejściem lub (|) i nigdzie indziej na tej stronie nie ma.

static dbl  IntPow(dbl st0, int x)  {
    UINT OrMask = UINT_MAX -1;
    dbl  st1=1.0;
    if(0==x) return (dbl)1.0;

    while(1 != x)   {
        if (UINT_MAX == (x|OrMask)) {     //  if LSB is 1...    
        //if(x & 1) {
        //if(x % 2) {
            st1 *= st0;
        }    
        x = x >> 1;  // shift x right 1 bit...  
        st0 *= st0;
    }
    return st1 * st0;
}

W przypadku 300 milionów pętli czasy testów porównawczych są następujące.

3.962 | i podejście do maski

4.851 podejście i

5 850 podejście procentowe

Dla osób, które myślą, że teoria lub lista języków asemblacyjnych rozstrzygają takie argumenty, powinna to być przestroga. W niebie i na ziemi jest więcej rzeczy, Horatio, niż marzysz w swojej filozofii.


1
Lepsze w użyciu, unsigned xponieważ x = x >> 1;jest to zachowanie zdefiniowane podczas implementacji x < 0. Niejasne, dlaczego xi OrMaskróżnią się rodzajem. Wystarczająco proste, aby ponownie napisać za pomocą while(x)testu.
chux - Przywróć Monikę

2
Zastanawiam się, którego kompilatora użyłeś do przetestowania tego, ponieważ większość kompilatorów powinna być wystarczająco inteligentna, aby skompilować % 2sprawę za pomocą bitowej &. Właśnie to przetestowałem i wyniki są całkowicie takie same (VS2015, wersje kompilacji ze wszystkimi optymalizacjami, zarówno x86, jak i x64). W przyjętej odpowiedzi podano to również w przypadku GCC (napisane w 2008 r.).
Lou

2
Problem z tym postem polega na tym, że założenie, że bitowe orbyłoby szybsze niż an, andjest bardzo mało prawdopodobne na jakiejkolwiek platformie / kompilatorze. Nawet gdyby istniała taka dziwna kombinacja platforma / kompilator (i nie opublikowałeś ani tego, ani kodu użytego do przeprowadzenia testu porównawczego), zależnie od innych kompilatorów, aby zachowywać się tak samo, byłby kiepski zakład optymalizacyjny. Tak więc, jak napisałem, zastanawiam się, na której platformie / kompilatorze był testowany , ponieważ jestem prawie pewien, że nie został poprawnie zmierzony.
Lou

2
Nie nazywając cię kłamcą, po prostu twierdząc z dużą pewnością, że nie zmierzyłeś poprawnie. Nie muszę jeszcze nazywać mnie kierowcą ciężarówki, przeczytaj mój oryginalny komentarz: zrobiłem punkt odniesienia, a wyniki były, zgodnie z oczekiwaniami, całkowicie takie same we wszystkich trzech przypadkach (pewność ~ 3 sigma, po każdym uruchomieniu każdego testu 10 razy za 500 000 .000 iteracji). Jeśli naprawdę masz długą, wybitną karierę, cofnij się o krok i zastanów się, czy twoje roszczenia mają sens, a następnie opublikuj rzeczywisty kod użyty do przeprowadzenia testu porównawczego. W przeciwnym razie post jest tym, co moim zdaniem, tylko pomyłką w pomiarze.
Lou


4

Jest to kontynuacja dyskusji z @RocketRoy na temat jego odpowiedzi , ale może być przydatna dla każdego, kto chce porównać te wyniki.

tl; dr Z tego, co widziałem, podejście Roya ( (0xFFFFFFFF == (x | 0xFFFFFFFE)) nie jest całkowicie zoptymalizowane x & 1jako modpodejście, ale w praktyce czasy działania powinny być takie same we wszystkich przypadkach.

Najpierw porównałem skompilowane dane wyjściowe za pomocą Eksploratora kompilatorów :

Testowane funkcje:

int isOdd_mod(unsigned x) {
    return (x % 2);
}

int isOdd_and(unsigned x) {
    return (x & 1);
}

int isOdd_or(unsigned x) {
    return (0xFFFFFFFF == (x | 0xFFFFFFFE));
}   

CLang 3.9.0 z -O3:

isOdd_mod(unsigned int):                          # @isOdd_mod(unsigned int)
        and     edi, 1
        mov     eax, edi
        ret

isOdd_and(unsigned int):                          # @isOdd_and(unsigned int)
        and     edi, 1
        mov     eax, edi
        ret

isOdd_or(unsigned int):                           # @isOdd_or(unsigned int)
        and     edi, 1
        mov     eax, edi
        ret

GCC 6.2 z -O3:

isOdd_mod(unsigned int):
        mov     eax, edi
        and     eax, 1
        ret

isOdd_and(unsigned int):
        mov     eax, edi
        and     eax, 1
        ret

isOdd_or(unsigned int):
        or      edi, -2
        xor     eax, eax
        cmp     edi, -1
        sete    al
        ret

Czapki do CLanga, zdałem sobie sprawę, że wszystkie trzy przypadki są funkcjonalnie równe. Jednak podejście Roya nie jest zoptymalizowane w GCC, więc YMMV.

Podobnie jest z Visual Studio; sprawdzając wersję demontażową wydania x64 (VS2015) pod kątem tych trzech funkcji, zauważyłem, że część porównawcza jest równa dla przypadków „mod” i „i” oraz nieco większa dla przypadku „Roy” lub „”:

// x % 2
test bl,1  
je (some address) 

// x & 1
test bl,1  
je (some address) 

// Roy's bitwise or
mov eax,ebx  
or eax,0FFFFFFFEh  
cmp eax,0FFFFFFFFh  
jne (some address)

Jednak po uruchomieniu rzeczywistego testu porównawczego dla porównania tych trzech opcji (zwykły mod, bitowy lub bitowy i) wyniki były całkowicie równe (ponownie, Visual Studio 2005 x86 / x64, kompilacja wydania, bez dołączonego debuggera).

Zespół wydania używa testinstrukcji andi modprzypadków, podczas gdy sprawa Roya używa tego cmp eax,0FFFFFFFFhpodejścia, ale jest mocno rozwinięta i zoptymalizowana, więc nie ma różnicy w praktyce.

Moje wyniki po 20 uruchomieniach (i7 3610QM, plan zasilania systemu Windows 10 ustawiony na wysoką wydajność):

[Test: Plain mod 2] ŚREDNI CZAS: 689,29 ms (Różnica względna: + 0,000%)
[Test: Bitowy lub] CZAS ŚREDNI: 689,63 ms (Różnica względna: + 0,048%)
[Test: Bitowy i] CZAS ŚREDNI: 687,80 ms (Różnica względna: -0,217%)

Różnica między tymi opcjami wynosi mniej niż 0,3%, więc jest raczej oczywiste, że zespół jest jednakowy we wszystkich przypadkach.

Oto kod, jeśli ktoś chce spróbować, z zastrzeżeniem, że testowałem go tylko w systemie Windows (sprawdź #if LINUXwarunek dla get_timedefinicji i zaimplementuj ją w razie potrzeby, wzięty z tej odpowiedzi ).

#include <stdio.h>

#if LINUX
#include <sys/time.h>
#include <sys/resource.h>
double get_time()
{
    struct timeval t;
    struct timezone tzp;
    gettimeofday(&t, &tzp);
    return t.tv_sec + t.tv_usec*1e-6;
}
#else
#include <windows.h>
double get_time()
{
    LARGE_INTEGER t, f;
    QueryPerformanceCounter(&t);
    QueryPerformanceFrequency(&f);
    return (double)t.QuadPart / (double)f.QuadPart * 1000.0;
}
#endif

#define NUM_ITERATIONS (1000 * 1000 * 1000)

// using a macro to avoid function call overhead
#define Benchmark(accumulator, name, operation) { \
    double startTime = get_time(); \
    double dummySum = 0.0, elapsed; \
    int x; \
    for (x = 0; x < NUM_ITERATIONS; x++) { \
        if (operation) dummySum += x; \
    } \
    elapsed = get_time() - startTime; \
    accumulator += elapsed; \
    if (dummySum > 2000) \
        printf("[Test: %-12s] %0.2f ms\r\n", name, elapsed); \
}

void DumpAverage(char *test, double totalTime, double reference)
{
    printf("[Test: %-12s] AVERAGE TIME: %0.2f ms (Relative diff.: %+6.3f%%)\r\n",
        test, totalTime, (totalTime - reference) / reference * 100.0);
}

int main(void)
{
    int repeats = 20;
    double runningTimes[3] = { 0 };
    int k;

    for (k = 0; k < repeats; k++) {
        printf("Run %d of %d...\r\n", k + 1, repeats);
        Benchmark(runningTimes[0], "Plain mod 2", (x % 2));
        Benchmark(runningTimes[1], "Bitwise or", (0xFFFFFFFF == (x | 0xFFFFFFFE)));
        Benchmark(runningTimes[2], "Bitwise and", (x & 1));
    }

    {
        double reference = runningTimes[0] / repeats;
        printf("\r\n");
        DumpAverage("Plain mod 2", runningTimes[0] / repeats, reference);
        DumpAverage("Bitwise or", runningTimes[1] / repeats, reference);
        DumpAverage("Bitwise and", runningTimes[2] / repeats, reference);
    }

    getchar();

    return 0;
}

Wierzę, że popełniłeś grzech główny przy porównywaniu; stworzenie takiego tak specyficznego, że nie reprezentuje środowiska rzeczywistego. Spójrz na język asemblera i zauważ, jak mało rejestrów używasz. Wysokie noty za wysiłek, ale wyniki te nie wytrzymają w przetwarzaniu w świecie rzeczywistym.

@RocketRoy: ponieważ wszystkie wyjścia są dokładnie takie same dla wszystkich trzech przypadków (no cóż, nieco gorzej dla twojego programu w jednym przypadku), nie obchodzi mnie, ile rejestrów zostało użytych. Ale znowu, nie krępuj się stworzyć i opublikować taki przykładowy program / środowisko, które pomieszają kompilator w celu stworzenia bardziej zoptymalizowanego zestawu w jednym z przypadków, przy czym wszystkie inne rzeczy są takie same.
Lou

Zawsze lubię zarozumiałych programistów. Jest to dobra cecha dla programisty, ale w bardziej złożonym programie w świecie rzeczywistym moja metoda będzie działać lepiej niż Twoja, ponieważ kompilator ma więcej sposobów rozwiązania problemu, dzięki czemu instrukcje nakładają się (w architekturze Intela), dając lepsze wyniki . Bardzo niewielu doświadczonych programistów z dobrym doświadczeniem w testowaniu porównawczym wolałoby test porównawczy, ale kontynuuj dobrą pracę i pamiętaj o ponownym uruchomieniu testów porównawczych, gdy pojawią się nowe wersje układów. Z czasem rzeczy się zmieniają.

3

Wiem, że to tylko cukier syntaktyczny i ma zastosowanie tylko w .net, ale co z metodą rozszerzenia ...

public static class RudiGroblerExtensions
{
    public static bool IsOdd(this int i)
    {
        return ((i % 2) != 0);
    }
}

Teraz możesz wykonać następujące czynności

int i = 5;
if (i.IsOdd())
{
    // Do something...
}

1
Niezły kod. Szkoda, że ​​twierdzi, że 2 jest nieparzyste, a 3 nie.
Anthony

ups, przepraszam ... moja logika jest błędna ...
rudigrobler

3

W „kreatywnej, ale mylącej kategorii” oferuję:

int isOdd(int n) { return n ^ n * n ? isOdd(n * n) : n; }

Wariant tego motywu specyficzny dla Microsoft C ++:

__declspec(naked) bool __fastcall isOdd(const int x)
{
    __asm
    {
        mov eax,ecx
        mul eax
        mul eax
        mul eax
        mul eax
        mul eax
        mul eax
        ret
    }
}

2

Metoda bitowa zależy od wewnętrznej reprezentacji liczby całkowitej. Modulo będzie działać wszędzie tam, gdzie jest operator modulo. Na przykład niektóre systemy faktycznie używają bitów niskiego poziomu do znakowania (jak języki dynamiczne), więc surowe x & 1 tak naprawdę nie będzie działać w tym przypadku.


2

IsOdd (int x) {return true; }

Dowód poprawności - rozważ zestaw wszystkich dodatnich liczb całkowitych i załóżmy, że istnieje niepusty zbiór liczb całkowitych, które nie są nieparzyste. Ponieważ liczby całkowite dodatnie są dobrze uporządkowane, będzie najmniejsza nieparzysta liczba, która sama w sobie jest dość nieparzysta, więc wyraźnie, że liczba nie może być w zestawie. Dlatego ten zestaw nie może być niepusty. Powtórz dla liczb całkowitych ujemnych, z wyjątkiem szukania największej nieparzystej liczby.


2

Przenośny:

i % 2 ? odd : even;

Nieportowalne:

i & 1 ? odd : even;

i << (BITS_PER_INT - 1) ? odd : even;

2

Jak niektórzy napisali, istnieje wiele sposobów, aby to zrobić. Według tej strony najszybszym sposobem jest operator modułu:

if (x % 2 == 0)
               total += 1; //even number
        else
               total -= 1; //odd number

Oto jednak inny kod, który został zaznaczony przez autora, który działał wolniej niż zwykła operacja modułu powyżej:

if ((x & 1) == 0)
               total += 1; //even number
        else
               total -= 1; //odd number

System.Math.DivRem((long)x, (long)2, out outvalue);
        if ( outvalue == 0)
               total += 1; //even number
        else
               total -= 1; //odd number

if (((x / 2) * 2) == x)
               total += 1; //even number
        else
               total -= 1; //odd number

if (((x >> 1) << 1) == x)
               total += 1; //even number
        else
               total -= 1; //odd number

        while (index > 1)
               index -= 2;
        if (index == 0)
               total += 1; //even number
        else
               total -= 1; //odd number

tempstr = x.ToString();
        index = tempstr.Length - 1;
        //this assumes base 10
        if (tempstr[index] == '0' || tempstr[index] == '2' || tempstr[index] == '4' || tempstr[index] == '6' || tempstr[index] == '8')
               total += 1; //even number
        else
               total -= 1; //odd number

Ile osób wiedziało nawet o metodzie Math.System.DivRem lub dlaczego mieliby z niej korzystać?



1

Aby wyjaśnić bardziej szczegółowo metodę operatora bitowego dla tych z nas, którzy nie wykonywali zbyt wiele algebry boolowskiej podczas naszych badań, oto wyjaśnienie. Prawdopodobnie nie przydadzą się OP, ale chciałem wyjaśnić, dlaczego NUMBER i 1 działa.

Pamiętaj, tak jak ktoś odpowiedział powyżej, sposób reprezentowania liczb ujemnych może zatrzymać tę metodę. W rzeczywistości może nawet złamać metodę operatora modulo, ponieważ każdy język może różnić się sposobem radzenia sobie z ujemnymi operandami.

Jeśli jednak wiesz, że NUMBER zawsze będzie dodatni, działa to dobrze.

Jak Tooony powyżej wskazał, że ważna jest tylko ostatnia cyfra w formacie binarnym (i denary).

Logiczna logika logiczna AND oznacza, że ​​oba wejścia muszą mieć wartość 1 (lub wysokie napięcie), aby 1 mogło zostać zwrócone.

1 i 0 = 0.

0 i 1 = 0.

0 i 0 = 0.

1 i 1 = 1.

Jeśli reprezentujesz dowolną liczbę jako binarną (użyłem tutaj reprezentacji 8-bitowej), liczby nieparzyste mają 1 na końcu, liczby parzyste mają 0.

Na przykład:

1 = 00000001

2 = 00000010

3 = 00000011

4 = 00000100

Jeśli weźmiesz dowolną liczbę i użyjesz bitowego AND (& w java) o 1, to albo zwróci 00000001, = 1, co oznacza, że ​​liczba jest nieparzysta. Lub 00000000 = 0, co oznacza, że ​​liczba jest parzysta.

Na przykład

To jest dziwne?

1 i 1 =

00000001 i

00000001 =

00000001 <- Nieparzysty

2 i 1 =

00000010 i

00000001 =

00000000 <- Parzysty

54 i 1 =

00000001 i

00110110 =

00000000 <- Parzysty

Oto dlaczego to działa:

if(number & 1){

   //Number is odd

} else {

   //Number is even
}

Przepraszam, jeśli to jest zbędne.


1

Liczba Zero parzystości | zero http://tinyurl.com/oexhr3k

Sekwencja kodu w języku Python.

# defining function for number parity check
def parity(number):
    """Parity check function"""
    # if number is 0 (zero) return 'Zero neither ODD nor EVEN',
    # otherwise number&1, checking last bit, if 0, then EVEN, 
    # if 1, then ODD.
    return (number == 0 and 'Zero neither ODD nor EVEN') \
            or (number&1 and 'ODD' or 'EVEN')

# cycle trough numbers from 0 to 13 
for number in range(0, 14):
    print "{0:>4} : {0:08b} : {1:}".format(number, parity(number))

Wynik:

   0 : 00000000 : Zero neither ODD nor EVEN
   1 : 00000001 : ODD
   2 : 00000010 : EVEN
   3 : 00000011 : ODD
   4 : 00000100 : EVEN
   5 : 00000101 : ODD
   6 : 00000110 : EVEN
   7 : 00000111 : ODD
   8 : 00001000 : EVEN
   9 : 00001001 : ODD
  10 : 00001010 : EVEN
  11 : 00001011 : ODD
  12 : 00001100 : EVEN
  13 : 00001101 : ODD

@ el.pescado, Dziękujemy. Jeśli zero jest parzyste, ile ma par?

@ el.pescado, Ok, zgadzam się z Tobą. Zatem, jeśli zastanowić się trochę, dlaczego dzielimy na 2 (dwa)? Co chcemy wiedzieć, dzieląc na dwie części? Dlaczego nie podzielić na 3 lub 5 itd.?

@ el.pescado Ten artykuł w Wikipedii Parzystość zerowa jest nieprawidłowa. Ten artykuł oszukał wielu ludzi. Pomyśl przed Wink.

1
Masz rację. Teraz, gdy przeczytałem inne odpowiedzi, znalazłem twoje najbardziej wyczerpujące :)
el.pescado,

@ el.pescado. Dziękuję Ci. :) Teraz jesteś najlepszym przyjacielem Zero. (uścisk)

1
I execute this code for ODD & EVEN:

#include <stdio.h>
int main()
{
    int number;
    printf("Enter an integer: ");
    scanf("%d", &number);

    if(number % 2 == 0)
        printf("%d is even.", number);
    else
        printf("%d is odd.", number);
}

0

Ze względu na dyskusję ...

Wystarczy spojrzeć na ostatnią cyfrę w dowolnej liczbie, aby sprawdzić, czy jest parzysta czy nieparzysta. Podpisane, niepodpisane, pozytywne, negatywne - wszystkie są w tym zakresie takie same. Więc to powinno działać w całości: -

void tellMeIfItIsAnOddNumberPlease(int iToTest){
  int iLastDigit;
  iLastDigit = iToTest - (iToTest / 10 * 10);
  if (iLastDigit % 2 == 0){
    printf("The number %d is even!\n", iToTest);
  } else {
    printf("The number %d is odd!\n", iToTest);
  }
}

Klucz znajduje się tutaj w trzecim wierszu kodu, operator dzielenia dokonuje podziału na liczby całkowite, więc w wyniku brakuje części ułamkowej wyniku. Na przykład 222/10 da wynik 22. Następnie pomnóż go ponownie przez 10, a otrzymasz 220. Odejmij to od pierwotnego 222, a skończysz na 2, który według magii jest tą samą liczbą co ostatnia cyfra w pierwotnym numerze. ;-) Nawiasy służą przypomnieniu o kolejności wykonywania obliczeń. Najpierw dokonaj podziału i mnożenia, a następnie odejmij wynik od pierwotnej liczby. Moglibyśmy je pominąć, ponieważ priorytet jest wyższy dla dzielenia i mnożenia niż odejmowania, ale daje to nam „bardziej czytelny” kod.

Moglibyśmy sprawić, że wszystko byłoby całkowicie nieczytelne, gdybyśmy chcieli. Dla nowoczesnego kompilatora nie miałoby to żadnej różnicy:

printf("%d%s\n",iToTest,0==(iToTest-iToTest/10*10)%2?" is even":" is odd");

Ale w przyszłości kod byłby trudniejszy do utrzymania. Wyobraź sobie, że chciałbyś zmienić tekst liczb nieparzystych na „nie jest parzysty”. Potem ktoś później chce dowiedzieć się, jakie zmiany wprowadziłeś i wykonać svn diff lub podobny ...

Jeśli nie martwisz się przenośnością, ale bardziej szybkością, możesz spojrzeć na co najmniej znaczący element. Jeśli ten bit jest ustawiony na 1, jest to liczba nieparzysta, jeśli wynosi 0, jest to liczba parzysta. Na małym systemie endian, takim jak architektura x86 Intela, byłoby to mniej więcej tak:

if (iToTest & 1) {
  // Even
} else {
  // Odd
}

Co dokładnie jest złego w samym przejściu iToTest% 2 == 0? Marnujesz podział wyodrębniający ostatnią cyfrę, więc twój jest dwa razy wolniejszy, niż powinien.
spacja

@freespace: Marnuję więcej, prawda? :-) Mnożenie i odejmowanie też. Ale co jest najbardziej wydajne między tymi dwoma rozwiązaniami, których nie odważę się powiedzieć. Nigdy nie twierdziłem, że jest to najszybsze rozwiązanie, wręcz przeciwnie, jeśli ponownie przeczytasz pierwszą linię mojego postu.
Tooony,

@ Tooo, ah, mój kapelusz humoru odpadł. To jest teraz formalnie z powrotem: D Przepraszam za to :)
Freespace

0

Jeśli chcesz być wydajny, użyj operatorów bitowych ( x & 1), ale jeśli chcesz być czytelny, użyj modulo 2 ( x % 2)


-1: Jeśli chcesz być wydajny, użyj jednego z nich. Jeśli chcesz, aby był przenośny, użyj %. Jeśli chcesz, aby był czytelny, użyj %. Hmmm, widzę tutaj wzór.
Thomas Eding

@trinithis, nie ma wzorca, a to rozwiązanie jest znacznie lepsze niż twoje.
Subs

0

Sprawdzanie parzystej lub nieparzystej jest prostym zadaniem.

Wiemy, że każda liczba dokładnie podzielna przez 2 jest parzystą liczbą nieparzystą.

Musimy tylko sprawdzić podzielność dowolnej liczby, a do sprawdzenia podzielności używamy %operatora

Sprawdzanie nawet nieparzystych za pomocą if else

if(num%2 ==0)  
{
    printf("Even");
}
else
{
    printf("Odd");
}

Program C do sprawdzania parzystego lub nieparzystego za pomocą if else

Korzystanie z operatora warunkowego / trójskładnikowego

(num%2 ==0) printf("Even") : printf("Odd");

Program C do sprawdzania parzystego lub nieparzystego za pomocą operatora warunkowego .

Korzystanie z operatora bitowego

if(num & 1)  
{
    printf("Odd");
}
else 
{
    printf("Even");
}

a gdzie dokładnie jest operator trójskładnikowy?
Beyondo

0

+ 66% szybciej>!(i%2) / i%2 == 0

int isOdd(int n)
{
    return n & 1;
}

Kod sprawdza ostatni bit liczby całkowitej, jeśli ma wartość 1 w binarnym

Wyjaśnienie

Binary  :   Decimal
-------------------
0000    =   0
0001    =   1
0010    =   2
0011    =   3
0100    =   4
0101    =   5
0110    =   6
0111    =   7
1000    =   8
1001    =   9
and so on...

Zauważ, że najbardziej prawy bit to zawsze 1 dla liczb nieparzystych .

te i bitowe i operator sprawdza, a po prawej nieco w naszej powrotnej linii, jeśli jest to 1

Pomyśl o tym jako o prawdzie i fałszu

Kiedy porównujemy n z 1, co oznacza 0001binarnie (liczba zer nie ma znaczenia).
wyobraźmy sobie, że mamy liczbę całkowitą n o rozmiarze 1 bajtu.

Byłby reprezentowany przez 8-bitowe / 8-binarne cyfry.

Jeśli int n wynosił 7 i porównujemy go z 1 , to jest jak

7 (1-byte int)|    0  0  0  0    0  1  1  1
       &
1 (1-byte int)|    0  0  0  0    0  0  0  1
********************************************
Result        |    F  F  F  F    F  F  F  T

Które F oznacza fałsz, a T prawda.

To porównuje tylko po prawej stronie, nieco, jeśli oboje są prawdziwe. Tak więc automagicznie 7 & 1jest T rue.

Co jeśli chcę sprawdzić bit przed skrajnie prawą stroną?

Po prostu zmień n & 1na n & 220010 w Binary i tak dalej.

Sugeruję stosowanie notacji szesnastkowej, jeśli dopiero zaczynasz operacje bitowe
return n & 1;>> return n & 0x01;.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.