如何用按位AND修改模数？如何用按位&与位移实现x%10、x/10？

Great questions—let's break these down clearly, since bitwise tricks like these are super useful for performance-critical code!

First, a key caveat: bitwise AND can only replace the modulus operation when your modulus is a power of 2. Here's the logic behind it:

• For a modulus m = 2^k, its binary form is a single 1 followed by k zeros (e.g., 8 is 1000 in binary). Subtract 1, and you get m-1—a number with k consecutive 1s (7 is 0111).
• When you run x & (m-1), you're masking out all bits of x except the last k bits. Those last k bits are exactly the remainder when x is divided by 2^k—which is exactly what x % m gives you.

To adjust the modulus, you just swap out m for another power of 2 and use its corresponding m-1 value in the AND:

• If you were using modulus 8 (2^3) with x & 7, switch to modulus 16 (2^4) by using x & 15.
• To drop to modulus 4 (2^2), use x & 3 instead.

Important note: This trick doesn't work for non-powers of 2. If your modulus is something like 10 or 7, bitwise AND alone can't replace the modulus operation—you'll need other bitwise or arithmetic hacks.

Since 10 isn't a power of 2, we can't use a simple AND for x%10. Instead, we combine shifts, multiplication (via precomputed constants), and subtraction to get the job done efficiently.

x/10 (Integer Division by 10) #

For 32-bit unsigned integers, a fast way to compute division by 10 uses a precomputed constant that approximates 1/10 * 2^32, then shifts right by 32 bits. Here's how it works:

• The constant 0x1999999A is (2^32 + 6)/10, which is a precise approximation of 2^32 / 10.
• Multiplying x by this constant gives a 64-bit result; shifting right by 32 bits effectively divides by 2^32, leaving us with the integer division of x by 10.

Example code (C-like):

uint32_t divide_by_10(uint32_t x) {
    return (uint32_t)((uint64_t)x * 0x1999999A >> 32);
}

For 64-bit integers, you'd use the constant 0x199999999999999A instead and shift right by 64 bits.

x%10 (Modulo 10) #

Once you have x/10, calculating x%10 is easy using the math relationship: x%10 = x - (x/10)*10. We can compute (x/10)*10 with shifts (since 10 = 8 + 2 = 2^3 + 2^1):

uint32_t mod_10(uint32_t x) {
    uint32_t div_result = divide_by_10(x);
    return x - ((div_result << 3) + (div_result << 1)); // Same as div_result * 10
}

If you want to squeeze out a bit more performance, you can inline the division logic directly into the modulo function, but splitting it keeps the code readable.

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