Operatore XOR

Lezione 6 di 17 del corso Manipolazione dei bit di Coddy.

Operatore XOR ( ^ )

Lo XOR bit a bit prende due sequenze di bit della stessa lunghezza. Se non hanno la stessa lunghezza, aggiungi degli zeri prima del MSB della sequenza di bit più corta. Se i due bit nella posizione confrontata delle sequenze di bit sono uguali, il bit nella sequenza risultante è 0, altrimenti è 1.

Il simbolo '^' viene usato per rappresentare l'operazione XOR.

Quando ne parliamo in termini matematici, usiamo '⊕' per rappresentare XOR. Quindi, in alcune domande potresti incontrare anche questa notazione. Ora creiamo una tabella per vedere cosa restituisce l'operatore XOR per tutte le possibili combinazioni di due bit.

x	0	1	1
y	1	0	1
x ^ y	1	1	0

Facciamo un esempio per capire meglio l'operazione-

Nell'esempio qui sopra abbiamo eseguito l'operazione XOR su (11)₁₀e (2)₁₀ ottenendo (9)₁₀. Abbiamo semplicemente scritto questi numeri in forma binaria, confrontato i due bit e seguito la definizione di operazione XOR riportata sopra.

Uso:

int a = 1;
int b = 0;
>> a ^ b
OUTPUT: 1

Ora, XOR ha alcune proprietà che possono ridurre il tempo necessario per risolvere le domande relative a XOR, se non le conosci.

Alcune importanti proprietà di XOR

x ⊕ 0 = x - Se esegui XOR tra un numero e zero, otterrai lo stesso numero.
x ⊕ x = 0 - Se esegui XOR tra un numero e se stesso, otterrai zero.
Prendiamo due numeri x e y. Supponiamo che x ⊕ y = z. Allora anche x ⊕ z = y e y ⊕ z = x sono uguaglianze valide.

Sfida

Medio

A Sean piace indossare calzini e avere calzini eleganti diversi nel suo armadio. Tiene i calzini con dei numeri scritti sopra. Per esempio, (1,1) , (10, 10) rappresentano due paia di calzini. Purtroppo, un giorno un gatto si intrufola nel suo armadio e porta via un calzino. I calzini presenti nell'armadio ti vengono forniti come array; completa la funzione MissingSock per scoprire quale calzino ha portato via il gatto.

Per esempio,

L'armadio originale contiene 6 calzini: 1, 1, 2, 3, 3, 2,

2 calzini con il numero 1
2 calzini con il numero 2
2 calzini con il numero 3

Il gatto è passato e ha rubato un calzino con il numero 1. L'input ora è: 1, 2, 3, 3, 2 perché manca un calzino con il numero 1. La sfida consiste nel trovare il calzino mancante (l'output dovrebbe essere 1 perché questo è il calzino mancante)

Provalo tu

#include <iostream>
#include <vector>
using namespace std;

int MissingSock(vector<int> socks) {
    // Scrivi il codice qui
}

Tutte le lezioni di Manipolazione dei bit

1Introduzione e basi

Cos’è la manipolazione dei bit?Perché serve la manipolazione dei bit?Numeri binari e decimali Operatori NOT e OR Operatore ANDOperatore XOROperatori di shift a destra e a sinistra Riepilogo degli operatori bitwise

2Algoritmi sui bit

Potenza di 2 Numero che ricorre un numero dispari di volte Numero di bit impostati Rotazione dei bit di un numero I Rotazione dei bit di un numero II

3Sfide pratiche

Tina e l’assegnazione dei bit XORty Trova K Trova la somma minima

Esercitati da solo: Compilatore C++ online