[位运算] XOR 异或 ^ NOT AND #3
Comments
运算总结XOR 异或运算 P=A⊕B& 与运算 (同时为1才为1, 否则为0)| 或运算 (有1就是1, 全0为0)~ 取反运算 (0变1 1变0)<< 左移运算符如果最右侧高位待舍弃位数不是1，则每次左移一位，相当与该数乘以2。 >> 右移运算符每次向右移动，相当于除以2。 |
2 - 137. 只出现一次的数字 II (除了某元素出现1次外其他均出现3次)
思路:
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ones, twos = 0, 0
for num in nums:
ones = ones ^ num & ~twos
twos = twos ^ num & ~ones
return ones最后返回0 # 独立想出来的 利用字典判断 + 两次相同异或区分值
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# 字典用来过滤 第一次 xor 第二次出现不操作 第三次出现操作
dictionary = {}
nums.sort()
result = 0
for i in nums:
if i in dictionary:
if dictionary[i] == 2:
result = result ^ i
dictionary[i] += 1
else:
dictionary[i] = 1
result = result ^ i
return result |
3 - 371. 两整数之和(异或 - 无进位结果, 与运算 - 进位位置说明 + 左移位)
例如: 3 + 4 = 7 无进位标识，返回异或结果即可 例如: 3 + 4 = 8 异或结果 + 进位结果 => 进位结果左移位 << 1 直到进位为0结束 // 第一版
var getSum = function(a, b) {
if (a === 0) return b
if (b === 0) return a
while (b !== 0) {
xor = a ^ b // 异或操作 不进位结果
carry = a & b // 与操作 说明在哪个位置上有进位
if (carry == 0) return xor
// 运算
carry = carry << 1
a = xor
b = carry
}
return a
};// 第二版
/**
* @param {number} a
* @param {number} b
* @return {number}
*/
var add = function(a, b) {
// 异或运算
xor = a ^ b
and = (a & b) << 1
if (and === 0){
return xor
}
return add(xor, and)
};在 Python 中，整数不是 32 位的，也就是说你一直循环左移并不会存在溢出的现象，这就需要我们手动对 Python 中的整数进行处理，手动模拟 32 位 INT 整型。 # 这个不完全对
class Solution:
def getSum(self, a: int, b: int) -> int:
if a == 0: return b
if b == 0: return a
while b !=0:
xor = a ^ b
carry = a & b
if carry == 0: return xor
carry = carry << 1
a = xor
b = carry
return a |
4 - 面试题15. 二进制中1的个数 与运算判断 + >> 1 右移位
class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
count = 0
while n != 0:
if n & 1 == 1: count +=1 # 与操作1 & 1 = 1, 0 & 1 = 0
n = n >> 1 # 右移一位
return count |
5 - 剑指 Offer 56 - I. 数组中数字出现的次数
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
if len(nums) == 2:
if nums[0] != nums[1]: return nums
nums.sort() # 排序
half = len(nums) // 2
left, right = nums[0: half], nums[half:]
left_val, right_val = 0, 0
for i in left: left_val = left_val ^ i
for i in right: right_val = right_val ^ i
# 值在right里面
if left_val == 0: return self.singleNumbers(right)
# 值在left里面
if right_val == 0: return self.singleNumbers(left)
# 值在左右两侧, 如果奇数个数 [1, 2, 2, 3, 3, 5] return [1, 5]
if len(left) % 2 == 1: return [left_val, right_val]
# 如果是 [1,2, 2, 4] 则需要这样处理
data = 0
for j in range(1, len(right)): data = data ^ right[j]
return [left_val ^ right[0], data] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 - 136. 只出现一次的数字 (除了某元素出现1次外其他均出现2次)
要求: 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
XOR 异或运算 P=A⊕B
The text was updated successfully, but these errors were encountered: