BitMagic

#逆转比特位

给定数字n，求颠倒每一位bit后产生的结果。

  1. 循环移位
    1
    unsigned int count = sizeof(int)*8
unsigned int reverse_num = 0
while num != 0:
    reverse_num |= (n & 1)<<count;
    n >>= 1;
    --count;
return reverse_num
  1. 二分
    两两之间、再求四四之间、递进求到16进行互相的交换
    1
    n = (((n & 0x55555555)<<1) | ((n>>1) & 0x55555555));
n = (((n & 0x33333333)<<2) | ((n>>2) & 0x33333333));
n = (((n & 0x0f0f0f0f)<<4) | ((n>>4) & 0x0f0f0f0f));
n = (((n & 0x00ff00ff)<<8) | ((n>>8) & 0x00ff00ff));
n = (((n & 0x0000ffff)<<16) | ((n>>16) & 0x0000ffff));
return n;

对于数字的移位操作，需要保证数字是无符号整数，否则可能是算数移位 或者 逻辑移位，依赖于具体的实现。

#整数二进制中1的数量

  1. n & (n-1) 去掉最低1

    1
    while n:
    c += 1
    n & = n-1

  2. n & (-n) 得到最低位1

    1
    while n:
    c += 1
    n -= n & (-n)

  3. 二分
    和Reverse Bit方法类似，先求两两之间、再求四四之间、递进求到16求1的数目

    1
    n = (n & (0x55555555)) + ((n >> 1) & 0x55555555)
n = (n & (0x33333333)) + ((n >> 2) & 0x33333333)
n = (n & (0x0f0f0f0f)) + ((n >> 4) & 0x0f0f0f0f)
n = (n & (0x00ff00ff)) + ((n >> 8) & 0x00ff00ff)
n = (n & (0x0000ffff)) + ((n >> 16) & 0x0000ffff)
return n

#Next Power of 2
通过n & (n-1) 获取最高位，再左移一位即可，注意检查是否为0:

1
next_pow = n & (n-1)
if next_pow == 0:
    return n
return next_pow << 1

#A * B 不能用乘法，除法

1
res = 0
isNeg = (a > 0 and b < 0) or (a < 0 and b > 0)
for i in range(63):
    if ((b >> i) & 1) > 0:
        tmp = res + (a << i) #考虑是否越界
        if tmp < res:
            return isNeg ? MIN_INT : MAXINT
        res = tmp
return res

#A / B 不能用乘法，除法

1
res = 0
isNeg = (a > 0 and b < 0) or (a < 0 and b > 0)
while a >= b:
    power = 1
    while ((b<<power) >= (b<<(power-1))) and (b<<power) <= a:
        power += 1
    res |= 1<<(power-1)
    a -= (b<<(power-1))
if isNeg:
    res *= -1

树的编码

#二叉树
根据二叉树的性质可以存在不同的编码方式

  1. 完全二叉树 (Complete Binary Tree)
    树除了最后一层，每一层的节点都是满的。按照层次遍历，输出各个节点即可。在解码时，检查层节点是否是满的。如果不是，说明是最后一层。

    顺道提一下，如何判断一颗树是完全二叉树呢？
    可利用每层节点都是满的性质，采用层次遍历，将每一节点的左右孩子都存在队列中。一旦出现为空的节点，其后的所有节点也一定都是空的.

    1
    queue = deque(root)
while queue and queue[0] not None:
    node = queue.popleft()
    queue.append(node.left)
    queue.append(node.right)
while queue and queue[-1] is None:
    queue.popleft()
return not queue

  2. 二叉搜索树
    由于二叉搜索树中序遍历的值是有序的。我们知道，对于任意二叉树，可使用中序和(前序&后续)任意一种，即可完成解码。
    从而在编码时，只需编码前序或者后续任意一种即可。
    解码时，通过preorder首元素进行二分，递归建立树，如果预先处理next数组，复杂度为O(n)
    代码可参考：

  3. 满二叉树(Full Tree)
    每个节点只有0或2个孩子。采用前序遍历，并用特殊符号标记是否存在孩子即可，和后续的普通二叉树方法类似。
  4. 普通二叉树
    可以采用任意一种遍历方式(前中后)，使用 # 标记空孩子，空格’ ‘隔开各个节点。解码时，需要注意 # 标记的空孩子。
    1
    # use preorder travase to visit the tree
# mark NULL node as #, space '_' to seperate each node
#        5
#    3      4
#  1   6       7
#
# 编码结果为: 5 3 1 # # 6 # # 4 # 7 # #
def encode(node):
    if not node:
        return '# '
    s = str(node.val) + ' '
    s += encode(node.left)
    return s+encode(node.right)

def decode(s, i):
    if i[0] == len(s):
        return None
    space_idx = s.find(' ', i[0])
    val = s[i[0]:space_idx]
    i[0] = space_idx+1
    if val == '#':
        return None
    root = TreeNode(val)
    root.left = decode(s, i)
    root.right = decode(s, i)
    return root

此种方式对于空节点较少的情形较好，对于空节点较多的场景，可以进行优化。
使用特殊字符 ! 标记节点存在孩子， 当不存在孩子时，什么也不用做。
如果只存在一个孩子，另外一个孩子仍然需要使用#标记。
参考之前给出的树的例子，编码长度大幅减少。

1
# use preorder travase to visit the tree
# mark NULL node as #, space '_' to seperate each node
# if node has childs, use !
#        5
#    3      4
#  1   6       7
#
# 编码结果为 5 ! 3 ! 1 6 4 ! # 7
def encode2(node):
    if not node:
        return '# '
    s = str(node.val) + ' '
    if node.left or node.right:
        s += '!'
        s += encode2(node.left)
        s += encode2(node.right)
    return s


def decode2(s, i):
    if i[0] == len(s):
        return None
    space_idx = s.find(' ', i[0])
    val = s[i[0]:space_idx]
    i[0] = space_idx+1
    if val == '#':
        return None
    root = TreeNode(val)
    if i[0] < len(s) and s[i[0]] == '!':
        i[0] += 1
        root.left = decode2(s, i)
        root.right = decode2(s, i)
    return root

#多叉树
编码方式和二叉树类似，可采用前序遍历，递归创建，使用#标记子节点结束。

1
def encode3(node):
    if not node:
        return ""
    s = str(node.val)+' '
    for child in node.children:
        s += encode3(child)
    s += '#'
    return s


def decode3(s, i):
    if i[0] == len(s):
        return None
    space_idx = s.find(' ', i[0])
    val = s[i[0]:space_idx]
    node = MultiTree(val)
    i[0] = space_idx+1
    while i[0] < len(s) and s[i[0]] != '#':
        node.children.append(decode3(s, i))
    i[0] += 1  # mark
    return node