Bit Manipulation — Questions, Answers & C Code
Examples
Author: ChatGPT (prepared for interview prep)
Contents 1. Basic Bit Concepts (1–10) 2. Bitwise Operators in C (11–18) 3. Bit Extraction and Modification
(19–28) 4. Bit Tricks and Optimization (29–38) 5. Interview-Level Logical Challenges (39–48) 6. Practical
Embedded Questions (49–58) 7. Coding Practice (59–66)
Introduction
This document contains 66 bit-manipulation interview questions with concise answers, explanations,
and C code examples where applicable. It's tailored for embedded systems, kernel, and device-driver
interviews. Use the code snippets as reference implementations — tweak as needed for edge cases or
different integer widths.
1. Basic Bit Concepts
1. What is a bit?
Answer: A bit is the smallest unit of data in computing, representing two states: 0 or 1.
2. How many bits are there in 1 byte?
Answer: 8 bits = 1 byte.
3. What are bitwise operators in C?
Answer: & (AND), | (OR), ^ (XOR), ~ (NOT), << (left shift), >> (right shift).
4. What’s the difference between logical and bitwise operators?
Answer: Logical operators ( && , || , ! ) operate on boolean truth values and short-circuit. Bitwise
operators work on each bit of integer operands with no short-circuit.
5. Explain bit shifting ( << and >> ).
Answer: x << n shifts bits of x left by n places (multiplying by 2^n for unsigned values). x >> n
shifts right by n (dividing by 2^n for unsigned, implementation-defined for signed).
1
6. What happens when you left shift by 1 bit?
Answer: Bits move one position left; least-significant bit becomes 0; value multiplies by 2 for unsigned
types.
7. What is the result of 1 << 3 ?
Answer: 8 (binary 00001000 ).
8. What is a bit mask?
Answer: A mask is a value used with bitwise ops to isolate, set, clear, or toggle specific bits (e.g.,
mask = 1 << n ).
9. What are LSB and MSB?
Answer: LSB — least significant bit (rightmost). MSB — most significant bit (leftmost).
10. What is endianness?
Answer: Byte order used to store multi-byte values: little-endian stores least-significant byte first; big-
endian stores most-significant byte first.
2. Bitwise Operators in C
11. Explain & , | , ^ , ~ , << , >> .
Answer: - a & b : bitwise AND — bit is 1 only if both bits are 1. - a | b : bitwise OR — bit is 1 if any
bit is 1. - a ^ b : XOR — bit is 1 if bits differ. - ~a : NOT — flips all bits. - a << n : left shift. - a >>
n : right shift.
Example: 5 & 3 = 0101 & 0011 = 0001 = 1.
12. What does XOR ( ^ ) do?
Answer: Yields 1 where bits are different, 0 where same. Useful for swapping and finding unique
elements.
Example (swap without temp):
2
x ^= y;
y ^= x;
x ^= y;
13. What’s the result of a & (~a) ?
Answer: 0 (a bitwise AND with its complement is zero).
14. How can you toggle a particular bit?
Answer: Use XOR with mask: x ^= (1 << n); toggles n-th bit.
15. What does a &= ~(1 << n) do?
Answer: Clears (sets to 0) the n-th bit of a .
16. Difference between x << 1 and x * 2 ?
Answer: For unsigned integers, they are typically equivalent if no overflow occurs. Shifts are sometimes
faster and explicit about bits; multiplication may trigger different optimizations for signed values.
17. What is the use of x ^= x ?
Answer: x ^= x sets x to 0.
18. How to check if two integers have opposite signs using bitwise operators?
Answer: ((a ^ b) < 0) for signed integers — highest bit differs set means opposite signs. In C:
if ((a ^ b) & (1 << (sizeof(int)*8 - 1))) .
3. Bit Extraction and Modification
19. How do you check if bit at position n is set?
Answer: (x & (1 << n)) != 0 .
Code:
3
int is_set(int x, int n) { return (x >> n) & 1; }
20. How to set a bit at position n?
Answer: x |= (1 << n);
21. How to clear a bit at position n?
Answer: x &= ~(1 << n);
22. How to toggle bit at position n?
Answer: x ^= (1 << n);
23. How do you count number of set bits in an integer?
Answer: Use Kernighan’s algorithm or builtin. Kernighan:
int count_bits(unsigned x) {
int c = 0;
while (x) { x &= (x - 1); c++; }
return c;
}
Or in GCC: __builtin_popcount(x) / __builtin_popcountll .
24. Write a function to reverse bits in an integer.
Answer (simple):
unsigned reverse_bits(unsigned x) {
unsigned r = 0;
for (int i = 0; i < sizeof(x)*8; i++) {
r = (r << 1) | (x & 1);
x >>= 1;
}
return r;
}
(There are faster table-based or divide-and-conquer methods.)
4
25. How to check if a number is a power of 2?
Answer: For positive x : (x & (x - 1)) == 0 and x != 0 .
26. How to swap two numbers without third variable?
Answer: Using XOR:
if (x != y) {
x ^= y;
y ^= x;
x ^= y;
}
(Guard against same variable case where x==y.)
27. How to find position of rightmost set bit?
Answer: pos = __builtin_ctz(x); (count trailing zeros) or pos = log2(x & -x) . If 1-based
index: pos+1 .
Manual:
int rightmost_pos(unsigned x) {
if (!x) return -1;
return __builtin_ctz(x);
}
28. How to clear rightmost set bit?
Answer: x &= (x - 1); clears lowest set bit.
4. Bit Tricks and Optimization
29. Why (x & (x - 1)) == 0 checks power of two?
Answer: Power of two has only one set bit; x-1 clears that bit and sets lower bits; ANDing yields 0
only for powers of two.
5
30. Purpose of (x & -x) ?
Answer: Isolates the least significant set bit (LSB). Example: x & -x gives value with only lowest set
bit.
31. Compute parity (odd/even count of 1s).
Answer: Use reduction with XOR:
int parity(unsigned x) {
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return x & 1;
}
Or __builtin_parity(x) in some compilers.
32. Multiply/divide by 2 using shifts?
Answer: Multiply: x << 1 ; Divide: x >> 1 (unsigned). For signed, watch rounding and sign
extension.
33. Check odd/even using bitwise.
Answer: if (x & 1) // odd else // even
34. Check positive/negative via bit manipulation.
Answer: For signed int x , sign bit: (x >> (sizeof(int)*8 - 1)) & 1 or simply x < 0 .
35. Implement bitwise rotation (left/right rotate).
Answer:
unsigned rol(unsigned x, int n) {
int bits = sizeof(x)*8;
n %= bits;
return (x << n) | (x >> (bits - n));
}
6
unsigned ror(unsigned x, int n) {
int bits = sizeof(x)*8;
n %= bits;
return (x >> n) | (x << (bits - n));
}
36. How to isolate least significant bit that is set?
Answer: lsb = x & -x; (same as question 30).
37. Explain bitfields in C and when to use them.
Answer: Bitfields allow packing multiple fields into a struct with specified bit widths: struct
{ unsigned a:3; unsigned b:5; } . Use for compact storage (hardware registers), but beware of
portability and packing/order differences.
38. How are flags/status registers implemented using bits?
Answer: Each bit represents a boolean flag. Use masks to set/clear/test bits. Example: STATUS |=
FLAG_ERROR; or if (STATUS & FLAG_READY) .
5. Interview-Level Logical Challenges
39. Reverse bits of unsigned integer.
Answer & code: See Q24 for simple approach; for 32-bit optimized approach, use divide-and-conquer
swapping with masks.
Optimized (32-bit):
unsigned reverse32(unsigned x) {
x = (x >> 1) & 0x55555555 | (x & 0x55555555) << 1;
x = (x >> 2) & 0x33333333 | (x & 0x33333333) << 2;
x = (x >> 4) & 0x0F0F0F0F | (x & 0x0F0F0F0F) << 4;
x = (x >> 8) & 0x00FF00FF | (x & 0x00FF00FF) << 8;
x = (x >> 16) | (x << 16);
return x;
}
40. Next higher number with same number of set bits.
Answer (Gosper's hack):
7
unsigned next_smallest_with_same_bits(unsigned x) {
unsigned u = x & -x;
unsigned v = u + x;
unsigned w = v + (((v ^ x) / u) >> 2);
return w;
}
Alternate clearer version:
unsigned snoob(unsigned x) {
unsigned smallest = x & -x;
unsigned ripple = x + smallest;
unsigned ones = x ^ ripple;
ones = (ones >> 2) / smallest;
return ripple | ones;
}
41. Count bits to convert a to b (Hamming distance).
Answer: Count set bits in a ^ b .
int bits_to_convert(int a, int b) { return __builtin_popcount(a ^ b); }
42. Find only non-repeating element where others appear twice (use XOR).
Answer: XOR all numbers; duplicates cancel leaving unique.
int find_unique(int *arr, int n) {
int res = 0;
for (int i = 0; i < n; ++i) res ^= arr[i];
return res;
}
43. Turn off k-th bit and return result.
Answer: result = x & ~(1 << k);
44. Do two integers differ by exactly one bit?
Answer: int diff = a ^ b; return diff && !(diff & (diff - 1)); (true if diff is a
power of two).
8
45. XOR of all numbers from 1 to n (pattern-based).
Answer: Pattern repeats every 4: - n % 4 == 0 → result n - n % 4 == 1 → result 1 -
n % 4 == 2 → result n + 1 - n % 4 == 3 → result 0
Function:
int xor_1_to_n(int n) {
switch (n & 3) {
case 0: return n;
case 1: return 1;
case 2: return n + 1;
default: return 0;
}
}
46. Reverse byte order of 32-bit (endianness swap).
Answer:
uint32_t swap32(uint32_t x) {
return (x >> 24) | ((x >> 8) & 0x0000FF00) | ((x << 8) & 0x00FF0000) |
(x << 24);
}
Or use builtin: __builtin_bswap32(x) .
47. Binary representation using recursion (no loops).
Answer:
void print_bin(unsigned x) {
if (x > 1) print_bin(x >> 1);
putchar((x & 1) ? '1' : '0');
}
48. Find two missing numbers in array using XOR.
Answer (outline): XOR all array elements with 1..n to get xor = a ^ b . Find a set bit in xor ,
partition numbers into two groups based on that bit, XOR each group to extract the two missing
numbers.
9
Code sketch:
void find_two_missing(int *arr, int n, int *x, int *y) {
int xor_all = 0;
for (int i = 0; i < n; ++i) xor_all ^= arr[i];
for (int i = 1; i <= n+2; ++i) xor_all ^= i;
int set_bit = xor_all & -xor_all;
int a = 0, b = 0;
for (int i = 0; i < n; ++i) {
if (arr[i] & set_bit) a ^= arr[i]; else b ^= arr[i];
}
for (int i = 1; i <= n+2; ++i) {
if (i & set_bit) a ^= i; else b ^= i;
}
*x = a; *y = b;
}
6. Practical Embedded Questions
49. How can bitwise operations help with control registers?
Answer: Control registers map flags to bits. Bitwise ops allow reading, setting, clearing, and toggling
hardware controls atomically or in read-modify-write cycles.
50. If hardware register uses bit 3 for enabling interrupts, how enable it?
Answer: reg |= (1 << 3); (assuming correct register width and volatile access).
51. Why are bitfields sometimes avoided in hardware register programming?
Answer: Bitfield layout, padding, and order (endianness-dependent) are implementation-defined — not
portable for hardware-mapped registers; better to use explicit masks and shifts.
52. How to set multiple bits together using a mask?
Answer: reg |= (MASK); where MASK has 1s at desired positions.
53. How to check multiple bits at once?
Answer: if ((reg & MASK) == MASK) /* all bits set */ or
if (reg & MASK) /* any bit set */ .
10
54. How to pack multiple flags into single byte?
Answer: Use bit positions: byte = (f0 << 0) | (f1 << 1) | ... and extract with masks.
55. Difference between |= and = when working with register bits?
Answer: |= sets bits while preserving others; = overwrites entire register value.
56. How do you read-modify-write a register safely (RMW)?
Answer: Read to a local variable, modify using masks, write back. In concurrent contexts, disable
interrupts or use atomic operations.
Example:
uint32_t v = REG;
v = (v & ~CLEAR_MASK) | (SET_MASK);
REG = v;
57. Use of volatile with bit manipulation?
Answer: Mark hardware-mapped variables volatile to prevent compiler from optimizing away
reads/writes.
58. Ensure atomic bit manipulation in multicore systems?
Answer: Use hardware atomic instructions (e.g., atomic set/clear), spinlocks, or bus-specific atomic
RMW primitives. For Linux kernel, use set_bit() / clear_bit() which are atomic.
7. Coding Practice (Common in Tests)
59. Print binary representation of a number.
Answer/Code:
void print_binary(unsigned x) {
for (int i = sizeof(x)*8 - 1; i >= 0; --i)
putchar((x & (1u << i)) ? '1' : '0');
}
11
60. Count trailing zeros.
Answer: Use __builtin_ctz(x) (undefined for x==0) or loop shifting.
Loop version:
int ctz(unsigned x) {
if (!x) return sizeof(x)*8;
int c = 0;
while ((x & 1) == 0) { c++; x >>= 1; }
return c;
}
61. Count leading zeros.
Answer: __builtin_clz(x) (undefined for x==0) or binary search method.
62. Return index of highest set bit.
Answer: int idx = 31 - __builtin_clz(x); for 32-bit. Return -1 if x==0.
63. Convert binary to decimal using bit operations only.
Answer: Parse bits and shift-add:
int binstr_to_int(const char *s) {
int r = 0;
while (*s) { r = (r << 1) + (*s++ - '0'); }
return r;
}
64. Compute n % 8 using bit manipulation.
Answer: n & 7 (since 8 is power of two).
65. Detect overflow in addition/subtraction using bits.
Answer: For signed addition a + b : overflow if ((a ^ sum) & (b ^ sum)) < 0 or check sign
bits: ((a ^ sum) & (b ^ sum)) & (1 << (bits-1)) .
Simpler (32-bit signed):
12
int add_overflow(int a, int b) {
int sum = a + b;
return ((a ^ sum) & (b ^ sum)) < 0;
}
66. Swap even and odd bits in an integer.
Answer: Mask and shift:
unsigned swap_even_odd(unsigned x) {
unsigned even = x & 0xAAAAAAAA; // bits 1,3,5... (if MSB is bit 31)
unsigned odd = x & 0x55555555; // bits 0,2,4...
return (even >> 1) | (odd << 1);
}
Final notes
• Many of these problems have multiple valid approaches — focus on correctness, complexity, and
edge cases (zero, negative, width).
• Use compiler builtins ( __builtin_* ) for performance and clarity when allowed.
• When working with hardware, prefer explicit masks and shifts over C bitfields for portability.
End of document.
13
