Bit Manipulation Problems Master List 🎯

Welcome to the exciting world of Bit Manipulation! This guide is designed to help you master common problems related to bit manipulation, an essential skill for any serious programmer. 💡

Bit manipulation is a technique used to perform operations at the bit level, which can significantly improve the efficiency of algorithms, especially for tasks involving flags, masks, and shift operations.

Table of Contents

1. Understanding Binary Numbers

2. Bitwise Operations

   • 2.1 Bitwise AND (&)
   • 2.2 Bitwise OR (|)
   • 2.3 Bitwise XOR (^)
   • 2.4 Bitwise NOT (~)
   • 2.5 Bitwise Shift (<< and >>)
   • 2.6 Bitwise Operators with Examples

3. Bit Manipulation Problems

   • 3.1 Flipping Bits
   • 3.2 Counting Set Bits
   • 3.3 Checking if a Number is Power of Two
   • 3.4 Swapping Numbers without Temp Variable
   • 3.5 Finding the First Set Bit
   • 3.6 Toggling All Set Bits
   • 3.7 Finding the Highest Set Bit
   • 3.8 Finding Two Numbers that Differ by One Bit

Understanding Binary Numbers 📝

Before diving into bit manipulation, let's understand how numbers are represented in binary.

• In binary, each digit (bit) represents a power of 2.
• Starting from the rightmost bit (least significant bit, LSB), each bit corresponds to 2^0, 2^1, 2^2, and so on.

Example: The binary number 1011 represents the decimal number 12^3 + 02^2 + 12^1 + 12^0 = 11.

Bitwise Operations 📝

Bitwise AND (&)

The bitwise AND operation performs a logical AND on corresponding bits of two numbers.

Example:

1101 & 1010 = 1000

Bitwise OR (|)

The bitwise OR operation performs a logical OR on corresponding bits of two numbers.

Example:

1101 | 1010 = 1111

Bitwise XOR (^)

The bitwise XOR operation performs a logical XOR on corresponding bits of two numbers.

Example:

1101 ^ 1010 = 0111

Bitwise NOT (~)

The bitwise NOT operation inverts all the bits of a number.

Example:

~1101 = 1010

Bitwise Shift (<< and >>)

The bitwise shift operations shift the bits of a number to the left or right.

• << : Shifts bits to the left.
• >> : Shifts bits to the right.

Example:

1101 << 1 = 1110 1101 >> 1 = 0111

Bitwise Operators with Examples 📝

int num1 = 1101; int num2 = 1010; // Bitwise AND int result1 = num1 & num2; // 1000 // Bitwise OR int result2 = num1 | num2; // 1111 // Bitwise XOR int result3 = num1 ^ num2; // 0111 // Bitwise NOT int result4 = ~num1; // 1010 // Bitwise Shift Left int result5 = num1 << 1; // 1110 // Bitwise Shift Right int result6 = num1 >> 1; // 0111

Bit Manipulation Problems 💡

Flipping Bits 📝

Write a program to flip the bits of an integer.

Example:

Input: 1101 Output: 0010

Counting Set Bits 📝

Write a program to count the number of set bits (1s) in an integer.

Example:

Input: 1101 Output: 3

Checking if a Number is Power of Two 📝

Write a program to check if a number is a power of two.

Example:

Input: 8 Output: True

Swapping Numbers without Temp Variable 📝

Write a program to swap two numbers without using a temporary variable.

Example:

Input: num1 = 10, num2 = 20 Output: num1 = 20, num2 = 10

Finding the First Set Bit 📝

Write a program to find the position of the first set bit (first 1) in an integer.

Example:

Input: 1101 Output: 3

Toggling All Set Bits 📝

Write a program to toggle all set bits (1s) of an integer.

Example:

Input: 1101 Output: 0010

Finding the Highest Set Bit 📝

Write a program to find the position of the highest set bit (highest 1) in an integer.

Example:

Input: 1101 Output: 3

Finding Two Numbers that Differ by One Bit 📝

Write a program to find two numbers that differ by only one bit.

Example:

Input: 1101, 1010 Output: True