Bit Manipulation Interview Problems for Embedded Engineers

Bit manipulation is the most embedded-specific coding topic. You use bitwise operations daily for register configuration, protocol field packing, flag management, and hardware control. Interviewers expect embedded candidates to be fluent with masks, shifts, and XOR tricks.

LeetCode Problems

#	Problem	Difficulty	Frequency
1	Number Complement	Easy	★★★★★
2	Is Power of Four	Easy	★★★★★
3	Range Bitwise AND	Medium	★★★★★
4	Bitwise XOR in a Subarray	Medium	★★★★★
5	Single Number II	Medium	★★★★★

Embedded Bit Manipulation Essentials

Operation	Technique	Code
Count set bits	Brian Kernighan's algorithm	`n &= (n-1)` in a loop — loops = set bit count
Power of 2 check	Single bit set detection	`(x != 0) && !(x & (x - 1))`
Swap without temp	XOR swap	`x ^= y; y ^= x; x ^= y`
Invert all bits	XOR with all-ones mask	`x ^ 0xFF` (for byte)
Set bit n	OR with shifted 1	`x \| (1 << n)`
Clear bit n	AND with inverted mask	`x & ~(1 << n)`
Toggle bit n	XOR with shifted 1	`x ^ (1 << n)`
Read bit n	AND and shift	`(x >> n) & 1`
Endianness swap (32-bit)	Byte reversal	`__builtin_bswap32(x)` or manual shift+mask
Detect endianness at runtime	Union or pointer cast	Check if first byte of `0x01` is `0x01` (little) or `0x00` (big)

Implementation

Number Complement Easy ★★★★★

Problem: Given a positive integer, return its complement by flipping all bits in its binary representation.

QSolution — O(log n) time, O(1) space — XOR Bit-by-Bit

Approach: Walk through each bit position of the number. XOR with 1 at each position to flip it. Stop when all significant bits have been processed (when the shifted copy reaches zero). This avoids flipping leading zeros.

cpp

class Solution {
public:
    int findComplement(int num) {
        int bit = 1, tp = num;
        while (tp) {
            num ^= bit;
            bit <<= 1;
            tp >>= 1;
        }
        return num;
    }
};

Embedded relevance: Bit complement operations are used constantly for creating inverted masks in register programming — e.g., clearing specific bits in a control register while preserving others.

Is Power of Four Easy ★★★★★

Problem: Given an integer, determine whether it is a power of four.

QSolution — O(1) time, O(1) space — Bit Trick

Approach: A number is a power of four if: (1) it's positive, (2) it has exactly one set bit (power of 2 check: n & (n-1) == 0), and (3) that bit is at an even position (bits 0, 2, 4, ...). The mask 0x55555555 has 1s at all even bit positions, so n & 0x55555555 != 0 confirms the set bit is in the right place.

cpp

class Solution {
public:
    bool isPowerOfFour(int num) {
        return num > 0 && ((num & (num - 1)) == 0) && (0x55555555 & num);
    }
};

Range Bitwise AND Medium ★★★★★

Problem: Given two integers left and right representing a range [left, right], return the bitwise AND of all numbers in this range.

QSolution — O(log n) time, O(1) space — Common Prefix

Approach: The AND of all numbers in [m, n] is the common leftmost bit prefix of m and n. Any bit position where m and n differ will have both 0 and 1 somewhere in the range, making the AND zero for that position. Use n = n & (n-1) to strip the rightmost set bit from n until n <= m. What remains is the common prefix.

cpp

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        while (m < n) {
            n = n & (n - 1);
        }
        return n;
    }
};

Bitwise XOR in a Subarray Medium ★★★★★

Problem: Given an array of integers and a list of queries [left, right], return the XOR of elements from index left to right for each query.

QSolution — O(n + q) time, O(1) extra space — Prefix XOR

Approach: Build a prefix XOR array where prefix[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]. The XOR of any subarray [i, j] is prefix[j] ^ prefix[i-1] because XOR is self-canceling: a ^ a = 0. This allows O(1) per query after O(n) preprocessing.

cpp

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        vector<int> res;

        for (int i = 1; i < arr.size(); i++) {
            arr[i] ^= arr[i - 1];
        }

        for (auto& v : queries) {
            if (v[0] == 0)
                res.push_back(arr[v[1]]);
            else
                res.push_back(arr[v[1]] ^ arr[v[0] - 1]);
        }

        return res;
    }
};

Embedded relevance: Prefix XOR is the technique behind CRC and checksum verification — computing the XOR of a data range to detect transmission errors in serial protocols.

Single Number II Medium ★★★★★

Problem: Given an integer array where every element appears three times except for one which appears exactly once, find the single element.

QSolution — O(n) time, O(1) space — Bit Counting

Approach: For each of the 32 bit positions, count how many numbers have that bit set. If the count modulo 3 is 1, the unique number has that bit set. This works because every other number contributes exactly 3 (or 0) to the count at each position, which vanishes modulo 3.

cpp

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < 32; ++i) {
            int sum = 0;
            for (int j = 0; j < nums.size(); ++j) {
                sum += (nums[j] >> i) & 1;
            }
            res |= (sum % 3) << i;
        }
        return res;
    }
};