Vui vẻ cùng Bit operations

Bit operations

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ẻ

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 (thanks anh @huydx)

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

Harder: Ứng dụng trong Binary index tree

Lấy ra Least significant bit

N & -N

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