Leetcode

按位与、或、异或等二进制运算方法

与 & AND

运算规则

0 & 0 = 0

0 & 1 = 0

1 & 0 = 0

1 & 1 = 1

Example

Calculate 3 & 5:

3: 0011

5: 0101

3&5: 0001

负数

负数按补码参与按位与运算。

或 | OR

运算规则

0 | 0 = 0

0 | 1 = 1

1 | 0 = 0

1 | 1 = 1

Example

Calculate 3 | 5:

3: 0011

5: 0101

3|5: 0111

异或 ^ XOR

运算规则

0 ^ 0 = 0

0 ^ 1 = 1

1 ^ 0 = 0

1 ^ 1 = 0

Example

Calculate 3 ^ 5:

3: 0011

5: 0101

3^5: 0110

取反 ~ NOT

运算规则

~ 0 = 1

~ 1 = 0

左移 <<，右移 >>

运算规则

按二进制左/右移 N位

Example

1 << 3

1
2
	0001 << 3 
=	1000

10 >> 2

1
2
	1010 >> 2 
=	0010

EX: Leetcode371. Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    # 该用法适用于JAVA, C++，但Python负数使用有问题
    def getSum2(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: int
        """
        if b == 0:
            return a

        temp = a ^b
        carry = (a &b )<< 1

        return self.getSum(temp, carry)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 用mask解决负数问题
   def getSum(self, a, b):
       """
       :type a: int
       :type b: int
       :rtype: int
       """
       MAX = 0x7FFFFFFF
       MIN = 0x80000000
       mask = 0xFFFFFFFF

       while b !=0:
           a, b = (a^b) & mask, ((a&b)<<1) & mask

       return a if a <= MAX else ~(a ^ mask)