Bitwise Algorithms | Practice Problems

This page compiles the core practice problems for Bitwise Algorithms. Working through these problems will help you master the key patterns of bit manipulation—such as masking, bit-shifting, and leveraging the mathematical properties of XOR.

1. Check if K-th Bit is Set or Not

Given a number n and a position k (1-indexed), check if the k-th bit of n is set (i.e., equal to 1) or not.

Examples

Input: n = 5, k = 1 $\rightarrow$ Output: "YES" (5 in binary is 101; the 1st bit is 1)
Input: n = 8, k = 2 $\rightarrow$ Output: "NO" (8 in binary is 1000; the 2nd bit is 0)

Naive Approach (Repeated Division)

We can repeatedly divide n by 2 (which is equivalent to shifting right by 1) until the target k-th bit reaches the Least Significant Bit (LSB) position, then check if it is 1.

function isKthBitSetNaive(n, k) {
    if (n === 0 && k > 1) return "NO";
    for (let i = 1; i < k; i++) {
        n = Math.floor(n / 2);
    }
    return (n % 2 !== 0) ? "YES" : "NO";
}

Time Complexity: O(k)
Auxiliary Space: O(1)

Efficient Approach (Using Left Shift / Masking)

We shift 1 left by k - 1 positions to create a bitmask where only the k-th bit is set, and perform a Bitwise AND.

function isKthBitSetLeftShift(n, k) {
    return ((n & (1 << (k - 1))) !== 0) ? "YES" : "NO";
}

Time Complexity: O(1)
Auxiliary Space: O(1)

Efficient Approach (Using Right Shift)

We shift the k-th bit of n right by k - 1 positions to align it with the LSB, and perform a Bitwise AND with 1.

function isKthBitSetRightShift(n, k) {
    return (((n >> (k - 1)) & 1) === 1) ? "YES" : "NO";
}

Time Complexity: O(1)
Auxiliary Space: O(1)

2. Count Set Bits

Given a positive integer n, count the number of set bits (1s) in its binary representation.

Examples

Input: n = 5 (Binary: 101) $\rightarrow$ Output: 2
Input: n = 7 (Binary: 111) $\rightarrow$ Output: 3

Naive Approach (Iterate through all bits)

Check the LSB of n, increment the counter if it's set, and shift n right. Repeat until n becomes 0.

function countSetBitsNaive(n) {
    let res = 0;
    while (n > 0) {
        if ((n & 1) === 1) res++;
        n = n >> 1;
    }
    return res;
}

Time Complexity: O(log n) (proportional to total number of bits)
Auxiliary Space: O(1)

