leetcode——位运算总结

2019-01-15

准备知识

  • 取反(NOT)：使数字1成为0，0成为1。取反操作符用波浪线”~“表示
  • 按位或(OR)：两个相应的二进位中只要有一个为1，该位的结果值为1。按位或操作符是”|”
  • 按位异或(XOR)：两个数如果某位不同则该位为1，否则该位为0。按位异或运算符是”^”
  • 按位与(AND)：两个相应的二进位都为1，该位的结果值才为1，否则为0。按位与用’&‘表示
  • 逻辑移位：应用逻辑移位时，移位后空缺的部分全部填0。符号有”>>“和”<<”

负数在计算机内部的存储方式是补码的形式。负数的补码就等于其正数反码+1。

136. 只出现一次的数字

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

0010 0100
^
0010 0100
=
0000 0000

由以上可得知，相同数字做^异或运算，会得到0。

137. 只出现一次的数字 II

只出现一次的数字 II

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

  1. 对每个整数以32位表示，分别统计每一位上1的个数，最后该位数上的和对3取余数；
  2. 如果余数不为0，则说明该位上只出现一次的元素，在该位上有1;
  3. 通过移位操作和1做位与运算，则可求得当前元素在该位是否有1。
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 参考https://shenjie1993.gitbooks.io/leetcode-python/137%20Single%20Number%20II.html
        res = 0
        # 将数值映射到32位的bit位上
        for i in range(32):
            sumone = 0
            tmp = 0
            for j in range(len(nums)):
                # 统计每个bit位上值为1出现的次数
                # x & 1 判断x的最后一位是否为1，为1则结果是1 不为1则结果是0
                # 每一轮统计要将数右移i位，去查看这个位上值是否为1
                sumone += (nums[j] >> i) & 1
            # sumone如果是3的倍数这说明这个位上出现了3次元素
            # 当余数不为0，则说明这个位上只出现了1次的数据在这个位置上有1
            # 然后将这个1左移i位就可以将只出现一次的那个数在这个位上取1
            # 按位或操作只要有一个为1，则结果为1
            tmp = sumone % 3
            # 处理负数的情况
            if i == 31 and tmp:
                res -= 1 << 31
            else:
                res |= tmp << i
        return res

if __name__ == '__main__':
    s = Solution()
    nums = [1, 1, 1, 2, 3, 3, 3]
    print(s.singleNumber(nums))
    
输出：
2

260. 只出现一次的数字 III

参见只出现一次的数字 III

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # 参考https://blog.csdn.net/smile_watermelon/article/details/47750249
        # 先对数组中的每个数字进行异或运算，以为有相同的数字，
        # 故异或运算后会抵消，剩下的就是两个只出现一次的数字异或运算的结果
        # 假设两个出现次数为1的数分别为a b
        # z = a ^ b
        z = 0
        for i in nums:
            z ^= i
        # 找到z中第一个位1的二进制位
        # 因为z中二进制位1的位置说明a,b中一个位0 一个位1
        index = 0
        while z & 1 == 0:
            z >>= 1
            index += 1

        a = 0
        b = 0
        for i in nums:
            # 然后比较这个数字的二进制位在index这个位上是否为1，将数字分开
            if (i >> index) & 1:
                a ^= i
            else:
                b ^= i
        return [a,b]

if __name__ == '__main__':
    s = Solution()
    nums = [1,2,1,3,2,5]
    print(s.singleNumber(nums))

输出：
[3,5]

参考文献

LeetCode——BitManipulation
位运算有什么奇技淫巧？
位运算简介及实用技巧（一）：基础篇
位运算简介及基本技巧