Su un compilatore moderno, come faccio a codificare intenzionalmente per 2 secondi con wraparound?

( Disclaimer: non sono un esperto in comportamenti non definiti, ma credo di sapere quanto basta per dare una risposta a questa domanda.)
( Dichiarazione di non responsabilità: la lunghezza della risposta non è un'indicazione di correttezza.)
( Altro disclaimer: Sembra che la risposta di Daniel Jour gestisca una condizione che no (né la versione di OP): quando (b-a) == 0x80000000 . L'importanza è che né OP o la mia versione di codice possono essere usati tranquillamente come un predicato di ordinamento , che L'ordinamento dei numeri modulari è un argomento in sé e l'esistenza di una risposta dipende dal dato.)

// OP's original code
bool seq_ordered (uint32_t a, uint32_t b)
{
    auto delta = int32_t (b-a);
    return delta > 0;
}

Penso che il tuo codice sia valido così com'è. Fa due ipotesi, ma entrambe le ipotesi dovrebbero andare bene.

• I valori di origine a e b sono correttamente codificati in ridimensionamento binario , che è compatibile con complemento a due.
• La piattaforma di destinazione C ++ utilizza il complemento a due.

Si dovrebbe fare attenzione al primo punto (i valori di origine), specialmente se sono generati dall'hardware (come un encoder rotativo). Sebbene sia pratico presumere che la maggior parte degli obiettivi C ++ utilizzi il complemento a due, i dispositivi da analogico a digitale non fanno parte del tuo "ambiente informatico". Controlla la documentazione del componente elettronico.

La protezione dal secondo punto è semplice: usa un static_assert in modo che il codice non venga compilato su bersagli che non usano il complemento a due.

static_assert((uint32_t)(-1) == (uint32_t)0xFFFFFFFFuL, "Invalid arithmetic unless target uses two's complement");

Spiegazione: (secondo la mia comprensione)

• Sottrazione tra due uint32_t obbedisce modulo 2 ³²
• La conversione da uint32_t a int32_t è definita dall'implementazione . È specificamente non indefinito . In genere questo significa che dipende dal fatto che l'obiettivo usi il complemento a due o meno.
  La mia opinione è che è pratico assumerla e quindi evitare di utilizzare static_assert .
• Se i due passaggi precedenti erano corretti, il confronto viene eseguito in int32_t e dovrebbe fornire il risultato matematicamente corretto.

Se non ti piace affatto la conversione in int32_t , ma stai bene con l'assunzione pratica del complemento a due, puoi evitare la conversione come segue:

// I think it should give mathematically identical result, no?
bool seq_ordered(uint32_t a, uint32_t b)
{
    uint32_t diff = (b - a);
    return (diff > 0uL) && (diff < 0x80000000uL);
}

( Disclaimer: basato sui miei test con alcuni compilatori C ++ in linea, lo smontaggio x86-64 generato dalla mia versione è diverso dalla versione di OP. In particolare, la mia versione si traduce in due confronti, mentre la versione OP risulta in un confronto.)

I seguenti collegamenti sono forniti come riferimento. Come ho detto, non sono esperto in questo, quindi non posso garantire la correttezza della mia risposta.

• link
• link

Stai lavorando al livello sbagliato qui. Dovresti semplicemente return b > a . Scrivere una funzione corretta in tutti i casi sarà eccezionalmente difficile e quasi tutti si sbagliano e ha un gruppo di UB sottile nella loro base di codice. E questo è prima cercando di ottenerlo velocemente come il compilatore.

O in termini semplici, la risposta alla tua domanda è "Non lo fai".

L'unico modo in cui questo può funzionare è usare una caratteristica del compilatore incorporato, come una funzione incorporata o un flag del compilatore come -fwrapv. Questi non esistono per tutti i compilatori.

TL; Versione DR:

Dal momento che non esistono problemi di overflow / underflow con unsigned tipi di dati in C ++ puoi calcolare in modo sicuro una differenza tra i tuoi due valori. La dimensione di questa differenza in relazione all'intervallo di valori possibili indica quale valore è inferiore all'altro:

template<bool Strict = true, typename T>
bool ordered(T assumed_smaller, T assumed_larger) {
  static_assert(std::is_unsigned<T>::value, "Need unsigned");
  // Calculate the half of the range of the type, by using it's bit width.
  constexpr T const half_range = 1u << ((sizeof(T) * CHAR_BIT) - 1);
  // Calculate difference, possibly with wrap around.
  T const difference = assumed_larger - assumed_smaller;
  bool const not_equal = difference != 0;
  if (Strict) {
    // Strict mode, disallow ordered(a,b) and ordered(b,a) to be both true
    return not_equal
           && ((difference < half_range)
               || ((difference == half_range)
                   && (assumed_smaller < assumed_larger)));
  } else {
    // Non-strict, both ordered(a,b) and ordered(b,a) are true
    // if they're half_range apart.
    return not_equal && (difference <= half_range);
  }
}

Un po 'più in dettaglio:

Assumendo numeri interi a 2 bit senza segno (quindi da 0 a 3 come valori possibili), uno ha i seguenti casi:

0 0 | false
0 1 | true
0 2 | true
0 3 | false

1 0 | false
1 1 | false
1 2 | true
1 3 | true

2 0 | false (0 2 is already true)
2 1 | false
2 2 | false
2 3 | true

3 0 | true
3 1 | false (1 3 is already true)
3 2 | false
3 3 | false

true significa che il primo valore sulla linea deve essere considerato "prima di" il secondo valore. Si può immaginare meglio questo quando si visualizzano i possibili valori disposti in una sorta di cerchio (dal momento che vogliamo consentire il wrapping):

  0
3   1
  2

Due valori sono nell'ordine corretto se siamo in grado di passare dall'assunto più piccolo all'altro - andando in senso orario - in non più di 2 passi. Pertanto 3 0 è nell'ordine corretto, ma 3 2 non lo è.

Per fare ciò, è sufficiente controllare se assumed_larger - assumed_smaller <= 2 (dove 2 è la metà di max_value + 1 , o 2^(bits-1) ). Questa differenza è il numero di passi in senso orario se assumed_larger > = assumed_smaller e in senso antiorario altrimenti (grazie a modulo, esempio: 0 - 3 = -3 = -3 + 4 = 1 (mod 4) ).

Questo lascia il seguente problema: 0 2 e 2 0 (così come 1 3 e 3 1 ) entrambi richiedono 2 passaggi, quindi con il test precedente entrambi sarebbero nell'ordine corretto, che è una violazione dell'aspettativa che "se a != b , poi o a prima di b o b prima di a .

Poiché la domanda afferma che i valori non saranno "distanti", questo non sarebbe un problema, ma per correggerlo è necessario gestire il caso assumed_larger - assumed_smaller == 2 specialmente confrontando effettivamente entrambi i valori.

bool seq_ordered(uint32_t assumed_smaller, uint32_t assumed_larger) {
  constexpr uint32_t const half_range = 1 << ((sizeof(uint32_t) * CHAR_BIT) / 2);
  uint32_t difference = assumed_larger - assumed_smaller;
  return (difference != 0)
         && ((difference < half_range)
             || ((difference == half_range)
                 && (assumed_smaller < assumed_larger)));