Learn these 10 Bitwise Tricks Or Regret Later | Competitive Programming Tricks Part 2

Summary

This video delves into essential bitwise tricks and operations, focusing on XOR, AND, and set bit counting techniques. It covers how XOR can be used to manipulate values, toggle between two numbers, and determine parity of set bits. Key properties of XOR and AND operations are explained, such as how to express the sum of two numbers using these operations. For C++ users, it introduces the efficient built-in `__builtin_popcount()` function to count set bits in constant time. These tips are valuable for competitive programmers looking to enhance their problem-solving efficiency with bitwise operations.

Takeaways

• 😀 XOR of two numbers can determine if the total number of set bits is even or odd.
• 😀 If the sum of set bits in two numbers is even, the XOR result will also have an even number of set bits.
• 😀 You can switch between two values (like 10 and 5) using XOR in a single operation.
• 😀 The formula for adding two numbers using XOR and AND is: a + b = (a XOR b) + 2 * (a AND b).
• 😀 XOR can remove common set bits, leaving only the non-matching bits.
• 😀 If you toggle a value using XOR (like 10 XOR 5), it will switch to the other value if they are equal.
• 😀 C++ has a built-in function `__builtin_popcount()` to count the number of set bits in a number in O(1) time.
• 😀 For C++ users, instead of iterating over bits to count set bits, you can use `__builtin_popcount()` for efficiency.
• 😀 The formula `a + b = a XOR b + 2 * (a AND b)` helps to break down addition using bitwise operations.
• 😀 For larger numbers (long long), use `__builtin_popcountll()` in C++ to count set bits efficiently.

Q & A

What is the relationship between XOR and the number of set bits in a number?

XOR can be used to determine the number of set bits in two numbers. The XOR of two numbers cancels out the bits that are the same, and only leaves bits that are different. By counting the number of 1s in the result of an XOR operation, we can find the number of set bits in the numbers being XORed.

How does XOR work when applied to two even or odd numbers?

If you XOR two even numbers or two odd numbers, the result will be an even number. Conversely, if one number is even and the other is odd, the XOR result will be odd.

What is the significance of the formula `A + B = A ⊕ B + 2 * (A & B)`?

This formula shows how addition of two numbers can be broken down into bitwise operations. `A ⊕ B` handles the non-overlapping bits (where one bit is 1 and the other is 0), and `2 * (A & B)` handles the carry bits (where both bits are 1). This is a key insight into how addition works at the bit level.

What is the advantage of using the `popcount` function in C++ for counting set bits?

The `popcount` function in C++ allows for an efficient way to count the number of set bits in a number. It performs this operation in constant time (O(1)), as opposed to iterating through each bit, which would take logarithmic time (O(log n)).

How can you toggle between two values (like 10 and 5) using XOR?

You can toggle between two values using XOR by applying `X = 10 ^ 5 ^ X`. If `X` is 10, XOR with 10 will cancel it out and return 5; if `X` is 5, XOR with 5 will cancel it out and return 10. This method avoids conditional statements and works in one step.

What happens when you XOR two binary numbers that have the same bits?

When you XOR two binary numbers that have the same bits at a position, the result for that bit will be 0. For example, `1 XOR 1 = 0` and `0 XOR 0 = 0`. This property allows XOR to cancel out matching bits.

Why is the number of set bits in a XOR operation sometimes odd or even?

The number of set bits in a XOR operation is determined by the parity of the sum of the set bits from both numbers. If the sum is odd, the result will have an odd number of set bits, and if the sum is even, the result will have an even number of set bits.

What are the uses of the XOR operation in competitive programming?

XOR is frequently used in competitive programming for tasks such as finding the number of set bits in a number, efficiently toggling between two values, and solving problems related to parity and bitwise arithmetic. It is especially useful for optimizing algorithms that require bitwise manipulation.

What are the two properties of bitwise addition mentioned in the video?

The two properties of bitwise addition discussed are: 1) `A + B = A ⊕ B + 2 * (A & B)`, which computes the sum by combining XOR and AND operations. 2) `A ⊕ B + (A & B)`, which adds non-overlapping bits once and overlapping bits twice.

Why is the formula `A + B = A ⊕ B + 2 * (A & B)` useful in programming?

This formula is useful because it allows us to break down the addition of two numbers into efficient bitwise operations. Instead of performing regular addition, this formula handles the non-carrying and carrying parts separately using XOR and AND, which is particularly valuable in low-level programming or when optimizing algorithms.