Efficient Approach (Brian Kernighan's Algorithm)

Instead of checking every bit, we can count only the set bits by clearing the rightmost set bit in each step using n = n & (n - 1).

function countSetBitsEfficient(n) {
    let res = 0;
    while (n > 0) {
        n = n & (n - 1); // Clears the rightmost set bit
        res++;
    }
    return res;
}

Time Complexity: O(set bits count)
Auxiliary Space: O(1)

Optimal Approach (Lookup Table for O(1) Time)

Precompute the number of set bits for all possible 8-bit numbers (0 to 255). For any 32-bit integer, we split it into four 8-bit chunks, look up the set bit count for each, and sum them.

let table = new Array(256);
 
function initializeTable() {
    table[0] = 0;
    for (let i = 1; i < 256; i++) {
        table[i] = (i & 1) + table[Math.floor(i / 2)];
    }
}
 
function countSetBitsLookup(n) {
    if (table[0] === undefined) initializeTable();
    return table[n & 0xff] + 
           table[(n >> 8) & 0xff] + 
           table[(n >> 16) & 0xff] + 
           table[(n >> 24) & 0xff];
}

Time Complexity: O(1)
Auxiliary Space: O(1) (using a fixed-size precomputed table of 256 elements)

3. Power of Two

Check if a given positive integer n is a power of 2.

Examples

Input: n = 4 $\rightarrow$ Output: true ($2^2 = 4$)
Input: n = 6 $\rightarrow$ Output: false

Naive Approach (Repeated Division)

Divide the number by 2 repeatedly as long as it's even. If it reduces to 1, it is a power of 2.

function isPowerOfTwoNaive(n) {
    if (n <= 0) return false;
    while (n !== 1) {
        if (n % 2 !== 0) return false;
        n = Math.floor(n / 2);
    }
    return true;
}

Time Complexity: O(log n)
Auxiliary Space: O(1)

Efficient Approach (Using Brian Kernighan's Property)

A power of 2 has exactly one set bit in its binary representation. If we clear this set bit using n & (n - 1), the result must be 0.

function isPowerOfTwoEfficient(n) {
    return n > 0 && (n & (n - 1)) === 0;
}

Time Complexity: O(1)
Auxiliary Space: O(1)

4. One Odd Occurring

Given an array of integers where all numbers occur an even number of times except for one number, find that single odd-occurring number.

Examples

Input: arr = [1, 2, 3, 2, 3, 1, 3] $\rightarrow$ Output: 3
Input: arr = [5, 7, 2, 7, 5, 2, 5] $\rightarrow$ Output: 5

Naive Approach (Nested Loops)

Count the occurrences of each element in the array using nested loops. If the count of an element is odd, return it.

function getOddOccurrenceNaive(arr) {
    const n = arr.length;
    for (let i = 0; i < n; i++) {
        let count = 0;
        for (let j = 0; j < n; j++) {
            if (arr[i] === arr[j]) count++;
        }
        if (count % 2 !== 0) return arr[i];
    }
    return -1;
}

Time Complexity: O(n^2)
Auxiliary Space: O(1)

Efficient Approach (Using XOR)

XORing any number with itself cancels it out (x ^ x = 0), and XORing with 0 preserves it (x ^ 0 = x). Therefore, XORing all elements together cancels out the even-occurring numbers and leaves the single odd-occurring one.

function getOddOccurrenceEfficient(arr) {
    let res = 0;
    for (let num of arr) {
        res = res ^ num;
    }
    return res;
}

Time Complexity: O(n)
Auxiliary Space: O(1)

5. Two Odd Occurring

Given an array where all elements appear an even number of times except for exactly two elements which occur an odd number of times, find these two elements.

Examples

Input: arr = [12, 23, 34, 12, 12, 23, 12, 45] $\rightarrow$ Output: 34 and 45
Input: arr = [10, 20] $\rightarrow$ Output: 10 and 20

Naive Approach

Iterate through the array and count frequencies using nested loops, printing elements that have an odd count.

function printTwoOddNaive(arr) {
    const n = arr.length;
    for (let i = 0; i < n; i++) {
        let count = 0;
        for (let j = 0; j < n; j++) {
            if (arr[i] === arr[j]) count++;
        }
        if (count % 2 !== 0) {
            console.log(arr[i]);
        }
    }
}

Time Complexity: O(n^2)
Auxiliary Space: O(1)

Efficient Approach (XOR Partitioning)

XOR all numbers in the array. Even occurrences cancel out, leaving xorAll = x ^ y (where x and y are the two odd-occurring numbers).
Find the rightmost set bit in xorAll using set_bit = xorAll & ~(xorAll - 1). This set bit indicates that x and y have different bits at this position (one has 1, the other has 0).
Partition the array elements into two groups based on whether this specific bit is set or not, and XOR them separately to isolate x and y.

function printTwoOddEfficient(arr) {
    let xorAll = 0;
    for (let num of arr) {
        xorAll ^= num;
    }
    
    // Get the rightmost set bit of xorAll
    let set_bit = xorAll & ~(xorAll - 1);
    
    let x = 0, y = 0;
    for (let num of arr) {
        if ((num & set_bit) !== 0) {
            x ^= num; // Group 1: target bit is set
        } else {
            y ^= num; // Group 2: target bit is unset
        }
    }
    
    console.log("The two odd elements are " + x + " & " + y);
    return [x, y];
}

Time Complexity: O(n)
Auxiliary Space: O(1)

6. Power Set using Bitwise

Generate all possible subsets (the power set) of a given set of n elements iteratively.

Example

Input: ['a', 'b', 'c']
Output Subsets: "", "a", "b", "ab", "c", "ac", "bc", "abc"

Iterative Bitwise Approach

A set of size n has 2^n subsets. We can map each number from 0 to 2^n - 1 to a subset. The j-th bit of the number indicates whether the j-th element of the set is present in the subset.

function printPowerSet(set) {
    const n = set.length;
    const powSetSize = 1 << n; // 2^n
    
    for (let counter = 0; counter < powSetSize; counter++) {
        let subset = "";
        for (let j = 0; j < n; j++) {
            // If the j-th bit in counter is set, include set[j]
            if ((counter & (1 << j)) !== 0) {
                subset += set[j];
            }
        }
        console.log(subset === "" ? '"" (Empty set)' : subset);
    }
}

Time Complexity: O(n * 2^n)
Auxiliary Space: O(1) (or O(n * 2^n) if storing the subsets)

Bit Algorithms | Important Tactics Bit Manipulation