Algo Infinity Verse

⚡ Learn Bit Manipulation

Optimize performance with binary operations

0 / 5 topics completed

Binary Basics

At the lowest level, all data in a computer is represented as sequences of 0s and 1s, called bits. Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a word.

Binary Representation

A decimal number is converted to binary by dividing it by 2 repeatedly and taking the remainders. For example, the decimal number 5 is 101 in binary.

Bit manipulation can be extremely fast because it is directly supported by the processor. It is often used in low-level systems programming, cryptography, and competitive programming to optimize code execution speed and reduce memory consumption.

Bitwise Operators

Programming languages provide bitwise operators to interact with binary representations directly. Here are the core operators in C++/Java/Python:

Operator	Name	Description	Example (A=5, B=3)
`&`	AND	1 if both bits are 1, else 0	`5 & 3 = 1` (0101 & 0011 = 0001)
`\|`	OR	1 if at least one bit is 1, else 0	`5 \| 3 = 7` (0101 \| 0011 = 0111)
`^`	XOR	1 if bits are different, else 0	`5 ^ 3 = 6` (0101 ^ 0011 = 0110)
`~`	NOT	Inverts all bits (0 becomes 1, 1 becomes 0)	`~5 = -6` (in 2's complement)
`<<`	Left Shift	Shifts bits left by n positions (multiplies by 2^n)	`5 << 1 = 10` (1010)
`>>`	Right Shift	Shifts bits right by n positions (divides by 2^n)	`5 >> 1 = 2` (0010)

💡

XOR Property: The XOR operator has a very special property: A ^ A = 0 and A ^ 0 = A. This is widely used in finding missing or unique elements in an array!

Common Tricks

Bitwise operators allow for elegant and fast solutions to common problems.

1. Check if a number is even or odd

Instead of using modulo (n % 2 == 0), we can check the least significant bit. If it's 1, the number is odd. If it's 0, it's even.

cpp

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

2. Check if a number is a power of 2

Powers of 2 have exactly one bit set to 1 in their binary representation. If we subtract 1 from a power of 2, all bits after the set bit become 1, and the set bit becomes 0. Doing an AND operation between n and n - 1 will result in 0.

python

def is_power_of_two(n):
    # n must be positive, and n & (n-1) must be 0
    return n > 0 and (n & (n - 1)) == 0

3. Counting set bits (Brian Kernighan's Algorithm)

To count how many 1s are in a binary representation, we can repeatedly clear the lowest set bit using n & (n - 1) until the number becomes 0.

java

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

Applications

Where are bitwise operations used in real-world scenarios?

Bit Masking: Using a mask to keep, set, or clear specific bits in a flag byte (e.g. file permissions).
Cryptography: Algorithms like AES and SHA heavy rely on shifts, XORs, and other bitwise operations for scrambling data.
Data Compression: Packing multiple boolean or small integer values into a single integer.
Competitive Programming: Solving subset generation problems using bit sequences from 0 to 2^N - 1.

Practice Exercises

Test your knowledge with these standard bit manipulation problems!

Find the Single Number

Given an array of integers where every element appears twice except for one, find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space.

We can use the XOR property: A ^ A = 0. If we XOR all elements in the array, the duplicates will cancel each other out, leaving only the single number.

cpp

int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

Reverse Bits

Reverse the bits of a given 32 bits unsigned integer.

We can extract the lowest bit of n using n & 1, add it to our result using left shift, then shift n to the right by 1 to get the next bit.