Bit Operations and Manipulation in C++ for Competitive Programming

Introduction

• Bitwise operations are used to manipulate data at the bit level. They are faster and more efficient compared to other arithmetic operations.
• Common bitwise operations include AND, OR, XOR, NOT, LEFT SHIFT, and RIGHT SHIFT.

Basic Bitwise Operators

1. AND (&)
   • Used to set specific bits to 0.
   • Example: a & b
2. OR (|)
   • Used to set specific bits to 1.
   • Example: a | b
3. XOR (^)
   • Used to flip specific bits.
   • Example: a ^ b
4. NOT (~)
   • Used to invert all bits.
   • Example: ~a
5. Left Shift (<<)
   • Shifts bits to the left, equivalent to multiplying by 2.
   • Example: a << 1
6. Right Shift (>>)
   • Shifts bits to the right, equivalent to dividing by 2.
   • Example: a >> 1

Common Bit Manipulation Techniques

1. Check if a number is odd or even

   bool isOdd(int x) {
       return x & 1;
   }
   
   

2. Get the i-th bit

   bool getBit(int x, int i) {
       return (x & (1 << i)) != 0;
   }
   
   

3. Set the i-th bit

   void setBit(int &x, int i) {
       x |= (1 << i);
   }
   
   

4. Clear the i-th bit

   void clearBit(int &x, int i) {
       x &= ~(1 << i);
   }
   
   

5. Toggle the i-th bit

   void toggleBit(int &x, int i) {
       x ^= (1 << i);
   }
   
   

6. Count the number of set bits (Hamming Weight)

   int countSetBits(int x) {
       int count = 0;
       while (x) {
           count += x & 1;
           x >>= 1;
       }
       return count;
   }
   
   

Advanced Bit Manipulation Techniques

1. Check if a number is a power of 2

   bool isPowerOfTwo(int x) {
       return x && !(x & (x - 1));
   }