Using bit manipulation to achieve operators

1)计算负数的逆元

def negative(n):
    return bit_add(~n, 1)

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):
    return bit_add(a, negative(b))

4)乘法计算

def bit_mul(a, b):
    result = 0

    while b:
        if b & 0x1:
            result = bit_add(result, a)
        b >>= 1
        a <<= 1

    return result

乘法模拟手工计算乘法的流程,将乘数b的二进制表示从左往右移动,当最低位为1时 (b & 0x1 == 1),把被乘数a加到result中,同时将被乘数a向左移动一位。

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

考虑32位整数表示 (64位改一下 i 就可以了)。从最大的倍数开始遍历,如果被除数x >> i 大于除数y,说明该位商为1,将1<<i加到结果中,并缩小x。

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.

这道题是在刷Explore的Trie tree topic里面看到的。首先一拿到题目,下意识的反应就是这道题没那么简单。最暴力的方法就是穷举遍历了,这样的话time complexity就会达到O(n^2)。

之后联想Trie tree和Binary之间的关系,可以画出上面这个图。这样问题就被转换为了找到最高的具有1节点的父节点,然后向下尽量找a^b = 1的分支 (我感觉我没有说清楚。。。)

之后看了讨论版里一位大佬的题解,真的是颇为震撼。他用了位运算的方法省去了很多不必要的步骤。 其中比较不好理解的是:

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

为了理解这句话,首先我们得知道:a^b^a=b.

在这里result^1 == a^b, p = a, 所以result^1^p = b。如果在prefixes中有任意两个数a,b可以得到result^1, 而且这两个数a,b构成了previous result,那么新的result就可以是result += 1了,不然只能是result <<= 1(末位为0)。

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

Piles of Boxes

Several days ago, I’ve joined a Hackathon that sponsored by Facebook.

As qualifying people to this event, they hand out an easy algorithm question. Shortly, you need to calculate how less time to move a bunch of boxes in same heigh.

Here is a solution for reference:


import collections

def box(boxesInPiles):
    sortBoxes = collections.OrderedDict(sorted(collections.Counter(boxesInPiles).items()))
    count = 0
    for index, key in enumerate(sortBoxes):
        count += index * sortBoxes[key]
    return count

print(box([4, 5, 5, 2, 4]))

Haskell moment

Here are some Haskell code chunks, which both are simple recursion algorithms.

Quicksort is a sort of poster child for Haskell because everyone does it to showcase how elegant Haskell is.

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
let smallerSorted = quicksort [a | a <- xs, a <= x]
    biggerSoted = quicksort [a | a <- xs, a > x]
in smallerSorted ++ [x] ++ biggerSoted
maximum' :: (Ord a) => [a] -> a
maximum' [] = error "List is empty!"
maximum' [x] = x
maximum' (x:xs) = (max x (maximum' xs))

replicate' :: Int  -> b -> [b]
replicate' n x
    | n <= 0 = []
    | otherwise = (x:(replicate' (n-1) x))

take' :: Int -> [a] -> [a]
take' n (x:xs)
    | n <= 0 = []
    | otherwise = x:(take' (n-1) xs)

reserve' :: [a] -> [a]
reserve' [] = []
reserve' (x:xs) = (reserve' xs) ++ [x]

Be a survivor of a disaster

这两天全靠红牛和咖啡续命了。

11月1号考完了这学期的第一门Final,在皇家展览馆考的。看了一下考场的座次表,三千人一起考试真的是美滋滋。考场的“服务人员”态度也特别好,看我手画Burndown Chart,就贴心的给我递过来了一把尺子 (可能是看我手画的太惨不忍睹了)。

因为这个暑假有四个月的时间,待在家里的话虽然可以轻松许多,但是还是觉得趁还可以实习,应该多锻炼一下自己。本来以为离放假还有一段时间,打算等考完试再去找实习,但是前两天算了一下日期,我发现再不找实习估计就来不及了,于是赶紧把简历投了起来。运气还不错的是,有好几个大佬都给了机会让我试一试。考完试的第二天,也就是11月2号,我约了微软的面试。正好打算考完试休息放松一天,于是2号就被我完全腾空用来面试了。

Continue reading