C#相邻位交换代码疑问：0x2AAAAAAA与0x15555555原理解析

Great question about this classic bitwise operation trick—let's break down each of your questions clearly, since this is a perfect example of how targeted bitmasks solve low-level problems efficiently.

Your Questions Answered #

1. What's the relationship between the number of 5s/As and the bit width? #

First, remember that each hexadecimal digit maps to 4 binary bits. The masks 0x15555555 and 0x2AAAAAAA are 32-bit masks (8 hex digits × 4 bits = 32 bits total).

• 5 in hex is 0101 in binary, and A is 1010 in binary.
• To cover all 32 bits, we repeat these 4-bit patterns 8 times. That's why you see 8 instances of 5 in 0x15555555 and 8 instances of A in 0x2AAAAAAA—each repetition fills the next 4 bits of the 32-bit mask.

2. Why use A and 5 as mask characters? #

The goal here is to isolate even-indexed and odd-indexed bits (bit numbering starts at 0 from the right, the least significant bit):

• 5 (0101) has 1s in the even positions of its 4-bit block (positions 0 and 2). Scaling this to 32 bits with 0x15555555 gives us a mask where every even bit (0, 2, 4, ..., 30) is 1.
• A (1010) has 1s in the odd positions of its 4-bit block (positions 1 and 3). Scaling to 32 bits with 0x2AAAAAAA gives a mask where every odd bit (1, 3, 5, ..., 31) is 1.

These masks let us cleanly split the original number into two separate groups: even bits and odd bits. We can then shift each group to swap their positions (shift even bits left by 1, odd bits right by 1) and combine them back together.

3. What's the purpose of the prefixes 2 and 1? #

The prefixes ensure our masks are full 32-bit values:

• Without the 2 prefix, 0xAAAAAAA would only be 28 bits long. Adding 2 (binary 10) at the start fills the highest two bits, making it a complete 32-bit mask where the 31st bit (the highest bit in a 32-bit signed integer) is 1, and the 30th is 0—continuing the 1010... pattern all the way to the top.
• Similarly, the 1 prefix in 0x15555555 adds 01 at the start, filling the highest two bits to maintain the 0101... pattern across all 32 bits, with the 31st bit as 0 and 30th as 1.

This ensures no bits are missed when we extract and swap adjacent pairs.

4. Advanced bitwise operation knowledge and recommended resources #

If you want to dive deeper into bitwise tricks, here are some top trusted references:

• Book: Hacker's Delight: This is the definitive guide to bitwise operations, packed with optimized tricks for arithmetic, logic, and data manipulation—exactly the kind of swap you're working with, plus hundreds more.
• Computer Architecture Textbooks: Most standard comp arch books (like Computer Organization and Design by Patterson & Hennessy) have detailed sections on bitwise operations, explaining how they map to hardware and why they're so efficient.
• Programming Competition Tutorials: Many competitive programming resources focus on bitwise techniques for problems like state compression, fast counting, and bitmask DP—these are great for practicing real-world applications.
• LeetCode/Codeforces Problems: Solve problems tagged with "bit manipulation" to apply what you learn; platforms like these have tons of problems ranging from basic to advanced.

内容的提问来源于stack exchange，提问作者Tom Buck