"Annullamento" di un intero wraparound

Moltiplica per 1041204193.

Quando il risultato di una moltiplicazione non si adatta a un int, non otterrai il risultato esatto, ma otterrai un numero equivalente al risultato esatto modulo 2 ** 32 . Ciò significa che se il numero moltiplicato per era coprime a 2 ** 32 (che significa solo che deve essere dispari) , puoi moltiplicare per il suo inversione moltiplicativa per ottenere il tuo numero indietro. Wolfram Alpha o l'algoritmo euclideo esteso può dirci che il modulo 2 inverso moltiplicativo 33 ** è 1041204193. Quindi, moltiplicalo per 1041204193, e hai il x originale indietro.

Se avessimo, diciamo, 60 invece di 33, non saremmo in grado di recuperare il numero originale, ma saremmo in grado di ridurlo a poche possibilità. Calcolando 60 in 4 * 15, calcolando l'inverso di 15 mod 2 ** 32, e moltiplicando per quello, possiamo recuperare 4 volte il numero originale, lasciando solo 2 bit di ordine elevato del numero alla forza bruta. Wolfram Alpha ci fornisce 4008636143 per l'inverso, che non adattarsi a un int, ma va bene. Troviamo semplicemente un numero equivalente a 4008636143 mod 2 ** 32, o lo forgiamo comunque in un int per fare in modo che il compilatore lo faccia per noi, e il risultato sarà anche un inverso di 15 mod 2 ** 32. ( Otteniamo -286331153. )

Questo forse è più adatto come domanda per Math (sic) SE. Stai fondamentalmente parlando dell'aritmetica modulare, dato che l'eliminazione dei bit più a sinistra è la stessa cosa.

Non sono bravo in matematica come le persone che sono su Math (sic) SE, ma cercherò di rispondere.

Quello che abbiamo qui è che il numero viene moltiplicato per 33 (3 * 11), e il suo unico denominatore comune con il tuo mod è 1. Questo perché, per definizione, i bit nel computer sono potenze di due, e quindi la tua mod è una potenza di due.

Sarai in grado di costruire la tabella in cui per ogni valore precedente si calcola il seguente valore. E la domanda diventa fare i seguenti numeri corrispondono a uno solo precedente.

Se non fosse 33, ma un primo o un potere di un primo, credo che la risposta sarebbe sì, ma in questo caso ... chiedere su Math.SE!

Test programmatico

Questo è in C ++ perché non conosco C #, ma il concetto è ancora valido. Questo sembra mostrare che puoi:

#include <iostream>
#include <map>

int main(void)
{
    unsigned short count = 0;
    unsigned short x = 0;
    std::map<unsigned short, unsigned short> nextprev;

    nextprev[0] = 0;
    while(++x) nextprev[x] = 0;

    unsigned short nextX;
    while(++x)
    {
            nextX = x*33;
            if(nextprev[nextX])
            {
                    std::cout << nextprev[nextX] << "*33==" << nextX << " && " << x << "*33==" << nextX << std::endl;
                    ++count;
            }
            else
            {
                    nextprev[nextX] = x;
                    //std::cout << x << "*33==" << nextX << std::endl;
            }
    }

    std::cout << count << " collisions found" << std::endl;

    return 0;
}

Dopo aver popolato questa mappa, sarai sempre in grado di ottenere la X precedente se conosci la prossima. C'è sempre un solo valore in ogni momento.

Un modo per ottenerlo è usare la forza bruta. Spiacente, non conosco C # ma il seguente è uno pseudo codice c-like per illustrare la soluzione:

for (x=0; x<=INT_MAX; x++) {
    if (x*33 == test_value) {
        printf("%d\n", x);
    }
}

Tecnicamente, ciò di cui hai bisogno è x*33%(INT_MAX+1) == test_value , ma l'overflow dei numeri interi eseguirà automaticamente l'operazione % a meno che la tua lingua non utilizzi interi precisione arbitrari (bigint).

Ciò che ti dà è una serie di numeri che potrebbero essere stati il numero originale. Il primo numero stampato sarebbe il numero che genererebbe un round di overflow. Il secondo numero sarebbe il numero che genererebbe due round di overflow. E così via ..

Quindi, se conosci meglio i tuoi dati, puoi fare un'ipotesi migliore. Ad esempio, la matematica dell'orologio comune (overflow ogni 12) tende a rendere più probabile il primo numero poiché la maggior parte delle persone è interessata alle cose accadute oggi.

