Leetcode: Single Number II @Python

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        bit = [0 for i in range(32)]
        for x in A:
            for i in range(32):
                if x & (1 << i) == 1 << i: bit[i] += 1
        res = 0
        for i in range(31): 
            if bit[i] % 3 == 1: 
                res += 1 << i  
        if bit[31] % 3 != 0: # negative
            res = -(2**31-res)
        return res 

I saw an interesting implementation with finite-state machine. More explaination can be find here.

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        ones = 0
        twos = 0
        for x in A:
            ones = (ones ^ x) & ~twos
            twos = (twos ^ x) & ~ones
        return ones