Come dimostrare che l'istruzione C -x, ~x+1 e ~(x-1) produce gli stessi risultati?

Question

Voglio conoscere la logica dietro questa affermazione, la prova.Le espressioni C -x, ~x+1 e ~(x-1) producono tutte gli stessi risultati per qualsiasi x.Posso dimostrare che questo è vero per esempi specifici.Penso che il modo per dimostrarlo abbia qualcosa a che fare con le proprietà del complemento a due.Qualche idea?

Answer 1

Si consideri ciò che si ottiene quando si aggiunge un numero al suo complemento bit per bit. Il complemento bitwise di un intero x n bit ha un 1 ovunque x ha un 0, e viceversa. Quindi è chiaro a vedere:

x + ~ x = 0b11 ... (valore n bit di tutti quelli) 11

Indipendentemente dal numero di bit in x. Inoltre, si noti che l'aggiunta di uno a un numero n-bit pieno di tutti quelli renderà avvolgere a zero. Così vediamo:

x + ~ x + 1 = 0b11 ... 11 + 1 = 0 e ~ x + 1 = -x.

Allo stesso modo, la nota (x - 1) + ~ (x - 1) = 0b11 ... 11. Poi (x - 1) + ~ (x - 1) + 1 = 0, e ~ (x - 1). = -X

Answer 2

Non sono sicuro che tu possa dimostrarlo con qualsiasi tipo di assioma utile diverso dalla riduzione piuttosto banale al fatto che abbiamo definito i numeri negativi nelle moderne ALU intere come in complemento a due.

I computer no Avere da implementare con hardware binario in complemento a due, è solo che ci sono varie proprietà interessanti e quasi tutto è costruito in questo modo al giorno d'oggi.(Ma non in virgola mobile!Quelli sono il complemento!)

Quindi costruiamo una macchina che rappresenta i numeri negativi nel complemento a 2.Le espressioni che mostrano che i numeri negativi devono essere rappresentati in complemento a due sono accurate, ma solo perché le abbiamo definite in questo modo.Questa è la base assiomatica per i numeri interi negativi nelle macchine moderne.

Dato che definiamo la negazione in termini di complemento a due, ti riferisci essenzialmente agli assiomi, anche se suppongo che sia ciò che alla fine fanno tutte le dimostrazioni.

Forse è per questo che non sono proprio un tipo da teoria.:-)

Answer 3

~ x + 1 è pari al complemento a 2 + 1 (cioè il numero negativo) rappresentazioni di -x, ~ (x-1) rappresenta anche lo stesso (si pensi al caso in cui ultimo bit è 1, ~ (x-1) = ~ (b1b2.b (n-1) 1 - 0) = b1'b2' ... b (n-1) '1 = b1'b2' ... b (n-1) '0 + 1 = . ~ x + 1 simile caso attesa per ultimo bit è 0. ~ (x-1) = ~ (b1b2..bi100..00 - 1) = ~ = b1b2..bi011..11 b1'b2' .. bi '100..00 = b1'b2' .. bi'011..11 + 1 = ~ x + 1.

Answer 4

Cercherò di presentare una spiegazione intuitiva che tutti dovrebbero trovare a portata di mano. Se insisti potremmo tentare un approccio più formale.

Nella rappresentazione in complemento a due, in modo da avere una rappresentazione unica dell'elemento a zero, sacrifichiamo un elemento positivo. Di conseguenza, v'è un numero in più negativa che non ha specchio positivo.

Quindi, dato 2 bit, otteniamo: {+1, 0, -1, -2} che sarebbe rappresentato in binario come:

-2    10
-1    11
 0    00
+1    01

Quindi, possiamo pensare di zero come uno specchio. Ora, dato un intero x, se vogliamo invertire il suo segno, possiamo iniziare invertendo tutti i bit. Questo sarebbe stato sufficiente se non ci fosse zero tra gli aspetti positivi e negativi. Ma dal momento che lo zero fa un cambiamento, in positivi, abbiamo compensare questo.

I due espressioni citate nell'interrogazione rendono tale compensazione prima e dopo ~(x-1) ~x+1 invertendo i bit. Si può facilmente verificare che l'utilizzo di +1 e -1 nel nostro esempio 2-bit.

Answer 5

In generale, questo non è vero, come lo standard C non richiede l'uso di complemento a due per rappresentare i numeri negativi.

In particolare, il risultato dell'applicazione di ~ a un tipo firmato non è definito.

Tuttavia, per quanto ne so tutte le macchine moderne utilizzano complemento a due per gli interi.