Trước hết, nhắc lại sơ lược về bit và toán tử bitwise.
Bit (binary digit) là đơn vị dữ liệu nhỏ nhất máy tính hiểu, chỉ có 2 giá trị: 0 (TẮT) và 1 (BẬT).
Toán tử bitwise là các toán tử thao tác ở cấp bit trong chương trình. Dùng để thao tác bit.
Trong C có 6 toán tử bitwise:
- Bitwise AND (&)
- Bitwise OR (|)
- Bitwise XOR (^)
- Bitwise left Shift (<<)
- Bitwise right Shift (>>)
- Bitwise NOT (~)
Tham khảo: https://www.tutorialspoint.com/cprogramming/c_bitwise_operators.htm
Dưới đây là các kỹ thuật quan trọng khi làm việc với bit.
Hoán đổi hai số (dùng XOR)
Có thể hoán đổi hai giá trị dùng XOR mà không cần biến tạm.
Ví dụ
#include <stdio.h>
int main() {
int x = 41;
int y = 90;
printf("Values before swapping! \n");
printf("x = %d \t", x);
printf("y = %d \n", y);
x = x ^ y;
y = y ^ x;
x = x ^ y;
printf("Values after swapping! \n");
printf("x = %d \t", x);
printf("y = %d \n", y);
return 0;
}
Đầu ra
Values before swapping! x = 41 y = 90 Values before swapping! x = 90 y = 41
Cách hiệu quả tìm MSB (Most Significant Bit)
Với số nguyên bất kỳ, tìm MSB hiệu quả bằng OR kết hợp dịch bit. Tìm MSB trong O(1) (với kích thước int cố định).
Ví dụ
Chương trình tìm MSB của int 32-bit:
#include <stdio.h>
int findMSB(int x) {
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x = x + 1;
return (x >> 1);
}
int main() {
int x = 49;
printf("The number is %d\n", x);
int msb = findMSB(x);
printf("MSB of the number is %d\n", msb);
}
Đầu ra
The number is 49 MSB of the number is 32
Tính trực tiếp XOR từ 1 đến n
Quan sát XOR từ 0 đến n thấy quy luật theo n%4.
Ví dụ
#include <stdio.h>
int findXORuptoN(int n) {
switch(n % 4) {
case 0: return n;
case 1: return 1;
case 2: return n + 1;
case 3: return 0;
}
}
int main() {
int n = 9870;
int xorupton = findXORuptoN(n);
printf("XOR of all number up to %d is %d\n", n, xorupton);
}
Đầu ra
XOR of all number up to 9870 is 9871
Đếm tổ hợp số ≤ n có tổng và XOR bằng nhau
Dùng dịch bit để đếm số bit 0 trong n, kết quả = 2^(số bit 0).
Ví dụ
#include <stdio.h>
int countValues(int n) {
int unset = 0;
while (n) {
if ((n & 1) == 0)
unset++;
n = n >> 1;
}
return (1 << unset);
}
int main() {
int n = 32;
printf("%d", countValues(n));
}
Đầu ra
32
Đếm số 0 đầu và cuối của số nguyên
GCC có hàm builtin: __builtin_clz (leading zeros), __builtin_ctz (trailing zeros).
Ví dụ
#include <stdio.h>
int main() {
int n = 32;
printf("The integer value is %d\n", n);
printf("Number of leading zeros is %d\n", __builtin_clz(n));
printf("Number of trailing zeros is %d\n", __builtin_ctz(n));
}
Đầu ra
The integer value is 32 Number of leading zeros is 26 Number of trailing zeros is 5
Kiểm tra số có phải lũy thừa của 2?
Dùng bitwise: n && !(n & (n-1)).
Ví dụ
#include <stdio.h>
int isPowerof2(int n) {
return n && (!(n & (n-1)));
}
int main() {
int n = 22;
if(isPowerof2(n))
printf("%d is a power of 2", n);
else
printf("%d is not a power of 2", n);
}
Đầu ra
22 is not a power of 2
Tìm XOR của tất cả tập con của một tập hợp
Nếu tập hợp có >1 phần tử, XOR tất cả tập con luôn = 0. Nếu 1 phần tử thì = phần tử đó.
Ví dụ
#include <stdio.h>
int findSubsetXOR(int set[], int size) {
if (size == 1)
return set[size - 1];
else
return 0;
}
int main() {
int set[] = {45, 12};
int size = sizeof(set) / sizeof(set[0]);
printf("The XOR of all subsets of set of size %d is %d\n", size, findSubsetXOR(set, size));
int set2[] = {65};
size = sizeof(set2) / sizeof(set2[0]);
printf("The XOR of all subsets of set of size %d is %d\n", size, findSubsetXOR(set2, size));
}
Đầu ra
The XOR of all subsets of set of size 2 is 0 The XOR of all subsets of set of size 1 is 65
Chuyển số nhị phân sang nguyên (dùng auto)
Từ khóa auto trong C cho phép viết literal nhị phân 0b....
Ví dụ
#include <stdio.h>
int main() {
auto integer = 0b0110110;
printf("The integer conversion of binary number '0110110' is %d", integer);
}
Đầu ra
The integer conversion of binary number '0110110' is 54
Đảo ngược tất cả bit của một số
Trừ số đó khỏi số có tất cả bit = 1 cùng độ dài.
Số = 0110100 Số all bits set = 1111111 Hiệu = 1111111 - 0110100 = 1001011 (số bit đảo)
Ví dụ
#include <stdio.h>
int main() {
int number = 23;
int n = number;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
printf("The number is %d\n", number);
printf("Number with reversed bits %d\n", n - number);
}
Đầu ra
The number is 23 Number with reversed bits 8
Kiểm tra bit có mẫu luân phiên
Dùng XOR: n ^ (n >> 1). Nếu kết quả dạng 111... thì bit luân phiên.
Ví dụ
#include <stdio.h>
int checkBitPattern(int n) {
int result = n ^ (n >> 1);
if (((result + 1) & result) == 0)
return 1;
else
return 0;
}
int main() {
int number = 4;
if (checkBitPattern(number))
printf("Bits of %d are in alternate pattern", number);
else
printf("Bits of %d are not in alternate pattern", number);
}
Đầu ra
Bits of 4 are not in alternate pattern