Bit Manipulation – Interview Questions and Practice Problems

A binary number is a number expressed in the binary numeral system or base-2 numeral system which represents numeric values using two different symbols: typically 0 (zero) and 1 (one). The base-2 system is a positional notation with a radix of 2. Because of its straightforward implementation in digital electronic circuitry using logic gates, the binary system is used internally by almost all modern computers and computer-based devices. Each digit is referred to as a bit.

 
Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a word. Computer programming tasks that require bit manipulation include low-level device control, error detection and correction algorithms, data compression, encryption algorithms, and optimization. For most other tasks, modern programming languages allow the programmer to work directly with abstractions instead of bits that represent those abstractions. Source code that does bit manipulation makes use of the bitwise operations: AND, OR, XOR, NOT, and bit shifts.

Bit manipulation, in some cases, can obviate or reduce the need to loop over a data structure and can give many-fold speed-ups, as bit manipulations are processed in parallel, but the code can become more difficult to write and maintain.

 
In this post, we will discuss a few such interesting bit manipulation hacks and interview questions:

1. Bit Hacks – Part 1 (Basic)Easy
2. Bit Hacks – Part 2 (Playing with k’th bit)Easy
3. Bit Hacks – Part 3 (Playing with the rightmost set bit of a number)Easy
4. Bit Hacks – Part 4 (Playing with letters of the English alphabet)Easy
5. Bit Hacks – Part 5 (Find the absolute value of an integer without branching)Easy
6. Find the total number of bits needed to be flippedEasy
7. Brian Kernighan’s Algorithm to count set bits in an integerEasy
8. Round up to the next highest power of 2Medium
9. Round up to the previous power of 2Medium
10. Compute the parity of a number using a lookup tableHard
11. Count set bits using a lookup tableHard
12. Multiply 16-bit integers using an 8-bit multiplierMedium
13. Swap individual bits at a given position in an integerHard
14. Check if a number is a power of 4 or notMedium
15. Check if a number is a power of 8 or notMedium
16. Reverse bits of an integerMedium
17. Swap two bits at a given position in an integerMedium
18. Print binary representation of a numberEasy
19. Add binary representation of two integersEasy
20. Swap adjacent bits of a numberMedium
21. Check if adjacent bits are set in the binary representation of a numberEasy
22. Reverse bits of an integer using a lookup tableHard
23. Circular shift on the binary representation of an integer by k positionsMedium
24. Find XOR of two numbers without using the XOR operatorMedium
25. Print all distinct subsets of a given setHard
26. Find the missing number in an arrayEasy
27. Find the missing number in an array without using any extra spaceEasy
28. Find the odd occurring element in an array in a single traversalEasy
29. Find two odd occurring elements in an array without using any extra spaceMedium
30. Find all odd occurring elements in an array having a limited range of elementsMedium
31. Find the duplicate element in a limited range arrayMedium
32. Find two duplicate elements in a limited range array (using XOR)Medium
33. Find the missing number and duplicate elements in an arrayMedium
34. Check if binary representation of a number is palindrome or notEasy
35. Efficiently implement power functionEasy
36. Find the odd occurring element in an array in logarithmic timeMedium
37. Huffman Coding Compression AlgorithmHard
38. XOR Linked List – Overview and Implementation in C/C++Medium
39. Generate the power set of a given setMedium
40. Swap two numbers without using a third variable | 5 methodsEasy
41. Find the square of a number without using the multiplication and division operatorEasy
42. Perform division of two numbers without using division operatorMedium
43. Generate 0 and 1 with 75% and 25% probabilityMedium
44. Determine if two integers are equal without using comparison and arithmetic operatorsEasy
45. Compute modulus division without division and modulo operatorEasy
46. Single line expressions to swap two integers in JavaEasy
47. Find minimum or maximum of two integers without using branchingHard
48. Conditionally negate a value without branchingMedium
49. Solve a given set of problems without using multiplication or division operatorsMedium
50. Generate binary numbers between 1 to n using a queueEasy