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 few such interesting bit manipulation hacks and interview questions –

 

  1. Bit Hacks – Part 1 (Basic)
     
  2. Bit Hacks – Part 2 (Playing with k’th bit)
     
  3. Bit Hacks – Part 3 (Playing with rightmost set bit of a number)
     
  4. Bit Hacks – Part 4 (Playing with letters of English alphabet)
     
  5. Bit Hacks – Part 5 (Find absolute value of an integer without branching)
     
  6. Bit Hacks – Part 6 (Random Problems)
     
  7. Brian Kernighan’s Algorithm to count set bits in an integer
     
  8. Compute parity of a number using lookup table
     
  9. Count set bits using lookup table
     
  10. Find the minimum or maximum of two integers without using branching
     
  11. Multiply 16-bit integers using 8-bit multiplier
     
  12. Round up to the next highest power of 2
     
  13. Round up to the previous power of 2
     
  14. Swap individual bits at given position in an integer
     
  15. Check if given number is power of 4 or not
     
  16. Reverse Bits of a given Integer
     
  17. Find odd occurring element in an array in single traversal
     
  18. Find two odd occurring element in an array without using any extra space
     
  19. Swap two bits at given position in an integer
     
  20. Add binary representation of two integers
     
  21. Swap Adjacent Bits of a Number
     
  22. Print all distinct Subsets of a given Set
     
  23. Perform Division of two numbers without using division operator (/)
     
  24. Check if adjacent bits are set in binary representation of a given number
     
  25. Conditionally negate a value without branching
     
  26. Find two duplicate elements in an limited range array (using XOR)
     
  27. Find missing number and duplicate elements in an array
     
  28. Check if given number is power of 8 or not
     
  29. Circular shift on binary representation of an integer by k positions
     
  30. Solve given set of problems without using multiplication or division operators
     
  31. Reverse Bits of an integer using lookup table
     
  32. Generate binary numbers between 1 to N
     
  33. Efficiently implement power function | Recursive and Iterative
     
  34. Find square of a number without using multiplication and division operator
     
  35. Generate power set of a given set
     
  36. Huffman Coding
     
  37. Find all odd occurring elements in an array having limited range of elements
     

 
 

Thank you for being with us. 🙂

 


Leave a Reply

avatar
  Subscribe  
Notify of