Bit Operations

If A,B are two bitmasking sets:

  • Set union: A|B

  • Set intersection: A&B

  • Set negation: ALL_BITS^A

  • Set off last element of the set: A = A&(A-1)

    Built-in function </br>

    Count Set bits of a number : __builtin_popcount(), __builtin_popcountll()

    Errichto’s Lecture
    1. Consider this problem: There are N≤5000 workers. Each worker is available during some days of this month (which has 30 days). For each worker, you are given a set of numbers, each from interval [1,30], representing his/her availability. You need to assign an important project to two workers but they will be able to work on the project only when they are both available. Find two workers that are best for the job — maximize the number of days when both these workers are available. </br></br> For two workers w1 and w2, intersection is mask[w1] & mask[w2]. Time Complexity = O(N^2) </br> What if the workers are working for D days. Then mask size will be D and int size = 2^D which only ll can hold. Beyond that you need to partition the bits. Partioning is ugly.</br>

    Nice solution : BITSETS

  • bitset<365> v;

  • v.count(): hamming weight

    https://en.cppreference.com/w/cpp/utility/bitset

    Sum-Xor property</br></br>

    #### Greedy Bitwise

    1. For problems related to maximising or minimization some bitwise SUM/PRODUCT, go bitwise from MSB TO LSB greedily.
    2. For prolems of difference between numbers, sometimes it is convenient to look the number in binary form, because after MSB of the number usually dictates the bigger the number and MSB of all numbers except one will be turned on. Ref: ArrayOps Codechef
    3. For problems where you need to go from MSB to LSB or vice versa, Example: a mod r. Represent a in base 2. In Base 2, a mod 2^i = mask after ith bit