Lecture_Notes/imperfect_notes/pragy/Bit Manipulation.md

Bit Manipulation

Bitwise AND &

3 & 5 011 & 101 = 001 = 1

Bitwise OR |

3 | 5 011 | 101 = 111 = 7

XOR ^

Exclusive OR. Either this, or that That is, both bits are different. For more than 2 bits, True when number of on bits is odd

---

a & 0 = 0     a & 1 = a     a & a = a
a | 0 = a     a | 1 = 1     a | a = a
a ^ 0 = a     a ^ 1 = ~a    a ^ a = 0

For all these 3 operations, associativity is followed

so, a \odot b \odot c = (a \odot b) \odot c = a \odot (b \odot c)

---

Masking property of XOR

b = (a^b) ^ a = (a^b) ^ a = b ^ (a^a) = b^ 0 = b

---

Shifts

<< k - shift left by k. Insert 0 on right >> k - shift right by k.

<< k = multiply by 2^k >> k = integer divide by 2^k

show with example, say 22 = 10110

---

find first set bit

simply loop from i = 1 to 64. check if x & (1<<i) is non-zero

---

Pair with XOR

Given A[N], find any pair of elements whose XOR is k

Brute Force: Consider all pairs. O(n^2)

If a[i] ^ a[j] = k, then a[j] = k ^ a[i]

So, for each a[i]. I need to find if k^a[i] also exists in the array.

Use a hashmap - O(n)

Corner Case

if k = 0, we need to search for repeated elements. So, make sure that you handle it separately. If we don't handle separately, we might have to store a list of values for each number, which will be bad.

---

Single Out

Given A[N] in which each number appears twice, except for one number. Find this number

Naive: Hashmap. O(n) space

Optimized:

Masking property of xor - each repeated number will unmask itself.

So, simply xor the entire array. Space complexity: O(1)

a^a = 0, a^0 = a Order doesn't matter, so a ^ b ^ a ^ c ^ b

a's will cancel out, b's will cancel out. Left with c

---

Double Out

Given A[N] in which each number appears twice, except for two numbers. Find these numbers 1 2 2 1 3 8 6 3 Return 6, 8

Naive: Counter. O(n) space

Optimized:

• x = xor of entire array. You get xor of the tw oneeded elements
• find out any bit where the xor is set. We know that for this bit, our needed elements differ. So, partition by this bit
• Since all other numbers come in pairs, each partition will also have the numbers in pairs
• calculate the xor of individual partitions


O(1) space

---

Tripled

Given A[N]. All elements occur thrice, exceopt one which occurs once. Find the single one.

Naive: Counter. O(n) space

Optimized:

Since numbers occurs thrice, for each bit, the count of 1s for that bit must be a multiple of 3. If it is not, then the single number must have that bit set.

So, construct that single number


Complexity: O(n \log \max)

If max integer is 32 bits, then O(32n)

---

Given A[N], find the pair with minimum xor

Brute Force: All pairs. Keep min. O(n^2)

Optimized:

Given a[i], best possibility is to find another a[i] If not, then we can find a[i]-1 or a[i]+1

We basically want the numbers to be different as right as possible

Intuition: Sort the numbers. Lower the difference, lower the XOR.

Proof:

Consider A < B < C

suppose A, C differ in ith bit. Bits 0 to i-1 are same (from MSB)

Then, A must have a 0 there, while C must have a 1.

If B is b/w A, C, then B can have a 0 or a 1 there.


• 0:
  • A^B < A^C
  • A^B < B^C
  • (both conditions are important)
• 1:
  • B^C < A^B
  • B^C < A^C

In both cases, the min xor is b/w consecutive elements, and not b/w extremes.

Solution: Sort. Find xor of consecutive pairs. Return min. O(n log n)

---

Google Code Jam '19

Given master server with N slaves. user inputs binary string of length N send each bit to one server to read back, master asks slaves slaves are faulty, can go down, and don't return anything


input: 1010. slaves 2, 4 go down read: 11

input: 1111 slaves 2, 4 go down read: 11

Find out all faulty slaves by minimizing number of input queries

Brute Force: O(n). Check each slave one by one by setting just one bit each time

Optimized:

• we send several strings. Represented as matrix
• If ith slave is faulty, then ith column is dropped off.
• Say 2, 3 are faulty
• 
• simply encode each slave number in each column and send
• 
• whatever comes back are columnwise numbers of active slaves
• 

Instead of sending N strings, we send strings of length N We only need \log_2 N strings

So, for 10^9 slaves, I only need 32 queries!

---

Sum of Hamming Distances

Given A[N], find sum of Hamming distance b/w each pair of elements. x = 0110 y = 1001 d = 1111

Brute Force: All pairs O(n^2)

Optimized: For each bit: count with bit set = x count with bit not set = y contribution of bit = 2^bit * x * y

sum up

O(32 * n)

Remember the pattern? Instead of summing up all submatrix, we counted contribution of each cell. Reverse Lookup

---

following Kshitij's lecture