In the realm of competitive programming, efficiency is key. Bitwise operations are among the fastest operations available, often outperforming traditional arithmetic operations like addition, subtraction, multiplication, and division. In this article, we will explore ten essential bitwise tricks that every competitive programmer should know. ## 1. Checking Even or Odd Numbers A common method to check if a number is even or odd is to use the modulus operator: ```cpp if (x % 2 == 0) { // x is even } else { // x is odd } ``` However, this approach is slower than using bitwise operations. Instead, you can check the least significant bit (LSB) of the number: ```cpp if (x & 1) { // x is odd } else { // x is even } ``` This method is faster and operates in constant time, O(1). ## 2. Checking if a Number is a Power of Two To determine if a number is a power of two, you can use the following bitwise trick: ```cpp if (x && !(x & (x - 1))) { // x is a power of two } ``` This works because a power of two has exactly one bit set in its binary representation. The expression `x & (x - 1)` will be zero if x is a power of two. Note that you should handle the case where x is zero separately, as zero is not a power of two. ## 3. Manipulating the k-th Bit To check if the k-th bit of a number is set, you can use: ```cpp if (x & (1 << k)) { // k-th bit is set } ``` To toggle the k-th bit, use the XOR operator: ```cpp x ^= (1 << k); ``` To set the k-th bit: ```cpp x |= (1 << k); ``` To unset the k-th bit: ```cpp x &= ~(1 << k); ``` ## 4. Multiplying or Dividing by Powers of Two You can efficiently multiply or divide a number by powers of two using bit shifts. For example: - To divide by 2^k: ```cpp x >>= k; // equivalent to x / (2^k) ``` - To multiply by 2^k: ```cpp x <<= k; // equivalent to x * (2^k) ``` This method is much faster than using the division or multiplication operators. ## 5. Finding x Modulo 2^k To compute `x % (2^k)` efficiently, use: ```cpp result = x & ((1 << k) - 1); ``` This operation extracts the last k bits of x, which is equivalent to calculating `x modulo 2^k`. ## 6. Swapping Two Numbers Without a Temporary Variable You can swap two numbers using the XOR operator without needing a temporary variable: ```cpp x ^= y; y ^= x; x ^= y; ``` This method is efficient and avoids the overhead of using an additional variable. ## 7. Properties of Set Bits A useful property in competitive programming is that if the number of set bits in a is X and in b is Y, then the number of set bits in `a ^ b` (XOR) is even if X + Y is even, and odd if X + Y is odd. This can help in solving problems related to parity and bit manipulation. ## 8. Toggling Between Two Values If you want to toggle a variable between two values, say 5 and 10, you can do it in one line: ```cpp x = 10 ^ 5 ^ x; ``` This will switch x between 5 and 10 based on its current value. ## 9. Addition Using Bitwise Operators You can express addition using bitwise operations: ```cpp int add(int a, int b) { while (b != 0) { int carry = a & b; a = a ^ b; b = carry << 1; } return a; } ``` This method uses XOR to add without carrying and AND to find the carry, which is then shifted left. ## 10. Counting Set Bits in C++ In C++, you can count the number of set bits in a number using the built-in function `__builtin_popcount(x)`, which operates in O(1) time: ```cpp int count = __builtin_popcount(x); ``` For long long integers, use `__builtin_popcountll(x)`. ## Conclusion These ten bitwise tricks can significantly enhance your efficiency as a competitive programmer. By mastering these techniques, you can solve problems faster and with less computational overhead. Start incorporating these tricks into your coding practice, and you'll likely see improvements in your performance in competitive programming contests.