Code Templates

Master essential bit manipulation operations with these optimized templates. While often used as small utility functions, knowing these patterns by heart enables you to write highly efficient code without consulting documentation.

The “Bitwise Toolbelt” Template

This template collects the most common bitwise operations you will use in interviews: checking, setting, clearing, and toggling bits, as well as handling powers of two and counting bits.

Multi-Language Support:

class BitUtils {
    // 1. Check if the k-th bit is set (1)
    static checkBit(n, k) {
        return (n & (1 << k)) !== 0;
    }

    // 2. Set the k-th bit to 1
    static setBit(n, k) {
        return n | (1 << k);
    }

    // 3. Clear the k-th bit (set to 0)
    static clearBit(n, k) {
        return n & ~(1 << k);
    }

    // 4. Toggle the k-th bit (0 -> 1, 1 -> 0)
    static toggleBit(n, k) {
        return n ^ (1 << k);
    }

    // 5. Check if number is a power of 2
    // Explanation: Powers of 2 have only one bit set.
    // n-1 flips that bit and all lower bits.
    static isPowerOfTwo(n) {
        return n > 0 && (n & (n - 1)) === 0;
    }

    // 6. Count set bits (Brian Kernighan's Algorithm)
    // Time: O(number of set bits), Space: O(1)
    static countSetBits(n) {
        let count = 0;
        while (n !== 0) {
            n = n & (n - 1); // Clears the lowest set bit
            count++;
        }
        return count;
    }
}

class BitUtils:
    # 1. Check if the k-th bit is set (1)
    @staticmethod
    def check_bit(n: int, k: int) -> bool:
        return (n & (1 << k)) != 0

    # 2. Set the k-th bit to 1
    @staticmethod
    def set_bit(n: int, k: int) -> int:
        return n | (1 << k)

    # 3. Clear the k-th bit (set to 0)
    @staticmethod
    def clear_bit(n: int, k: int) -> int:
        return n & ~(1 << k)

    # 4. Toggle the k-th bit (0 -> 1, 1 -> 0)
    @staticmethod
    def toggle_bit(n: int, k: int) -> int:
        return n ^ (1 << k)

    # 5. Check if number is a power of 2
    @staticmethod
    def is_power_of_two(n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0

    # 6. Count set bits (Brian Kernighan's Algorithm)
    @staticmethod
    def count_set_bits(n: int) -> int:
        count = 0
        while n:
            n &= (n - 1)  # Clears the lowest set bit
            count += 1
        return count

public class BitUtils {
    // 1. Check if the k-th bit is set (1)
    public static boolean checkBit(int n, int k) {
        return (n & (1 << k)) != 0;
    }

    // 2. Set the k-th bit to 1
    public static int setBit(int n, int k) {
        return n | (1 << k);
    }

    // 3. Clear the k-th bit (set to 0)
    public static int clearBit(int n, int k) {
        return n & ~(1 << k);
    }

    // 4. Toggle the k-th bit (0 -> 1, 1 -> 0)
    public static int toggleBit(int n, int k) {
        return n ^ (1 << k);
    }

    // 5. Check if number is a power of 2
    public static boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }

    // 6. Count set bits (Brian Kernighan's Algorithm)
    public static int countSetBits(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1); // Clears the lowest set bit
            count++;
        }
        return count;
    }
}

#include <iostream>

class BitUtils {
public:
    // 1. Check if the k-th bit is set (1)
    static bool checkBit(int n, int k) {
        return (n & (1 << k)) != 0;
    }

    // 2. Set the k-th bit to 1
    static int setBit(int n, int k) {
        return n | (1 << k);
    }

    // 3. Clear the k-th bit (set to 0)
    static int clearBit(int n, int k) {
        return n & ~(1 << k);
    }

    // 4. Toggle the k-th bit (0 -> 1, 1 -> 0)
    static int toggleBit(int n, int k) {
        return n ^ (1 << k);
    }

    // 5. Check if number is a power of 2
    static bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }

    // 6. Count set bits (Brian Kernighan's Algorithm)
    static int countSetBits(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1); // Clears the lowest set bit
            count++;
        }
        return count;
    }
};

package bitmanipulation

// 1. Check if the k-th bit is set (1)
func CheckBit(n, k int) bool {
    return (n & (1 << k)) != 0
}

// 2. Set the k-th bit to 1
func SetBit(n, k int) int {
    return n | (1 << k)
}

// 3. Clear the k-th bit (set to 0)
func ClearBit(n, k int) int {
    return n & ^(1 << k) // Go's unary XOR is NOT operator
}

