Một số ứng dụng của phép toán trên bit
Bit
1
HuuThanhDTD

HuuThanhDTD viết ngày 14-08-2018

Các phép toán trên bit luôn give best performance và tối giản hóa bộ nhớ. Hôm nay mình viết bài này note lại cho mọi người xài chơi, có đủ cấp độ.

Zero Space Swap

x ^= y;
y ^= x;
x ^= y;

Xóa đi bit 1 cuối cùng hoặc kiểm tra một số N có phải là power of 2

N = N & (N-1); // Xóa đi bit 1 cuối cùng
0 == N & (N-1); // Kiểm tra power of 2
// Thử nghĩ về việc kiểm tra power of 4 xem :)

Kiểm tra chẵn lẻ

N & 1 == 0 // chẵn
N & 1 == 1 // lẻ

Phép toán

Nhân 2^K

N <<= K

Chia cho 2^K

N >>= K

Chia 4 dư mấy

N & 3

Chia 8 dư mấy

N & 7

Chia 2^K dư mấy

N & ((1 << K) - 1)

Bật bit thứ K của số N

N = N | (1 << K)

Tắt bit thứ K của số N

Golang: N &= ^(1 << K)
C/Java: N &= ~(1 << K)

Max và min

min(x,y) = y ^ ((x ^ y) & -(x < y))
max(x,y) = y ^ ((x ^ y) & -(x > y))

Kiểu dữ liệu string

//Chuyển ký tự thành ký tự thường:
//Dùng phép OR với khoảng trống => (x | '  ')
('a' | '  ') => 'a' ; ('A' | '  ') => 'a'

//Chuyển ký tự thành chữ in hoa:
//Dùng phép AND với ký tự gạch dưới => (x & '_')
('a' & '_') => 'A' ; ('A' & '_') => 'A'

//Đổi ngược kiểu ký tự (hoa thành thường và ngược lại):
//Dùng phép XOR với khoảng cách => (x ^ ' ')
('a' ^ ' ') => 'A' ; ('A' ^ ' ') => 'a'

//Tìm vị trí của ký tự trong bảng chữ cái(vd: A là 1, Z là 26):
//Kết quả trong khoảng từ 1 tới 26, không phân biệt hoa thường
//AND với ký tự '?' => (x & '?') hoặc XOR với ký tự '@' => (x ^ '@')
('C' & '?') => 3 ; ('Z' ^ '@') => 26
//Chuyển ký tự thành ký tự thường:
//Dùng phép OR với khoảng trống => (x | '  ')
('a' | '  ') => 'a' ; ('A' | '  ') => 'a'
 
//Chuyển ký tự thành chữ in hoa:
//Dùng phép AND với ký tự gạch dưới => (x & '_')
('a' & '_') => 'A' ; ('A' & '_') => 'A'
 
//Đổi ngược kiểu ký tự (hoa thành thường và ngược lại):
//Dùng phép XOR với khoảng cách => (x ^ ' ')
('a' ^ ' ') => 'A' ; ('A' ^ ' ') => 'a'
 
//Tìm vị trí của ký tự trong bảng chữ cái(vd: A là 1, Z là 26):
//Kết quả trong khoảng từ 1 tới 26, không phân biệt hoa thường
//AND với ký tự '?' => (x & '?') hoặc XOR với ký tự '@' => (x ^ '@')
('C' & '?') => 3 ; ('Z' ^ '@') => 26

Trên đây là mấy trò tiêu biểu hay xài. Còn nhiều trò nữa ở link này: BitHacks

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Hãy đăng nhập để bình luận :)
HuuThanhDTD

HuuThanhDTD

19 bài viết.
18 bình luận
{{liked ? "Đã bookmark" : "Bookmark"}}
Follow
{{like_count}}

bookmark

{{ comment_count }}

bình luận

{{liked ? "Đã bookmark" : "Bookmark"}}


HuuThanhDTD
Follow
19 bài viết.
18 bình luận

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