Il risolutore SMT Z3 potrebbe chiedergli di darti un incarico soddisfacente per la formula x * 33 = valueFromFile . Invertirà quell'equazione per te e ti darà tutti i possibili valori di x . Z3 supporta l'aritmetica bitvector esatta inclusa la moltiplicazione.

    public static void InvertMultiplication()
    {
        int multiplicationResult = new Random().Next();
        int knownFactor = 33;

        using (var context = new Context(new Dictionary<string, string>() { { "MODEL", "true" } }))
        {
            uint bitvectorSize = 32;
            var xExpr = context.MkBVConst("x", bitvectorSize);
            var yExpr = context.MkBVConst("y", bitvectorSize);
            var mulExpr = context.MkBVMul(xExpr, yExpr);
            var eqResultExpr = context.MkEq(mulExpr, context.MkBV(multiplicationResult, bitvectorSize));
            var eqXExpr = context.MkEq(xExpr, context.MkBV(knownFactor, bitvectorSize));

            var solver = context.MkSimpleSolver();
            solver.Assert(eqResultExpr);
            solver.Assert(eqXExpr);

            var status = solver.Check();
            Console.WriteLine(status);
            if (status == Status.SATISFIABLE)
            {
                Console.WriteLine(solver.Model);
                Console.WriteLine("{0} * {1} = {2}", solver.Model.Eval(xExpr), solver.Model.Eval(yExpr), solver.Model.Eval(mulExpr));
            }
        }
    }

L'output è simile a questo:

SATISFIABLE
(define-fun y () (_ BitVec 32)
  #xa33fec22)
(define-fun x () (_ BitVec 32)
  #x00000021)
33 * 2738875426 = 188575842

Per annullare quel risultato otterrai una quantità di numeri finiti non nulli (normalmente infinita, ma int è un sottoinsieme finito di ℤ). Se questo è accettabile, basta generare i numeri (vedi altre risposte).

Altrimenti è necessario mantenere un elenco di cronologia (di lunghezza finita o infinita) della cronologia della variabile.

Come sempre, c'è una soluzione da uno scienziato e una soluzione di un ingegnere.

Sopra troverai una soluzione molto buona da uno scienziato, che funziona sempre, ma richiede di calcolare "inversione moltiplicativa".

Ecco una soluzione rapida dell'ingegnere, che non ti costringerà a provare tutti i possibili numeri interi.

val multiplier = 33 //used with 0x23456789
val problemAsLong = (-1947051863).toLong & 0xFFFFFFFFL

val overflowBit = 0x100000000L
for(test <- 0 until multiplier) {
  if((problemAsLong + overflowBit * test) % multiplier == 0) {
    val originalLong = (problemAsLong + overflowBit * test) / multiplier
    val original = originalLong.toInt
    println(s"$original (test = $test)")
  }
}

Quali sono le idee?

1. Abbiamo avuto un overflow, quindi usiamo i tipi più grandi da recuperare ( Int -> Long )
2. Probabilmente abbiamo perso alcuni bit a causa di un overflow, recuperiamoli
3. L'overflow non è stato superiore a Int.MaxValue * multiplier

Il codice eseguibile completo si trova su link

Dettagli:

• val problemAsLong = (-1947051863).toLong & 0xFFFFFFFFL
  Qui convertiamo il nostro numero memorizzato in Long, ma poiché Int e Long sono firmati, dobbiamo farlo correttamente.
  Quindi limitiamo il numero usando bit AND con bit di Int.
• val overflowBit = 0x100000000L
  Questo bit o la sua moltiplicazione potrebbero essere persi con la moltiplicazione iniziale.
  È un primo bit al di fuori della gamma Int.
• for(test <- 0 until multiplier)
  Secondo la terza idea, l'overflow massimo è limitato dal moltiplicatore, quindi non provare più del necessario.
• if((problemAsLong + overflowBit * test) % multiplier == 0)
  Verifica se aggiungendo un eventuale overflow perduto arriviamo a una soluzione
• val original = originalLong.toInt
  Il problema originale era nella gamma Int, quindi torniamo indietro. Altrimenti potremmo recuperare in modo non corretto i numeri, che erano negativi.
• println(s"$original (test = $test)")
  Non rompere dopo la prima soluzione, perché potrebbero esserci altre possibili soluzioni.

PS: 3rd Idea non è strettamente corretta, ma lasciata per essere comprensibile.
Int.MaxValue è 0x7FFFFFFF , ma l'overflow massimo è 0xFFFFFFFF * multiplier .
Quindi il testo corretto sarebbe "L'overflow non era superiore a -1 * multiplier ".
Questo è corretto, ma non tutti lo capiranno.