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

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