# Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:

`Input: 4, 14, 2 Output: 6 Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). So the answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6. `

Note:

1. Elements of the given array are in the range of `0 `to `10^9`
2. Length of the array will not exceed `10^4`.

# Using bit manipulation to achieve operators

1）计算负数的逆元

``````def negative(n):

2）加法计算

``````def bit_add(a, b):
b &= (2 ** 32 - 1)
while b:
tmp = a
sum = tmp ^ b
carry = (tmp & b) << 1
return a``````

3）减法计算

``````def bit_sub(a, b):

4）乘法计算

``````def bit_mul(a, b):
result = 0

while b:
if b & 0x1:
b >>= 1
a <<= 1

return result``````

5）除法计算

``````def bit_div(x, y):
result = 0
for i in range(32)[::-1]:
if (x >> i) >= y:
result += (1 << i)
x -= (y << i)

return result``````

I’m going to simulate the whole adding process by bit manipulation:

``````def add(a, b):
if not b:
return a

sum = a ^ b  # Just add without carry
carry = (a & b) << 1  # Just carry without add

and it works 🙂

## 我想试一试

### Status

Listensmileagree, and then do whatever the fuck you were gonna do anyway.

# Find medians from a slide window

`a = [1,2,3,12,-5,33]k = 3b = [2,3,3,12]b`

# Maximum XOR of Two Numbers in an Array

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ ij < n.

Could you do this in O(n) runtime?

Example:

`Input: [3, 10, 5, 25, 2, 8] Output: 28 Explanation: The maximum result is 5 ^ 25 = 28.`

result += any(result ^ 1 ^ p in prefixes for p in prefixes)

``````class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
result = 0

for i in range(32)[::-1]:
result <<= 1
prefixes = {num >> i for num in nums}
result += any(result ^ 1 ^ p in prefixes for p in prefixes)

return result

``````

# Flatten a Multilevel Doubly Linked List

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example:

`Input:  1---2---3---4---5---6--NULL                          |                          7---8---9---10--NULL                                  |                                  11--12--NULL Output: 1-2-3-7-8-11-12-9-10-4-5-6-NULL `
``````"""
# Definition for a Node.
class Node:
def __init__(self, val, prev, next, child):
self.val = val
self.prev = prev
self.next = next
self.child = child
"""

class Solution:
def flatten(self, head: 'Node') -> 'Node':
return None

stack = list()

while cur:
if cur.child:
if cur.next:
stack += [cur.next]
cur.next = cur.child
cur.next.prev = cur
cur.child = None

if not cur.next and stack:
temp = stack.pop()
cur.next = temp
temp.prev = cur

cur = cur.next

# Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

`    1       / \     2   5   / \   \ 3   4   6 `

The flattened tree should look like:

`1   \     2       \         3           \            4               \                 5         \                     6`
``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
node, stack = root, []

while node:
if node.right:
stack.append(node.right)
node.right = node.left
node.left = None

if not node.right and stack:
temp = stack.pop()
node.right = temp

node = node.right``````