Lecture_Notes/imperfect_notes/pragy/Bit Manipulation.md
2020-03-19 12:51:33 +05:30

5.6 KiB

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

![3e86c025.png](:storage/e8857c4d-a2f9-4142-91cb-4eb909379fd2/3e86c025.png =400x)

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

![f51be358.png](:storage/e8857c4d-a2f9-4142-91cb-4eb909379fd2/f51be358.png =400x)

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

7ddd6b6e.png

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.

![4cded4eb.png](:storage/e8857c4d-a2f9-4142-91cb-4eb909379fd2/4cded4eb.png =300x)

  • 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

![56cbd86d.png](:storage/e8857c4d-a2f9-4142-91cb-4eb909379fd2/56cbd86d.png =300x)

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
  • ![47132572.png](:storage/e8857c4d-a2f9-4142-91cb-4eb909379fd2/47132572.png =300x)
  • simply encode each slave number in each column and send
  • ![5c782630.png](:storage/e8857c4d-a2f9-4142-91cb-4eb909379fd2/5c782630.png =200x)
  • whatever comes back are columnwise numbers of active slaves
  • ![9e762159.png](:storage/e8857c4d-a2f9-4142-91cb-4eb909379fd2/9e762159.png =400x)

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