Đầu tiên chúng ta hãy nhớ lại các bit about và toán tử bitwise là viết tắt.
Bit là một chữ số nhị phân. Nó là đơn vị dữ liệu nhỏ nhất mà máy tính có thể hiểu được. Trong chỉ có thể có một trong hai giá trị 0 (biểu thị TẮT) và 1 (biểu thị BẬT) .
Toán tử bitwise là các toán tử hoạt động ở mức bit trong chương trình.
Các toán tử này được sử dụng để thao tác các bit trong chương trình.
Trong C, chúng ta có 6 toán tử bitwise -
-
Bitwise VÀ (&)
-
Bitwise HOẶC (HOẶC)
-
Bitwise XOR (XOR)
-
Shift trái bit (<<) / p>
-
Shift phải bitwise (>>)
-
Bitwise không (~)
https://www.tutorialspoint.com/cprogramming/c_bitwise_operators.htm
Bây giờ, chúng ta hãy tìm hiểu một số chiến thuật quan trọng, tức là những thứ có thể hữu ích nếu bạn làm việc với bit.
Hoán đổi hai số (sử dụng bitwise XOR)
Chúng ta có thể hoán đổi hai giá trị bằng cách sử dụng toán tử XOR bit. Việc thực hiện là -
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 (bit quan trọng nhất)
Đối với bất kỳ giá trị số nguyên nào, chúng ta có thể tìm ra bit quan trọng nhất là một cách hiệu quả. Điều này được thực hiện bằng cách sử dụng toán tử hoặc cùng với một toán tử dịch chuyển bit. Phương pháp này có thể tìm MSB theo độ phức tạp thời gian o (1).
Kích thước của số nguyên phải được xác định trước để tạo chương trình.
Ví dụ
Chương trình tìm MSB của số nguyên 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 của tất cả các số từ 1 đến n.
Nếu chúng ta quan sát XOR từ 0 đến n một cách cẩn thận, chúng ta có thể rút ra một mẫu tổng quát. Được minh họa ở đây -
Ví dụ
#include <stdio.h>
// Direct XOR of all numbers from 1 to n
int findXORuptoN(int n){
switch( n%4){
case 0: return n;
case 1: return 1;
break;
case 2: return n+1;
break;
case 3: return 0;
break;
default: break;
}
}
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
Tính trực tiếp tổng số kết hợp với một số nhỏ hơn hoặc bằng với một số có tổng và XOR bằng nhau.
Sử dụng các toán tử dịch chuyển theo từng bit, chúng ta có thể dễ dàng thực hiện công việc và sẽ tốn ít thời gian hơn.
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
Tìm số chữ 0 đứng đầu và đứng sau trong một số nguyên
Có các phương pháp sẵn có để tìm số lượng các số 0 ở đầu và ở cuối của một số nguyên, nhờ vào thao tác bit.
* Đây là một chức năng có sẵn của GCC
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_clz(n));
} Đầu ra
The integer value is 32 Number of leading zeros is 26 Number of trailing zeros is 26
Kiểm tra xem một số có phải là lũy thừa của hai không?
Để kiểm tra xem một số có phải là lũy thừa của 2 hay không, được thực hiện dễ dàng bằng cách sử dụng toán tử bitwise.
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ả các tập con của một tập hợp
Điều này có thể được thực hiện bằng cách sử dụng thực tế là nếu có nhiều hơn 1 phần tử thì XOR của tất cả các tập con luôn là 0 và ngược lại là số.
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 đổi số nguyên nhị phân đã cho
tự động từ khóa trong C được sử dụng để thực hiện nhiệm vụ.
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
Lật tất cả các bit của một số
Chúng ta có thể lật tất cả các bit của một số bằng cách trừ nó khỏi một số có tất cả các bit được đặt.
Number = 0110100 The number will all bits set = 1111111 Subtraction -> 1111111 - 0110100 = 1001011 (number with flipped bits)
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 xem các bit có mẫu thay thế không
Sử dụng phép toán bitwise XOR, chúng ta có thể tìm xem các bit của một số có nằm trong các mẫu thay thế hay không. Đoạn mã dưới đây cho biết cách -
Ví dụ
#include <stdio.h>
int checkbitpattern(int n){
int result = n^(n>>1);
if(((n+1)&n) == 0)
return 1;
else
return 0;
}
int main (){
int number = 4;
if(checkbitpattern == 1){
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