CP_SESSIONS

Bits Manipulation

View on GitHub

Bit Manipulation

Introduction

Bit manipulation is a technique used to manipulate the bits that make up a binary number. In competitive programming, this technique can be used to solve problems quickly and efficiently. Here, I will introduce you to bit manipulation and how it can be used in competitive programming.

Basic Bitwise Operators

The following are the basic bitwise operators you need to know:

  1. AND (&): The result of a & b is a number where each bit is set to 1 only if the corresponding bits of a and b are both 1. Otherwise, the bit is set to 0.
  2. OR (|): The result of a | b is a number where each bit is set to 1 if either the corresponding bit of a or b is 1. Otherwise, the bit is set to 0.
  3. XOR (^): The result of a ^ b is a number where each bit is set to 1 if the corresponding bits of a and b are different. Otherwise, the bit is set to 0.
  4. NOT (~): The result of ~a is a number where each bit is the complement of the corresponding bit in a. That is, if the bit in a is 0, the bit in the result is 1, and vice versa.

Bitwise Shift Operators

The following are the bitwise shift operators:

  1. Left Shift (<<): The result of a << b is a number where the bits of a are shifted left by b positions. The leftmost b bits are set to 0.
  2. Right Shift (>>): The result of a >> b is a number where the bits of a are shifted right by b positions. The rightmost b bits are set to 0.

Bit Manipulation Techniques

Here are some common bit manipulation techniques you can use in competitive programming:

  1. Setting a bit: To set the ith bit of a number n, you can use the expression n |= (1 << i).
  2. Clearing a bit: To clear the ith bit of a number n, you can use the expression n &= ~(1 << i).
  3. Checking if a bit is set: To check if the ith bit of a number n is set, you can use the expression n & (1 << i) != 0.
  4. Counting the number of set bits in a number: To count the number of set bits in a number n, you can use the following code snippet:
count = 0
while n:
    count += n & 1
    n >>= 1

Bit manipulation is a powerful technique that can be used to solve problems quickly and efficiently in competitive programming. By understanding the basic bitwise operators and bitwise shift operators, as well as common bit manipulation techniques, you will be able to solve problems that would otherwise be difficult or time-consuming to solve.

And we are here to learn it in practice and get benefit of using it.
Enjoy Bits Manipulation!

My Session @ ICPC SCU

Reading Materials

Video Materials

Practice problems