Number System - C P P

Theory

• Convert
  • Convert Decimal to Binary
  • Convert Binary to Decimal
  • Convert Negative Decimal Number to Binary
• Bit Manipulation
  • ~var => 1's complement
  • builtin_clz(var) => Number of leading zeroes
  • builtin_ctz(var) => Number of trailing zeroes
  • __builtin_popcount(var) => Number of 1-bits
• Modulo Arithmetics - Commonly Used => 10⁹ + 7 - Exponentiation - n is odd => a _ (a^n/2 _ a^n/2) - n is even => (a^n/2 * a^n/2)
• Euclid Algorithm
  • gcd(a, b) = gcd(a - b, b)
  • lcm(a, b) * gcd(a, b) = a * b

Tricks

• N & 1 => Get First Bit
  • (N >> x) & 1 => Get bit value at xth position
  • True if Odd Number
• N & ~(N-1) => Get rightmost set bit
• N & (N-1) => Brian Kernighan’s algorithm
  • Subtracting 1 from a decimal number flips all the bits after the rightmost set bit
  • Used to check if number is power of 2
• N ^ N = 0
• 0 ^ N = n
• Swap 2 Numbers
  • a = a ^ b
  • b = a ^ b
  • a = a ^ b
• Get Reverse Number from given Digits
  • ans = (digit * 10ⁱ) + ans
• Get Number from given Digits
  • ans = (ans * 10) + digit