Bitwise Ops

2018-03-09

Basic Knowledge

Twos-complement binary: 补码二进制， 计算机以补码的形式存储数字。

1
2
3
4
5
6
正数: 原，反，补码 即其二进制表示，最高位符号位0
负数: [原]对应正数的符号位变1，[反]原码除了符号位都取反，[补]反码+1
+1: 0000 0001, 0000 0001, 0000 0001
-1: 1000 0001, 1111 1110, 1111 1111
已知负数补码求原码：补码-1，最高位不变，其余位取反。

Bitwise operators in python:

1
2
3
4
5
6
a << k # left shift k bits: 右端补0 (a * (2^k))
a >> k # right shift k bits: 左端补0 (a // (2^k))
a & b  # and
a | b  # or
~ a    # a的补码取反: -a - 1
a ^ b  # xor

XOR quality:

1
2
3
a ^ a = 0
a ^ b = b ^ a
a ^ b ^ c = a ^ (b ^ c)

Problems

XOR’s quality

  1. #156 Given an array of integers, every element appears twice except for one. Find that single one.

    1
    2
    3
    4
    5
    def singleNumber(nums):
        ret = 0
        for x in nums:
            ret ^= x
        return ret

  2. #168 Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

    1
    2
    3
    4
    5
    6
    def missingNumber(self, nums):
        ret, n = 0, len(nums)
        for i in range(n):
            ret = ret ^ i ^ nums[i]
        ret = ret ^ n
        return ret

  3. #389 Given two strings s and t which consist of only lowercase letters.
    String t is generated by random shuffling string s and then add one more letter at a random position.
    Find the letter that was added in t.

    1
    2
    3
    4
    5
    6
    def findTheDifference(self, s, t):
        ret, ls = 0, len(s)
        for i in range(ls):
            ret ^= ord(s[i]) ^ ord(t[i])
        ret ^= ord(t[ls])
        return chr(ret)

XOR and Truth Table

List the truth table first and then change it into boolean algebra.

  1. #137 Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

    1
    2
    3
    4
    5
    6
    7
    def singleNumber(self, nums):
        bit1, bit2 = 0, 0
        for x in nums:
            last_bit1 = bit1
            bit1 = (~bit1 & bit2 & x) | (bit1 & ~bit2 & ~x)
            bit2 = ~last_bit1 & (bit2 ^ x)    
        return bit2

  2. #variant Given an array of integers, every element appears once except for one, which appears exactly three times. Find that single one.

    1
    2
    3
    4
    5
    6
    7
    def single_number(nums):
        bit1, bit2 = 0, 0
        for x in nums:
            last_bit1 = bit1
            bit1 = ~bit2 & (last_bit1 ^ x)
            bit2 = (~bit1 & bit2 & ~x) | (bit1 & ~bit2 & x)
        return bit1

XOR and Divide Groups

  1. #260 Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    def singleNumber(self, nums):
        rst = 0
        for x in nums:
            rst ^= x
        mask = 1
        while not (mask & rst):
            mask <<= 1
        # divide into 2 groups by set bit
        rst1, rst2 = 0, 0
        for x in nums:
            if x & mask:
                rst1 ^= x
            else:
                rst2 ^= x
        return [rst1, rst2]