BIT Manipulation

BITMASK - Two varieties of approach

BITSET   in   cpp
  1. NOTE - use bitset => binary representation (NOT decimal)
  2. Why do we need?
    • Let's say make boolean array of size 1e9 => High time complexity
    • But with bitset, it will automatically break 1e9 into multiple part of each 32 size (bcz 32-bit system) => time = 1e9/32
  3. Can use in case of take/ not take situation
  4. bitset<1000> num --> by default, num = 0
    • bitset<1000> num (x) --> set num = x => x can be number or binary string
    • num.to_string() => converts to string
    • num.to_ullong() => converts to unsigned long long;
    • can access ith bit as num[i]
  5. Operations
    		• sets all bits to 1           --> num.set()
      		sets all bits to 0
      		toggles the values of bits              -> num.flip() - flip all
                                                  -> num.flip(2) - flip 2nd index
      		returns the number of bits = 1 --> can't use __builtin_popcount(x)

These can be done in O(1) like &, |, ^ --> NOT O(logn)
__builtin_popcountll(x) --> counts the number of 1 in x
__builtin_ctz(x) --> counts the number of trailing zeros in x

  • n & (n+1) clears all trailing ones:  make all trailing 1 before 1st '0' as 0
    • 00110111 -> 00110000 => makes all 1 before 1st '0' as 0
    • 0011 01112→0011 00002\
  • n | (n+1) sets the last cleared bit:  make 1st 0 as 1 and no change to others
    • 00110111 -> 00111111

  • m & (m-1) unset the last set bit
     --> Eg.- m=26 as 11010     changes into 11000

  • if n is in form of 2^m  => (n-1) & n = 0
  • if odd => n&1 = 1

  • To check bit at index = i --> 1 & (num>>i ) --> gives only 0 or 1
    • AVOID (1<<i) & num --> bcz this results in 0 or 2^i

  • To set bit at index = i --> num | (1<<i )
  • To toggle bit at index = i --> num ^ (1<<i )
  • ~num => 1's complement --> invert all bits
    • ~num + 1 --> 2's complement => same as -num
    • bcz in cpp all -ve are stored as 2's complement
  • a+b = (a^b) + 2*(a&b)
    • Just like full adder in digital system => sum = a xor b 
    • Carry = a&b --> BUT why 2*(a&b)
      • bcz a&b just tells the places where we have carry
      • let's say 1+1 (in bit form) --> gives 10 (i.e. 2 in decimal form) 
        • This 2 is the actual value => val*places or 2*(a&b)
    • NOTE: - (a+b) and (a^b) have same parity

  • To compute xor from 1 to n // If n is a multiple of 4   if (n % 4 == 0)     return n;  // If n%4 gives remainder 1   if (n % 4 == 1)     return 1;  // If n%4 gives remainder 2   if (n % 4 == 2)     return n + 1;   // If n%4 gives remainder 3   return 0;

    • Repeats in cycle as previous value used to generate next value --> 4n bcz it's last 2 characters are 0 => no effect on addding 1, 2 or 3

Comments

Post a Comment

Popular posts from this blog

Templates (for CP)

Next smaller element in left and right side of any element -  Link     (Can easily modify) Next greater element for both sides in one pass -  Link String Hashing -  Link MUST call precalc() inside function Count inversions in any random array (GENERAL)  -  Link Count inversions in binary string -  Link Sum of XOR of all subarrays -  Link  ——₪——  Original question link Sum of XOR of all subsequence -   Link  ——₪——  Original question link Prefix sum of 2-D array -  Link Number of subarrays with sum = k →  Link Number of subarrays with sum divisible by k  →  Link Segment Trees →  Link djikstera algorithm -  Link Prime Factorization of given number n →  Link Count no. of divisors in  O(N ⅓ )  →  Link
Read more

DSA Trees + Heap

Image
Trees are special form of graph If n nodes => n-1 edges (means 2 points have only 1 line joining them) They are acyclic => means from node A to node B there is only 1 way to reach Whenever see  stuffs like  connected ,  unique path  -> tree Types of traversal in trees inorder traversion - left -> root -> right preorder traversion - root -> left  -> right postorder traversion - left  -> right -> root If first time visited -> must be root (bcz parent hai)  => PRE-ORDER If second time visited -> left subtree fully analyzed bcz we are moving in anti-clockwise direction => toh left check krke hi aayenge  => IN-ORDER If third time visited -> left and right subtree fully analyzed => POST-ORDER Post-order is reverse of Pre-order from clockwise Binary search tree (BST) = Binary tree + Search property each subtree follows -- left subtree < root value < right subtree Inorder traversal in BST is...
Read more

Modular Basics + Number Theory + Permutations

Image
Binary Exponentiation - to find   a b  →  converted b into binary  Benefit - instead of multiplying b times => multiply   lo g 2 ( b ) times If a is large  →  take  (a % M) If M is itself very large (like 1e18) =>  instead of a*a  →  DO a+a+a....(a times) even if a*a = 1e18  →  will not get reduced log²(n) bcz log(n) for binary_Multiply & log(n) f or expo Same code as expo => Only change * to + everywhere If b is large in a b  →  a b c  ≠  a ( b c  %  M )  ( mod M )  →   cannot take mod in power Use Euler Theorem  →  a b c ≡ a ( b c  % ɸ(m) )  (mod M )  → ɸ is euler totient function For safety, add extra ɸ in power bcz above fails if gcd(a, m) ≠  1 a b c ≡ a (ɸ(m) + ( b c  % ɸ(m) )) ( mod M )   →  updated GCD + prime  properties a divides b + b divides a ---> a =  ±  b gcd is alwa...
Read more