AlgoViz
HomeBit Manipulation

Bit Manipulation

AND, OR, XOR and shifts — the classic constant-space tricks.

0/ 24 understood · 0%
Walkthroughs
8
Problems
24
Start here
24 shown
  1. OverviewAND · OR · XOR · shifts · the classic tricksEasy
  2. Single NumberXOR fold · pairs cancelEasy
  3. Number of 1 BitsHamming weight · n & (n − 1)Easy
  4. Missing NumberXOR index ⊕ value · pairs cancelEasy
  5. Practice problems
  6. Introduction to Bits and TricksAND, OR, XOR and the shiftsEasy
  7. Check if the i-th bit is Set or NotShift the bit down, or the mask upEasy
  8. Check if a Number is Odd or NotThe lowest bit is the parityEasy
  9. Check if a Number is Power of 2 or NotExactly one bit setEasy
  10. Count the Number of Set BitsBrian Kernighan: clear the lowest set bitEasy
  11. Set/Unset the rightmost unset bitOR with n+1Easy
  12. Swap Two NumbersThree XORs, no temporaryEasy
  13. Divide two numbers without multiplication and divisionSubtract the largest shifted divisorMedium
  14. Minimum Bit Flips to Convert NumberCount the set bits of the XORMedium
  15. Single Number - IXOR everything; the pairs vanishMedium
  16. Power Set Bit ManipulationEach number 0..2^n-1 is a subsetMedium
  17. XOR of numbers in a given rangePrefix XOR has a four-case patternMedium
  18. Single Number - IIISplit the array on one differing bitMedium
  19. Print Prime Factors of a NumberDivide out each factor as you find itHard
  20. Divisors of a NumberPair them up around the square rootEasy
  21. Count primes in range L to RSieve of Eratosthenes, then countHard
  22. Prime factorisation of a NumberSmallest-prime-factor sieveHard
  23. Pow(x,n)Square and multiply, driven by the bitsEasy
  24. Reverse BitsShift out one side, shift in the otherMedium
  25. Sum of Two IntegersXOR adds, AND finds the carriesMedium