Master Bitwise Operations: From Basics to Classic Interview Problems

Introduction

Bitwise operations hide in the corners of programming languages, powerful yet mysterious. Interviewers often use them to test candidates, so this guide records essential knowledge to prepare you.

Understanding Bitwise Operations

All numbers are stored in binary; bitwise operations manipulate the binary bits directly.

Common operators are AND (&), OR (|), XOR (^), NOT (~), left shift (<<), right shift (>>), and unsigned right shift (>>>).

AND (&)

Rule: each bit is 1 only if both corresponding bits are 1. 0&0=0, 0&1=0, 1&1=1 Example: 2 & -2

OR (|)

Rule: each bit is 1 if at least one corresponding bit is 1. 0|0=0, 0|1=1, 1|1=1 Example: 2 | -2

XOR (^)

Rule: each bit is 1 if the corresponding bits differ. 0^0=0, 0^1=1, 1^1=0 Example: 2 ^ -2

NOT (~)

Rule: flips each bit (0 becomes 1, 1 becomes 0).

Shift Operators

Left shift (<<) adds zeros on the right; right shift (>>) replicates the sign bit; unsigned right shift (>>>) adds zeros on the left.

For <<, the value is multiplied by 2 for each shift.

For >>, positive numbers shift in zeros (division by 2), negative numbers shift in the sign bit (preserving negativity).

For >>>, zeros are always shifted in, potentially changing a negative number to positive.

Bitwise Tricks

Check Odd/Even

if (n & 1 == 1) {
    // n is odd
}

The last bit determines parity.

Swap Two Numbers Without Temp

a = a ^ b;
 b = a ^ b; // b becomes original a
 a = a ^ b; // a becomes original b

Binary Enumeration

Use binary masks to enumerate subsets efficiently.

Classic Bitwise Problems

Add Two Integers Without + - * /

Iteratively use XOR for sum without carry and AND shifted left for carry.

public int Add(int num1, int num2) {
    int a = num1 ^ num2;
    int b = (num1 & num2) << 1;
    if (b == 0) return a;
    else return Add(a, b);
}

Count Number of 1 Bits

Method 1: test each of the 32 bits.

public int NumberOf1(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        if ((n & (1 << i)) != 0) count++;
    }
    return count;
}

Method 2: repeatedly clear the lowest set bit.

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

Find Single Number (All Others Appear Twice)

public int singleNumber(int[] nums) {
    int value = 0;
    for (int num : nums) {
        value ^= num;
    }
    return value;
}

Find Single Number (All Others Appear Thrice)

Count bits at each position modulo 3.

public int singleNumber(int[] nums) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        int sum = 0;
        for (int num : nums) {
            if (((num >> i) & 1) == 1) sum++;
        }
        if (sum % 3 == 1) result |= (1 << i);
    }
    return result;
}

Find Two Unique Numbers (Others Appear Twice)

Use XOR to get a^b, find a differing bit, then separate the array.

public int[] singleNumbers(int[] nums) {
    int xor = 0;
    for (int num : nums) xor ^= num;
    int index = getFirst1(xor);
    int a = 0, b = 0;
    for (int num : nums) {
        if (((num >> index) & 1) == 0) a ^= num; else b ^= num;
    }
    return new int[]{a, b};
}
private int getFirst1(int val) {
    int index = 0;
    while ((val & 1) == 0 && index < 32) {
        val >>= 1;
        index++;
    }
    return index;
}

Conclusion

The presented bitwise fundamentals and classic problems provide a solid foundation for tackling interview questions and many algorithmic challenges. More advanced applications, such as game theory problems, will be shared in future articles.