首页 > 其他 > 详细

位运算

时间:2020-05-28 22:09:02      阅读:46      评论:0      收藏:0      [点我收藏+]

位运算就是直接对整数在内存中的二进制位进行操作,往往简单的位操作就能快速实现复杂运算。

n & (n - 1) 操作是计算一个数的二进制中有多少位为1的常用操作,位运算中最常用的三个基本操作为与、或、非、异或。

熟练使用位操作(Bit Manipulation)可以玩出很多奇技淫巧。

?、?个有趣的位操作

1. 利?或操作 | 和空格将英?字符转换为?写
(a |  ) = a
(A |  ) = a

2. 利?与操作 & 和下划线将英?字符转换为?写

(b & _) = B 
(B & _) = B
3. 利?异或操作 ^ 和空格进?英?字符??写互换
(d ^  ) = D
(D ^  ) = d

4. 判断两个数是否异号

int x = -1, y = 2; 
bool f = ((x ^ y) < 0); // true 
int x = 3, y = 2; 
bool f = ((x ^ y) < 0); // false
可以利?乘积或者商来判断两个数是否异号,但是这种处理?式可能造成溢出,从?出现错误。

5. 交换两个数

int a = 1, b = 2; 
a ^= b; 
b ^= a; 
a ^= b; 
// 现在 a = 2, b = 1

6. 加一

int n = 1; 
n = -~n; // 
现在 n = 2

7. 减一

int n = 2; 
n = ~-n; 
// 现在 n = 1

?、算法常?操作 n&(n-1)

n(n-1)这个操作是算法中常?的,作?是消除数字 n 的?进制表?中的最后?个 1。

1. 返回 n 的?进制表?中有?个 1

int hammingWeight(uint32_t n)
 { 
    int res = 0; 
    while (n != 0) 
    { 
        n = n & (n - 1);
        res++; 
    }
        return res;
}        

 三、leetcode上的经典位运算题

1. 只出现一次的数字一

题目大意是除了一个数字出现一次,其他都出现了两次,让我们找到出现一次的数。

复杂度要求:

    时间复杂度:O(N),其中N为数组长度。

    空间复杂度:O(1)

我们执行一次全员异或即可。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        single_number = 0
        for num in nums:
            single_number ^= num
        return single_number

2. 只出现一次的数字二

题目大意是除了一个数字出现一次,其他都出现了三次,让我们找到出现一次的数。

复杂度要求:

    时间复杂度:O(N),其中N为数组长度。

    空间复杂度:O(1)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for i in range(32):
            cnt = 0  # 记录当前 bit 有多少个1
            bit = 1 << i  # 记录当前要操作的 bit
            for num in nums:
                if num & bit != 0:
                    cnt += 1
            if cnt % 3 != 0:
                # 不等于0说明唯一出现的数字在这个 bit 上是1
                res |= bit

        return res - 2 ** 32 if res > 2 ** 31 - 1 else res

3. 只出现一次的数字三

 题目大意是除了两个数字出现一次,其他都出现了两次,让我们找到这个两个数。

复杂度要求:

    时间复杂度:O(N),其中N为数组长度。

    空间复杂度:O(1)

解题思路:我们进行一次全员异或操作,得到的结果就是那两个只出现一次的不同的数字的异或结果。

我们刚才讲了异或的规律中有一个任何数和本身异或则为0, 因此我们的思路是能不能将这两个不同的数字分成两组 A 和 B。

分组需要满足两个条件.

1. 两个独特的的数字分成不同组

2. 相同的数字分成相同组

这样每一组的数据进行异或即可得到那两个数字。

问题的关键点是我们怎么进行分组呢?

由于异或的性质是,同一位相同则为 0,不同则为 1. 我们将所有数字异或的结果一定不是 0,也就是说至少有一位是 1.

我们随便取一个, 分组的依据就来了, 就是你取的那一位是 0 分成 1 组,那一位是 1 的分成一组。

这样肯定能保证2. 相同的数字分成相同组, 不同的数字会被分成不同组么。 很明显当然可以, 因此我们选择是 1,也就是

说两个独特的的数字在那一位一定是不同的,因此两个独特元素一定会被分成不同组。

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        ret = 0  # 所有数字异或的结果
        a = 0
        b = 0
        for n in nums:
            ret ^= n
        # 找到第一位不是0的
        h = 1
        while(ret & h == 0):
            h <<= 1
        for n in nums:
            # 根据该位是否为0将其分为两组
            if (h & n == 0):
                a ^= n
            else:
                b ^= n

        return [a, b]

 

 

位运算

原文:https://www.cnblogs.com/shnuxiaoan/p/12983786.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!