XQA
Back to Data Structures & Algorithms
2026-04-166 min read

Bit Manipulation (Data Structures & Algorithms)

Learn Bit Manipulation (Data Structures & Algorithms) step by step with clear examples and exercises.

Title: Bit Manipulation (Data Structures & Algorithms) Using Python

Why This Matters

Bit manipulation is a fundamental skill for programmers, playing a crucial role in interviews, real-world problem solving, and optimizing algorithms. It enables us to perform intricate operations on individual bits of data, significantly improving the efficiency of our solutions. Understanding bit manipulation can help you tackle problems related to data compression, encryption, and performance optimization.

Prerequisites

Before diving into bit manipulation, it's essential to have a strong understanding of the following concepts:

  1. Basic Python syntax and control structures (loops, conditionals)
  2. Data types (integers, floats, strings)
  3. Operators (arithmetic, logical, bitwise)
  4. Functions and modules
  5. Familiarity with Big O notation to analyze the time complexity of algorithms
  6. Understanding of basic data structures like arrays and linked lists

Core Concept

Understanding Binary Representation

Every number in a computer is represented as a sequence of bits (0s and 1s). For example, the decimal number 17 can be represented as binary:

17 (decimal) = 10001 (binary)

Each digit in the binary representation corresponds to a power of 2:

1 * 2^4 + 0 * 2^3 + 0 * 2^2 + 0 * 2^1 + 1 * 2^0 = 17

Bitwise Operators

Python provides several bitwise operators that allow us to perform operations on individual bits:

  • & (bitwise AND)
  • | (bitwise OR)
  • ^ (bitwise XOR)
  • ~ (bitwise NOT or complement)
  • << (left shift)
  • >> (right shift)

Let's explore each of these operators with examples:

Bitwise AND (&)

The bitwise AND operator compares each corresponding bit in two numbers and produces a 1 only if both bits are 1. For example:

x = 60 # binary: 1111000
y = 13 # binary: 1101
x & y # binary: 1100 (decimal: 12)

Bitwise OR (|)

The bitwise OR operator produces a 1 if either of the corresponding bits is 1. For example:

x = 60 # binary: 1111000
y = 13 # binary: 1101
x | y # binary: 1111001 (decimal: 61)

Bitwise XOR (^)

The bitwise XOR operator produces a 1 if the corresponding bits are different. For example:

x = 60 # binary: 1111000
y = 13 # binary: 1101
x ^ y # binary: 1010001 (decimal: 49)

Bitwise NOT (~)

The bitwise NOT operator inverts all the bits of a number. For example:

x = 60 # binary: 1111000
~x # binary: 00001111 (decimal: -61)

Left Shift (<<) and Right Shift (>>)

Left shift moves all bits of a number to the left by a specified amount, filling the vacated positions with zeros. Right shift moves all bits to the right, filling the vacated positions with the sign bit for signed integers or zeros for unsigned integers. For example:

x = 10 # binary: 1010
x << 2 # binary: 101000 (decimal: 40)
x >> 2 # binary: 000101 (decimal: 5)

Practical Applications of Bitwise Operations

Bit manipulation can be used in various practical scenarios, such as toggling a bit, checking if a number is a power of 2, finding the highest set bit, and implementing efficient data structures like Bloom filters.

Toggling a Bit (Flip-Flop)

To toggle a specific bit in an integer, we can use the bitwise XOR operator with a mask that isolates the target bit:

def flip_bit(n, pos):
return (n ^ (1 << pos))

Checking if a Number is a Power of 2

We can check if a number is a power of 2 using only bitwise operations by checking if the last set bit is also set in n - 1. If it's not, then n cannot be a power of 2.

def is_power_of_two(n):
return n != 0 and (n & (n - 1)) == 0

Finding the Highest Set Bit

To find the highest set bit in an integer, we can perform a binary search using bitwise AND operations to isolate the target bit:

def highest_set_bit(n):
if n == 0:
return -1

pos = 0
while n != 0:
n &= n - 1
pos += 1

return pos

Bitwise Operations and Strings

In Python, the bitwise operators perform byte-wise operations on strings, treating them as sequences of bytes rather than characters. For example:

s = "ABCD" # binary: 01000001 01000002 01000003 01000004
s & "EFGH" # binary: 00000000 00000000 00000000 01000000 (decimal: 128)

Worked Example

Let's implement a function that checks if a number is a power of 2 using only bitwise operations:

def is_power_of_two(n):
return n != 0 and (n & (n - 1)) == 0

In this example, we use the bitwise AND operator to check if the last set bit of n is also set in n - 1. If it's not, then n cannot be a power of 2.

Common Mistakes

  1. Forgetting that Python uses 0-indexing for arrays and strings.
  2. Assuming that the right shift operator (>>) preserves the sign bit for signed integers in Python, but it doesn't. Use the bitwise AND operator with 1 to check the sign bit:
x = -5 # binary: 1010
x >> 1 # binary: 0101 (Python) or 1011 (arithmetic shift, e.g., C++)
x & 1 # binary: 1 (Python) or 0 (arithmetic shift)
  1. Misunderstanding the behavior of the bitwise operators when applied to strings. In Python, the bitwise operators perform byte-wise operations on strings, treating them as sequences of bytes rather than characters. For example:
s = "ABCD" # binary: 01000001 01000002 01000003 01000004
s & "EFGH" # binary: 00000000 00000000 00000000 01000000 (decimal: 128)

Practice Questions

  1. Write a function to swap two numbers without using a temporary variable. Use bitwise operators.
  2. Implement a function that counts the number of set bits in an integer using only bitwise operations.
  3. Write a Python program to check if a given number is a prime using only bitwise operations.
  4. Implement a function that toggles all the bits in an integer using bitwise operators.
  5. Write a function to find the maximum number that can be represented with n bits, using only bitwise operations.
  6. Write a function to check if two integers have an odd number of common set bits (i.e., the XOR of the numbers has at least one 1).
  7. Implement a function that finds the rightmost set bit in an integer using only bitwise operations and without using the highest_set_bit function from above.
  8. Write a program to perform a binary search using only bitwise operators.
  9. Implement a function that checks if a given number is a palindrome (reads the same forwards and backwards) using only bitwise operations.
  10. Write a Python program to implement a simple encryption algorithm using bitwise XOR with a key.

FAQ

  1. Why do we need bitwise operators when we have if-else statements?
  • Bitwise operators allow us to perform complex operations on individual bits quickly and efficiently, which can significantly improve the performance of our algorithms in certain scenarios.
  1. What is the difference between left shift (<<) and right shift (>>) in Python?
  • Left shift moves all bits to the left by a specified amount, filling the vacated positions with zeros. Right shift moves all bits to the right, but it does not preserve the sign bit for signed integers in Python. Use the bitwise AND operator with 1 to check the sign bit if needed.
  1. Why is the bitwise XOR operation useful?
  • The bitwise XOR operation can be used to perform various tasks, such as finding the difference between two numbers, toggling bits, and implementing efficient data structures like Bloom filters.
  1. How can we use bitwise operators for data compression or encryption?
  • Bit manipulation techniques can be employed in data compression algorithms (e.g., Run-Length Encoding) and cryptographic protocols (e.g., RC4, AES). These applications use the ability to perform operations on individual bits quickly and efficiently.
Bit Manipulation (Data Structures & Algorithms) | Data Structures & Algorithms | XQA Learn