Ứng dụng của phép toán XOR
Python
70
White

Petit Vietnam viết ngày 24/06/2018

Ứng dụng của phép toán XOR

Phép toán XOR trong logic có input là 2 bit a và b, output là 1 khi mà a != b và 0 trong trường hợp ngược lại. Bảng giá trị chân lí của phép XOR như sau:

a b a XOR b
0 0 0
0 1 1
1 0 1
1 1 0

Các tính chất của phép XOR:

1, A XOR 0 = A
2, A XOR A = 0
3, (A XOR B) XOR C = A XOR (B XOR C)
4, (B XOR A) XOR A = B XOR 0 = B

Sau đây là 2 ví dụ về việc sử dụng phép XOR:

1. Mã hóa

Cho trước một khóa key, ta có thể biến đổi kí tự x ban đầu thành một kí tự x1 = x XOR key . (x1 != x)

Lúc này nếu một người nào đó có khóa key có thể tìm lại kí tự gốc bằng cách sử dụng phép XOR với key một lần nữa (tính chất 4)

Ví dụ ta có thông điệp muốn gửi đi là : "tối nay hẹn ở chỗ cũ lúc 9 giờ" và chọn 1 khóa là key = 12 (giá trị bất kì). (Hàm bytearray sẽ chuyển dãy kí tự thành một dãy số trước khi thực hiện phép XOR)

key = 12
message = 'tối nay hẹn ở chỗ cũ lúc 9 giờ'

encrypt = bytearray(key ^ x for x in bytearray(message, 'utf-8'))
print(encrypt)
# bytearray(b'x\xed\xb7\x9de,bmu,d\xed\xb6\xb5b,\xed\xb7\x93,od\xed\xb7\x9b,o\xc9\xa5,`\xcf\xb6o,5,ke\xed\xb7\x91')

Để giải mã thì ta lặp lại quá trình trên với cùng key

message = bytearray(key ^ x for x in encrypt)
print(message)
# bytearray(b't\xe1\xbb\x91i nay h\xe1\xba\xb9n \xe1\xbb\x9f ch\xe1\xbb\x97 c\xc5\xa9 l\xc3\xbac 9 gi\xe1\xbb\x9d')

Lúc này message là một chuỗi unicode (các kí tự máy tính hiểu được). Muốn chuyển lại cho chúng ta hiểu được ta dùng hàm decode để thu được thông điệp ban đầu. Tất nhiên chỗ cũ cũng giống như việc quy ước giá trị của key chỉ có người gửi và người nhận biết.

print(message.decode()) # 'tối nay hẹn ở chỗ cũ lúc 9 giờ'

2. Tìm phần tử lặp.

Cho một mảng gồm n phần tử có giá trị từ 1 đến n-1 (chỉ có 1 phần tử duy nhất lặp lại 2 lần). Giả sử chỉ được duyệt qua dãy 1 lần duy nhất. Tìm phần tử đó.

Ví dụ:
input: n = 4, a = [4, 2, 3, 1, 2]. Ta thấy 2 là phần tử lặp lại 2 lần.
output: 2

Bài toán có thể giải bằng cách đơn giản như sau (tổng các số từ 1 đến n có thể thay bằng công thức n * (n-1) / 2):

(4 + 2 + 3 + 1 +  2)  -  (1 + 2 + 3 + 4)  # 2

Một cách khác là sử dụng phép toán XOR, ta áp dụng phép toán xor tất cả các phần tử trong dãy a với các phần tử từ 1 đến n:

(4 ^ 2 ^ 3 ^ 1 ^ 2)  ^ (1 ^ 2 ^ 3 ^ 4) # 2

Sử dụng tính chất 3 ta có thể chuyển biểu thức trên thành dạng như sau:

(4 ^ 4) ^ (3 ^ 3) ^ (2 ^ 2 ^ 2) ^ (1 ^ 1)

Do tính chất 2 nên các cặp (4^4), (3^3), (1^1) = 0, (2^2^2) = (0^2) = 2 (tính chất 1)

3. Kết

2 ví dụ trên tuy đơn giản nhưng nó cho thấy những kiến thức đơn giản của toán học có thể áp dụng được trong lập trình, mã hóa.

PetitVietnam 24-06-2018

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Petit Vietnam

1 bài viết.
0 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Bài viết liên quan
White
7 4
Description Mình là một thằng thích đọc sách. Nhưng lúc nào cũng bận (lười) nên cũng mấy tháng rồi chưa hoàn thành được quyển sách nào. Mình đa số...
Rice viết hơn 1 năm trước
7 4
White
5 2
Requirement Hôm bữa đọc được bài https://kipalog.com/posts/Hocvacaithienkienthuctucacduancanhanpetproject thấy hay quá. Tính cũng định viết con ap...
Rice viết hơn 1 năm trước
5 2
White
0 0
(Ảnh) (image from internet) Mở bài Chào mừng mọi người đến với bài post tiếp theo của phần “The Python Tutorial” của series “Khám phá Đại Bản Doa...
BeautyOnCode viết 25 ngày trước
0 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
1 bài viết.
0 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!