| Bit A | Bit B | A AND B | A OR B | A XOR B | NOT A |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
Trong ngôn ngữ C, có 6 toán tử được gọi là toán tử bitwise (hay còn được gọi là toán tử bit vì chúng hoạt động ở mức độ bit).
Cleat bit: xoá giá trị của 1 bit trong biến.
1 AND 0 = 0
0 AND 0 = 0Set bit: đặt giá trị của 1 bit trong biến.
1 OR 1 = 1
1 OR 0 = 0Toggle bit: đảo giá trị của một bit trong biến.
1 XOR 1 = 0
0 XOR 1 = 1Read bit: đọc giá trị của một bit trong biến.
0 AND 1 = 0
1 AND 1 = 1 #include <stdio.h>
unsigned int setBit (unsigned int value, unsigned int k);
unsigned int clearBit (unsigned int value, unsigned int k);
unsigned int readBit (unsigned int value, unsigned int k);
unsigned int toggleBit (unsigned int value, unsigned int k);
void printBinary (unsigned int num);
int main(){
unsigned int value = 8; unsigned int k = 2;
unsigned int SetBit, ClearBit, ReadBit, ToggleBit;
SetBit = setBit(value, k - 1);
ClearBit = clearBit(value, k - 1);
ReadBit = readBit(value, k - 1);
ToggleBit = toggleBit(value, k - 1);
printf("Value: %u, Order: %u\n", value, k);
printf("Value in binary:"); printBinary(value);
printf("SetBit: \t"); printBinary(SetBit);
printf("ClearBit: \t"); printBinary(ClearBit);
printf("ReadBit: \t"); printBinary (ReadBit);
printf("ToggleBit: \t"); printBinary(ToggleBit);
return 0;
}
unsigned int setBit (unsigned int value, unsigned int k)
{
return value |= (1<<k);
}
unsigned int clearBit (unsigned int value, unsigned int k){
return value &= ~(1<<k);
}
unsigned int readBit(unsigned int value, unsigned int k){
return (value & (1<<k)) >> k;
}
unsigned int toggleBit (unsigned int value, unsigned int k){
return value ^= (1<<k);
};
void printBinary(unsigned int num) {
int i;
int num_bits = (num == 0) ? 1 : log2(num) + 1;
for (i = num_bits - 1; i >= 0; i--) {
printf("%u", readBit(num, i));
}
printf("\n");
}Trong ngôn ngữ C, chúng ta có thể chỉ định kích thước (theo bit) của các thành phần trong struct và union.
Ý tưởng của bit field là sử dụng bộ nhớ một cách hiệu quả khi chúng ta biết rằng giá trị của một trường hoặc nhóm trường sẽ không vượt quá giới hạn hoặc nằm trong một khoảng nhỏ.
Bit field trong C được sử dụng khi không gian lưu trữ trong chương trình của chúng ta bị hạn chế.
Lợi ích của Bit field trong C
Bit field là các biến được định nghĩa với một độ rộng hoặc kích thước được xác định trước. Cú pháp khai báo của bit field như sau:
struct
{
data_type member_name : width_of_bit-field;
};data_type: Đây là một kiểu số nguyên xác định giá trị của trường bit mà sẽ được hiểu. Kiểu có thể là int, signed int hoặc unsigned int. member_name: Tên của bit field. width_of_bit-field: Số bit trong trường bit. Độ rộng phải nhỏ hơn hoặc bằng với độ rộng bit của kiểu dữ liệu được chỉ định.
#include <stdio.h>
union test {
// Bit-field member x with 3 bits
unsigned int x : 3;
// Bit-field member y with 3 bits
unsigned int y : 3;
// Regular integer member z
int z;
};
int main()
{
// Declare a variable t of type union test
union test t;
// Assign the value 5 to x (3 bits)
t.x = 5;
// Assign the value 4 to y (3 bits)
t.y = 4;
// Assign the value 1 to z (32 bits)
t.z = 1;
// Print the values of x, y, and z
printf("t.x = %d, t.y = %d, t.z = %d", t.x, t.y, t.z);
return 0;
}
}t.z = 1; giá trị 1 sẽ ghi vào vùng nhớ 32 bits này => giá trị của vùng nhớ (cả 32 bits) lúc này là 1.t.x, t.y và t.z in ra sẽ là giá trị của vùng nhớ union t => Kết quảThuật toán được chia ra nhiều loại khác nhau, tuy nhiên, note này chỉ nói đến thuật toán cơ bản là tìm kiếm và sắp xếp trên mảng hoặc trên danh sách liên kết.
Mục đích của thuật toán tìm kiếm là tìm ra dữ liệu tương ứng với khóa $k$ trong danh sách. Dữ liệu tìm kiếm có thể là chỉ số của phần tử trong mảng hoặc dữ liệu được người dùng định nghĩa. Ví dụ:
struct data {
int key; // khóa tìm kiếm
int data; // dữ liệu
};Mỗi thuật toán lại có độ phức tạp tính toán khác nhau. Cần để ý đến:
Tìm kiếm tuần tự là phương pháp tìm kiếm phần tử trong một mảng hay một danh sách liên kết bằng cách so sánh lần lượt từng phần tử trong danh sách với khóa k.
Ví dụ tìm kiếm vị trí phần tử $k$ trong mảng:
int find(int *arr, int len, int k) {
for (int i = 0; i < len; i++) {
if (arr[i] == k) {
return i;
}
}
return -1;
}Ví dụ tìm kiếm phần tử $k$ trong danh sách liên kết:
struct node {
int key;
int data;
struct node* next;
};
struct node* find(struct node* node, int k) {
struct node *inode;
for (inode = node; inode->next != NULL; inode = inode->next) {
if (inode->key == k) {
return inode;
}
}
return NULL;
}Có thể thấy, với mỗi phần tử trong danh sách, có 2 thao tác so sánh được thực hiện: Kiểm tra điều kiện dừng khi hết mảng và kiểm tra phần tử hiện tại thỏa mãn hay chưa. Có thể tối ưu thao tác này bằng cách thay thế phần tử tìm kiếm cuối cùng bằng phần tử có khóa hợp lệ (phần tử chặn). Như vậy, chắc chắn sẽ tìm thấy phần tử trong mảng và không cần kiểm tra điều kiện hết mảng. Ví dụ minh họa:
int find(int *arr, int len, int k) {
int last = arr[len-1];
arr[len-1] = k; // đặt phần tử cuối cùng = k
int i;
while (arr[i] != k) {
i+=1;
}
arr[len-1] = last; // trả lại giá trị phần tử cuối
if (i == len - 1) {
if (last == k) {
return len - 1;
} else {
return -1;
}
} else {
return i;
}
}Độ phức tạp thời gian:
Đối với danh sách kiểu mảng (có thể truy cập phần tử bằng chỉ số) đã được sắp xếp, việc tìm kiếm có thể được cải thiện đáng kể. Khi so sánh khóa $k$ với phần tử giữa danh sách, dựa vào kết quả so sánh mà một nửa danh sách có thể được loại bỏ do biết chắc chắn là các phần tử trong đó nhỏ hơn hoặc lớn hơn khóa tìm kiếm $k$.
Ví dụ tìm kiếm với $k = 8$ trong dãy $[1, 2, 3, 4, 5, 6, 7, 8, 9]$ có phần tử chính giữa bằng $5$. Với $k=8>5$, ta sẽ chỉ cần tìm kiếm $k$ trong dãy $[6, 7, 8, 9]$ với phương pháp tương tự.
// tìm kiếm trong danh sách tăng dần
int binary_search(int *arr, int first, int last, int k) {
if (last >= first) {
int mid = (first+last)/2; // first + (last-first)/2
if (arr[mid] == k) {
return mid;
} else if (arr[mid] > k) {
// phần tử hiện tại lớn hơn khóa
// -> tìm kiếm ở nửa trước
binary_search(arr, first, mid-1, k);
} else {
// phần tử hiện tại nhỏ hơn khóa
// -> tìm kiếm ở nửa sau
binary_search(arr, mid+1, last, k);
}
} else {
// last < first: danh sách rỗng - không tìm thấy
return -1;
}
}Độ phức tạp thời gian:
void insertion_sort(int *arr, int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
for (j = i - 1; j>=0; j--) {
if (arr[j] > key) {
arr[j+1] = arr[j];
} else {
break;
}
}
arr[j+1] = key;
}
}void bubble_sort(int*arr, int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n-i-1; j++) {
if(arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}void selection_sort(int *arr, int n) {
for (int i = 0; i < n-1; i++) {
int index_min = i;
int min = arr[i];
// tìm chỉ số và giá trị phần tử nhỏ hơn arr[i]
for (int j = i+1; j < n; j++) {
if (arr[j] < min) {
index_min = j;
min = arr[j];
}
}
arr[index_min] = arr[i];
arr[i] = min;
}
}
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
// Partition the array using the last element as the pivot
int partition_sort(int arr[], int low, int high)
{
// Choosing the pivot
int pivot = arr[high];
// Index of smaller element and indicates
// the right position of pivot found so far
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than the pivot
if (arr[j] < pivot) {
// Increment index of smaller element
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
// The main function that implements QuickSort
// arr[] --> Array to be sorted,
// low --> Starting index,
// high --> Ending index
void quickSort(int arr[], int low, int high)
{
if (low < high) {
// pi is partitioning index, arr[p]
// is now at right place
int pi = partition_sort(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}