// 4. Toggle the k-th bit (0 -> 1, 1 -> 0)
func ToggleBit(n, k int) int {
    return n ^ (1 << k)
}

// 5. Check if number is a power of 2
func IsPowerOfTwo(n int) bool {
    return n > 0 && (n & (n - 1)) == 0
}

// 6. Count set bits (Brian Kernighan's Algorithm)
func CountSetBits(n int) int {
    count := 0
    for n != 0 {
        n = n & (n - 1)
        count++
    }
    return count
}

class BitUtils
  # 1. Check if the k-th bit is set (1)
  def self.check_bit(n, k)
    (n & (1 << k)) != 0
  end

  # 2. Set the k-th bit to 1
  def self.set_bit(n, k)
    n | (1 << k)
  end

  # 3. Clear the k-th bit (set to 0)
  def self.clear_bit(n, k)
    n & ~(1 << k)
  end

  # 4. Toggle the k-th bit (0 -> 1, 1 -> 0)
  def self.toggle_bit(n, k)
    n ^ (1 << k)
  end

  # 5. Check if number is a power of 2
  def self.is_power_of_two(n)
    n > 0 && (n & (n - 1)) == 0
  end

  # 6. Count set bits (Brian Kernighan's Algorithm)
  def self.count_set_bits(n)
    count = 0
    while n != 0
      n &= (n - 1) # Clears the lowest set bit
      count += 1
    end
    count
  end
end

Code Breakdown

The trickiest part of typical bit manipulation problems is often the n & (n - 1) operation, which is central to “Kernighan’s Algorithm” for counting bits and for checking powers of two.

Here is how n = n & (n - 1) works visually for n = 12 (1100 binary):

  graph TD
    start["Start: n = 12 (1100)"]
    step1["n - 1 = 11 (1011)"]
    step2["Result = 12 & 11"]
    final["New n = 8 (1000)"]

    start -->|Subtract 1| step1
    start -->|Bitwise AND| step2
    step1 --> step2
    step2 -->|Rightmost bit cleared| final

    style start fill:#e1f5fe,stroke:#01579b
    style step1 fill:#fff9c4,stroke:#fbc02d
    style final fill:#e8f5e9,stroke:#2e7d32

Variations

Generating All Subsets

A powerful application of bit manipulation is iterating through all subsets of an array. If an array has N elements, there are 2^N subsets. We can use the bits of a number from 0 to 2^N - 1 as a mask.

function generateSubsets(nums) {
    const output = [];
    const n = nums.length;
    // 1 << n is 2^n
    for (let i = 0; i < (1 << n); i++) {
        const subset = [];
        for (let j = 0; j < n; j++) {
            // Check if j-th bit is set in i
            if ((i & (1 << j)) !== 0) {
                subset.push(nums[j]);
            }
        }
        output.push(subset);
    }
    return output;
}

def generate_subsets(nums):
    output = []
    n = len(nums)
    # 1 << n is 2^n
    for i in range(1 << n):
        subset = []
        for j in range(n):
            # Check if j-th bit is set in i
            if (i & (1 << j)) != 0:
                subset.append(nums[j])
        output.append(subset)
    return output

import java.util.*;

public class Subsets {
    public List<List<Integer>> generateSubsets(int[] nums) {
        List<List<Integer>> output = new ArrayList<>();
        int n = nums.length;

        for (int i = 0; i < (1 << n); i++) {
            List<Integer> subset = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    subset.add(nums[j]);
                }
            }
            output.add(subset);
        }
        return output;
    }
}

#include <vector>
#include <cmath>

class Subsets {
public:
    std::vector<std::vector<int>> generateSubsets(std::vector<int>& nums) {
        std::vector<std::vector<int>> output;
        int n = nums.size();

        for (int i = 0; i < (1 << n); ++i) {
            std::vector<int> subset;
            for (int j = 0; j < n; ++j) {
                if ((i & (1 << j)) != 0) {
                    subset.push_back(nums[j]);
                }
            }
            output.push_back(subset);
        }
        return output;
    }
};

package subsets

func GenerateSubsets(nums []int) [][]int {
    output := [][]int{}
    n := len(nums)

    for i := 0; i < (1 << n); i++ {
        subset := []int{}
        for j := 0; j < n; j++ {
            if (i & (1 << j)) != 0 {
                subset = append(subset, nums[j])
            }
        }
        output = append(output, subset)
    }
    return output
}

def generate_subsets(nums)
  output = []
  n = nums.length

  (0...(1 << n)).each do |i|
    subset = []
    (0...n).each do |j|
      subset << nums[j] if (i & (1 << j)) != 0
    end
    output << subset
  end
  output
end

Practice

Apply these templates to the following problems: