算法 二进制练习

发表于 | 分类于
字数统计: 321字 | 阅读时长 ≈ 1分钟

位运算总结

常识

加法非进位

n=a^b

加法进位

c=a&b

加法

a+b=n+c=sum

n+c可以进一步递归，直到c为0时，返回n

基本操作

a=0^a = a^0

0=a ^ a

由上面两个推导出：a=a^ b ^b

没有加减乘除的加法

python写这道题有些复杂

image-20200730190241516

1
2
3
4
5
6
7
class Solution:
    def add(self, a: int, b: int) -> int:
        x=0xffffffff
        a,b=a&x,b&x #取32位以内的二进制
        while b!=0:
            a,b=(a^b),(a&b)<<1&x
        return a if a<=0x7fffffff else ~(a^x) #若补码 aa 为负数,需要还原将32位以上取反

更推荐用C / C++ / JAVA

1
2
3
4
5
6
class Solution {
public:
    int add(int a, int b) {
        return b == 0 ? a : add((a ^ b),(unsigned int)(a & b) << 1);
    }
};

只出现一次的数

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

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 :

1
2
输入: [2,2,1]
输出: 1

用的定律就好了

1
2
3
4
5
6
7
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result=0
        for num in nums:
            result^=num
        print(result)
        return result