One
Overview of Bitwise Operations
Bitwise operations are operations that directly manipulate the binary bits in memory, and are commonly used in low-level programming and high-performance computing. C++ provides six bitwise operators:
-
<span><span>&</span></span>: Bitwise AND (AND operation) -
<span><span>|</span></span>: Bitwise OR (OR operation) -
<span><span>^</span></span>: Bitwise XOR (XOR operation) -
<span><span>~</span></span>: Bitwise NOT (NOT operation) -
<span><span><<</span></span>: Left Shift (left shift operation) -
<span><span>>></span></span>: Right Shift (right shift operation)
[Bitwise Operator Precedence]
- Highest precedence:~ (Bitwise NOT), which is a unary operator;
- Next is:<< (left shift), >> (right shift);
- Then:& (Bitwise AND);
- Next is:^ (Bitwise XOR);
- Finally:| (Bitwise OR).
[Note] Bitwise operations only apply to integer types (such as int, char, long, etc.) and cannot be used with floating-point types.
Two
Detailed Explanation of Bitwise Operators
1. Bitwise AND (&):
[Operation Rule] The result is 1 only if both bits are 1; otherwise, the result is 0.
[Example Program]
int a = 5; // 0101
int b = 3; // 0011
int c = a & b; // 0001 (1)[Application Cases]
1. Determine Odd or Even: If (n & 1) == 0, then n is even;
2. Clear Specific Bit: n & ~(1 << k), clears the k-th bit.
2. Bitwise OR (|):
[Operation Rule] The result is 1 if at least one of the bits is 1; otherwise, the result is 0.[Example Program]
int a = 5; // 0101
int b = 3; // 0011
int c = a | b; // 0111 (7)[Application Cases]Set Specific Bit:n | (1 << k), sets the k-th bit to 1.
3. Bitwise XOR (^):
[Operation Rule]Result is 1 if the bits are different, 0 if they are the same.[Example Program]
int a = 5; // 0101
int b = 3; // 0011
int c = a ^ b; // 0110 (6)[Properties]1.a ^ a = 0;2.a ^ 0 = a;3. SatisfiesCommutative and Associative laws.[Application Cases]1. Swap Two Numbers: a ^= b; b ^= a; a ^= b;2. Find the Unique Non-Repeating Number (all other numbers appear twice).
4. Bitwise NOT (~):
[Operation Rule] 0 becomes 1, 1 becomes 0.[Example Program]
int a = 5; // 00000000 00000000 00000000 00000101
int b = ~a; // 11111111 11111111 11111111 11111010 (-6)To understand why the binary number <span><span>11111111 11111111 11111111 11111010</span></span> represents the number -6, it needs to be analyzed from the perspective ofTwo’s Complement representation.Because signed integers are represented in computers usingTwo’s Complement.Rules of Two’s Complement Representation:1. The highest bit is the sign bit: When the highest bit is 1, it indicates that the number is negative; when the highest bit is 0, it indicates that the number is positive.2. The Two’s Complement of a positive number: is the same as its original representation.3. The Two’s Complement of a negative number: is obtained by inverting the bits of its original representation and adding 1.[Analysis Process]1. The absolute value of -6 is 6, and the original representation of 6 is as follows:
00000000 00000000 00000000 000001102. Inverting the original representation gives the complement, as follows:
11111111 11111111 11111111 111110013. Adding 1 to the complement gives the Two’s Complement of -6 (i.e., the binary representation of -6):
11111111 11111111 11111111 111110105. Left Shift (<<):
[Operation Rule] Shifts the binary bits to the left, filling low bits with 0.[Example Program]
// Shift all binary bits of a to the left by 1 bit
int a = 5; // 0101
int b = a << 1; // 1010 (10)[Application Cases]Quickly multiply by powers of 2: n << m is equivalent to n * pow(2, m).
6. Right Shift (>>):
[Operation Rule] Shifts the binary bits to the right, filling high bits with 0.[Example Program]
// Shift all binary bits of a to the right by 1 bit
int a = 10; // 1010
int b = a >> 1; // 0101 (5)
int b = a >> 2; // 0010 (2) (rounding down)[Application Cases]Quickly divide by powers of 2: n >> m is equivalent to n / pow(2, m).[Note] The right shift operation for signed numbers may cause sign extension issues, which need to be particularly noted.
int a = -8; // Binary: 1111...1111000 (32 bits)
int b = a >> 1; // Binary: 1111...1111100 (-4) // Fill 1 on the left instead of 0Three
Classic Cases of Bitwise Operations
Example 1: Count the number of 1s in binary:
# include <bits/stdc++.h>
using namespace std;
int count_1(int n) {
// Count the number of 1s in binary
int cnt = 0; // Declare counting variable cnt
while (n) { // Continue counting as long as n is not 0
cnt++; // Increment counter by 1 each loop
n &= (n - 1); // Remove the lowest bit of 1
}
return cnt; // Return count result
}
int main() {
int n;
cin >> n;
cout << count_1(n) << endl;
return 0;
}Manually calculate, and it is easy to understand the counting algorithm.
Example 2: Determine if a positive integer is a power of 2:
# include <bits/stdc++.h>
using namespace std;
// Determine if a positive integer is a power of 2
bool isPowerOfTwo(int n) {
return (n > 0) && ((n & (n-1)) == 0);
}
int main() {
int n;
cin >> n;
cout << isPowerOfTwo(n) << endl;
return 0;
}Observe the characteristics of the binary representation of powers of 2, which makes it easy to determine.
Example 3: Swap the values of two variables:
# include <bits/stdc++.h>
using namespace std;
// Swap the values of two variables
void jiao_huan(int &a, int &b) {
a ^= b;
b ^= a;
a ^= b;
return ;
}
int main() {
int a, b;
cin >> a >> b;
jiao_huan(a, b); // Swap the values of a and b
cout << a << " " << b << endl;
return 0;
}Write it down on paper, calculate the example, and understand the commutative and associative properties of XOR operations.
Example 4: Find the number that appears an odd number of times (all others appear an even number of times):
# include <bits/stdc++.h>
using namespace std;
int nums[10];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> nums[i];
int ret = 0; // ret stores the final result, initialized to 0
for (int num : nums) { // Iterate through each number
ret ^= num; // Perform XOR operation with ret
}
cout << ret << endl; // The final result in ret is the number that appears an odd number of times
return 0;
}Flexible use of the commutative and associative properties of XOR operations.
Note: This case only applies when only one number appears an odd number of times, while all other numbers appear an even number of times; if multiple numbers appear an odd number of times, this method cannot be used directly.
Example 5: Bitmask Permission System:
const int READ = 1 << 0; // 0001
const int WRITE = 1 << 1; // 0010
const int EXEC = 1 << 2; // 0100
// Set permissions
int permissions = READ | WRITE; // 0011
// Check permissions
bool canRead = permissions & READ;
bool canExec = permissions & EXEC;
// Add permissions
permissions |= EXEC;
// Remove permissions
permissions &= ~WRITE;Linux system’s permission control is set this way, with the addition of the following three different granularities of permission control:File Owner (User),Group and Other Users (Others).
< This lesson ends here >
Previous Recommendations
C++ Programming for Kids (17) High Precision Algorithms (Multiplication and Division)
C++ Programming for Kids (16) High Precision Algorithms (Addition and Subtraction)
C++ Programming for Kids (15) Divide and Conquer Algorithms
C++ Programming for Kids (14) Recursive Algorithms
C++ Programming for Kids (13) Iterative Algorithms
C++ Programming for Kids (12) Sorting Algorithms (4) Counting Sort
200 – Eliminate the Enemy (J)
Python Programming for Kids (20) Divide and Conquer Algorithms
Python Programming for Kids (19) Recursion and Iteration
Scratch Version of “Gold Miner”(Paid)
J30-01 Knapsack Problem (Dynamic Programming)
Visual Impairment Training Mini Game – Fox Doodle(Paid)
J29 – Tower of Hanoi (Divide and Conquer)
Visual Impairment Training Mini Game – Find Text(Paid)
Scan the QR code to get
More Exciting Content
Little Xiao’s Programming for Kids
