Operator XOR

Lekcja 6 z 17 w kursie Operacje bitowe w Coddy.

Operator XOR ( ^ )

Bitowy XOR przyjmuje dwa ciągi bitów o jednakowej długości. Jeśli nie są jednakowej długości, dodaj zera przed najbardziej znaczącym bitem krótszego ciągu. Jeśli bity na porównywanych pozycjach obu ciągów są równe, bit w wynikowym ciągu ma wartość 0, w przeciwnym razie 1.

Symbol '^' służy do zapisu operacji XOR.

W zapisie matematycznym używamy symbolu '⊕' do oznaczenia XOR. Dlatego w niektórych zadaniach możesz się z nim spotkać. Teraz utwórzmy tabelę, aby zobaczyć, jaki wynik zwraca operator XOR dla wszystkich możliwych kombinacji dwóch bitów.

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

Rozważmy przykład, aby lepiej zrozumieć tę operację —

W powyższym przykładzie wykonaliśmy operację XOR na (11)₁₀i (2)₁₀, w wyniku czego otrzymaliśmy (9)₁₀. Zapisaliśmy te liczby w postaci binarnej, porównaliśmy oba bity i zastosowaliśmy powyższą definicję operacji XOR.

Zastosowanie:

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

XOR ma też pewne właściwości. Jeśli ich nie znasz, mogą znacznie skrócić czas rozwiązywania zadań związanych z XOR.

Ważne właściwości XOR

x ⊕ 0 = x - Jeśli wykonasz XOR liczby z zerem, otrzymasz tę samą liczbę.
x ⊕ x = 0 - Jeśli wykonasz XOR liczby z samą sobą, otrzymasz zero.
Weźmy dwie liczby x i y. Załóżmy, że x ⊕ y = z. Wówczas równości x ⊕ z = y i y ⊕ z = x również są prawdziwe.

Wyzwanie

Średni

Sean uwielbia nosić skarpetki i mieć w szafie różne stylowe skarpetki. Trzyma skarpetki z zapisanymi na nich numerami. Na przykład (1,1), (10, 10) reprezentują dwie pary skarpet. Niestety pewnego dnia kot zakrada się do jego szafy i zabiera skarpetkę. Skarpetki znajdujące się w szafie są podane jako tablica. Uzupełnij funkcję MissingSock, aby ustalić, którą skarpetkę zabrał kot.

Na przykład:

W szafie pierwotnie znajduje się 6 skarpetek: 1, 1, 2, 3, 3, 2,

2 skarpetki z numerem 1
2 skarpetki z numerem 2
2 skarpetki z numerem 3

Kot przyszedł i ukradł jedną skarpetkę z numerem 1. Dane wejściowe to teraz: 1, 2, 3, 3, 2, ponieważ brakuje jednej skarpetki z numerem 1. Wyzwaniem jest znalezienie brakującej skarpetki (wynikiem powinno być 1, ponieważ to właśnie ta skarpetka zaginęła).

Spróbuj swoich sił

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

int MissingSock(vector<int> socks) {
    // Wpisz kod tutaj
}

Wszystkie lekcje w sekcji Operacje bitowe

1Wprowadzenie i podstawy

Czym jest manipulacja bitami?Dlaczego potrzebujemy manipulacji bitami?Liczby binarne i dziesiętne Operatory NOT i OR Operator ANDOperator XOROperatory przesunięcia w prawo i w lewo Podsumowanie operatorów bitowych

2Algorytmy bitowe

Potęga liczby 2 Liczba występująca nieparzystą liczbę razy Liczba ustawionych bitów Rotacja bitów liczby I Rotacja bitów liczby II

3Wyzwania praktyczne

Tina i jej zadanie z bitami XORty Znajdź K Znajdź minimalną sumę

Poćwicz samodzielnie: Kompilator C++ online