DSA interview question

Bit Manipulation Prerequisites for Trie Problems — Theory

Easy · Data structures · Topics: trie, bit manipulation, theory

The problem

Before your team lets you touch any Trie-based bit manipulation problems (Max XOR, Max XOR with constraints, etc.), your tech lead wants to confirm you're fluent in the bitwise building blocks these problems rely on. This is a theory/fundamentals check — not a single coded problem, but a set of core operations and concepts you need cold: extracting bits, setting/clearing bits, counting bits, understanding two's complement, and how XOR's properties make it ideal for Trie-based "maximize/minimize" problems.

Function signature

(Theory-style — here are the standard utility functions interviewers expect you to write fluently and explain.)

int getBit(int num, int i);             // get value of i-th bit (0 or 1)
int setBit(int num, int i);             // set i-th bit to 1
int clearBit(int num, int i);           // set i-th bit to 0
int toggleBit(int num, int i);          // flip i-th bit
int countSetBits(int num);              // count total 1-bits (popcount)
bool isPowerOfTwo(int num);             // check if num is a power of 2
int highestSetBitPosition(int num);     // index of the most significant 1-bit

Test cases

Operation	Input	Output	Explanation
`getBit(num=10, i=1)`	`10 = 1010`	`1`	Bit at position 1 (0-indexed from LSB) is 1
`setBit(num=10, i=0)`	`10 = 1010`	`11`	`1010 -> 1011`
`clearBit(num=10, i=1)`	`10 = 1010`	`8`	`1010 -> 1000`
`toggleBit(num=10, i=0)`	`10 = 1010`	`11`	`1010 -> 1011` (bit 0 was 0, becomes 1)
`countSetBits(num=7)`	`7 = 0111`	`3`	Three 1-bits
`isPowerOfTwo(num=16)`	`16 = 10000`	`true`	Exactly one set bit
`isPowerOfTwo(num=18)`	`18 = 10010`	`false`	Two set bits
`highestSetBitPosition(num=13)`	`13 = 1101`	`3`	Most significant 1 is at index 3 (0-indexed from LSB)

How interviewers phrase it

"Before we dive into the Trie problem, can you walk me through how you'd extract/set/clear a specific bit in an integer?"
"What's the most efficient way to count set bits in a number?"
"Why does XOR work so well for 'maximize the difference' type problems?"
This is rarely asked as a standalone interview question — it's almost always a precursor check before a real Trie/bit-manipulation problem, or comes up naturally when the interviewer asks "can you explain that bit operation you just wrote?"

Clarifying questions to ask

Are we working with signed or unsigned integers? (Matters for right-shift behavior on negative numbers — arithmetic vs logical shift — and for how many bits to consider, e.g., 31 vs 32.)
What's the expected bit-width / value range? (Determines loop bounds in Trie-building code, e.g., BITS = 31 for values up to 2^31-1.)
Should bit positions be 0-indexed from the LSB (least significant bit) or MSB? (Standard convention: 0-indexed from LSB — confirm to avoid off-by-one bugs later.)

Follow-ups to expect

"Why does n & (n-1) clear the lowest set bit? Walk through why."
"How does Brian Kernighan's algorithm count set bits faster than checking all 32 bits individually?"
"Why is n & (n-1) == 0 a valid power-of-two check?"
"Explain why XOR is 'self-inverse' and why that matters for problems like 'find the single non-duplicate number.'"
"Why does maximizing XOR favor making higher bits differ first? Connect this to why Tries process bits from MSB to LSB."
"How would you handle negative numbers in two's complement when doing these bit operations?"
"Why do Trie-based XOR problems typically fix the bit-width (like 31) rather than looping until the number becomes 0?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview