首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法:位运算

算法:位运算

作者头像
用户3578099
发布2022-04-18 16:18:38
9570
发布2022-04-18 16:18:38
举报
文章被收录于专栏:AI科技时讯AI科技时讯

位运算

知识点介绍

1.原码、反码和补码

二进制有三种不同的表示形式:原码、反码和补码计算机内部使用补码来表示

原码:就是其二进制表示(注意,有一位是符号位)

00 00 00 11  -> 3
10 00 00 11  -> -3

反码正数的反码就是原码,负数的反码是符号位不变,其余位取反(对应正数按位取反)

00 00 00 11 -> 3的反码
11 11 11 00 -> -3的反码

补码正数的补码就是原码,负数的补码是反码+1

00 00 00 11 -> 3的补码
11 11 11 01 -> -3的补码

符号位:最高位为符号位,0表示正数,1表示负数。在位运算中符号位也参与运算

总结

•正数的原码就是其二进制,反码也是原码,补码也是原码•负数的源码就是其二进制,只不过首位是1,符号位;反码是符号位不变,其它取反;补码是反码+1;•在计算机中,负数以正值的类补码操作形式表达(取反+1)

2.按位非操作~
~1 = 0
~0 = 1

~num的补码中的0和1全部取反(0变为1, 1变为0),有符号整数的符号位在~运算中同样会取反。

00 00 01 01 -> 5
对其取反 ~5 = -6
11 11 10 10 -> -6

11 11 10 11 -> -5
对其取反 ~(-5) = 4
00 00 01 00 -> 4
3.按位与操作&

对位进行与操作,1与1为1,其余为0

1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0

只有两个对应位都为1时才为1

 00 00 01 01 -> 5
&
 00 00 01 10 -> 6
---
 00 00 01 00 -> 4

可以看到5&6=4

4.按位或操作|

对位进行或操作,只要有一个为1,则结果为1

1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0

只要两个对应位有一个为1时就为1

 00 00 01 01 -> 5
&
 00 00 01 10 -> 6
---
 00 00 01 11 -> 7

可以看到5|6=7

5.按位异或操作^

对位进行异或操作,只有两个元素不一样的时候为1,其余为0

1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0

只有两个对应位不同时才为1

 00 00 01 01 -> 5
&
 00 00 01 10 -> 6
---
 00 00 00 11 -> 3

可以看到5^6=3

异或操作的性质:满足交换律和结合律

A: 00 00 11 00  -> 12
B: 00 00 01 11  -> 7

A^B: 00 00 10 11  -> 11
B^A: 00 00 10 11  -> 11

可以看到: A^B = B^A

另外有A^0=A , A^A=0

A: 00 00 11 00  -> 12
A: 00 00 11 00  -> 12
0: 00 00 00 00  -> 0

A^A: 00 00 00 00  -> 0
A^0: 00 00 11 00  -> 12

另外有A^B^A = A^A^B=B

A: 00 00 11 00  -> 12
B: 00 00 01 11  -> 7

A^B: 00 00 10 11 -> 11
A:   00 00 11 00 -> 12

A^B^A: 00 00 01 11 -> 7 == B

A: 00 00 11 00
A: 00 00 11 00

A^A: 00 00 00 00
B: 00 00 01 11
A^A^B: 00 00 01 11 -> 7 == B
6.按位左移操作<<

num << inum的二进制表示向左移动i位所得的值。

00 00 10 11 -> 11

11 << 3
---
01  01 10 00 -> 88

左移一位相当于所有位置向左移动一位,末尾补零。相当于每一位都乘以2,总数也是乘以2。

这种左移操作比乘法操作要快,可以在编程的时候适当运用该位运算。

7.按位右移操作>>

num >> inum的二进制表示向右移动i位所得的值。

00 00 10 11 -> 11

11 >> 2
---
00  00 00 10 -> 2

11/2 = 5

5/2 = 2

注意python中除法应该用///的结果是浮点型

右移一位相当于所有位置向右移动一位,首位补零。相当于每一位都除以2,总数也是除以2。

这种右移操作比除法操作要快,可以在编程的时候适当运用该位运算。

学习视频

•https://tianchi.aliyun.com/course/932/14644

位运算一般用于找唯一元素,常用的运算是异或,与等。具体问题可以慢慢找规律得到。

例题

114. 只出现一次的数字

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

说明:

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

示例 :

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

解题思路

思路一:使用哈希表的形式,元素作为key,次数作为value,但使用了额外空间

思路二:使用位运算的性质:X^X=0 X^0=X,如果一个列表中就只存在唯一的元素,其它元素都出现两次,那么将这些运算都进行异或操作,最后剩余的元素就是唯一元素。因为两个相同的元素异或结果为0,0与唯一元素异或就是唯一元素。

python实现

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        length = len(nums)
        if length == 1:
            return nums[0]

        ans = nums[0]
        for i in range(1, length):
            ans ^= nums[i]
        return ans

c++实现

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(auto e: nums)
        {
            res ^= e;
        }
        return res;
    }
};
181.只出现一次的数字III

给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

进阶:你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?

*

示例 *

输入:nums = [1,2,1,3,2,5]
输出:[3,5]
解释:[5, 3] 也是有效的答案。
输入:nums = [-1,0]
输出:[-1,0]
输入:nums = [0,1]
输出:[1,0]

解题思路:

这题与上一题有些变化,如果按照上一题的思路来看,最后异或得到的元素是只出现一次的两个元素异或的值。

比如以[1,2,1,3,2,5],每个元素都进行异或操作,得到的结构是3^5

00 00 00 11 -> 3
00 00 01 01 -> 5

3^5
---
00 00 01 10 -> 6

再看一下6的负数-6的二进制,

00 00 01 10
11 11 10 10 -> -6

6与-6进行与操作
6&-6
---
00 00 00 10 -> 2可以看到,只保留一位上有1

再观察1,2,3,5的二进制形式:
00 00 00 01  -> 1
00 00 00 10  -> 2
00 00 00 11  -> 3
00 00 01 01  -> 5

1与2进行与操作
00 00 00 00 

2与2进行与操作
00 00 00 10

3与2进行与操作
00 00 00 10

5与2进行与操作
00 00 00 00

可以看到1与5的结果是一样的,2与3的结果是一样的。

这些元素与6&-6得到的结果进行与操作,就能保留出那一个位置上有1的,基于此将列表分为两部分,每部分都只有一个唯一元素存在`[1, 1, 5]`与`[2, 2, 3]`,题目又转化为上一题的样式,最终将结果进行合并即可。

python实现

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        length = len(nums)
        if length == 2:
            return nums

        inner_num = 0
        for num in nums:
            inner_num ^= num
        inner_num &= (-inner_num)
        num1 = 0
        num2 = 0
        for num in nums:
            if num & inner_num:
                num1 ^= num
            else:
                num2 ^= num
        return [num1, num2]

c++实现

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int length = nums.size();
        if(length==2)
        {
            return nums;
        }

        int inner_num = 0;
        for(auto num: nums)
        {
            inner_num ^= num;
        }

        int lsb = (inner_num == INT_MIN ? inner_num: inner_num & (-inner_num));  // 防止溢出

        int num1 = 0;
        int num2 = 0;
        for(auto num: nums)
        {
            if(num & lsb)
            {
                num1 ^= num;
            }
            else
            {
                num2 ^= num;
            }
        }
        return {num1, num2};
    }
};
115. 只出现一次的数字II

给你一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

示例 :

输入:nums = [2,2,3,2]
输出:3
输入:nums = [0,1,0,1,0,1,99]
输出:99

解题思路:

•哈希表的方式,统计元素出现次数,再进行遍历一次找出出现一次的元素•位运算:考虑二进制的每一位,如果是三个数的,则相加为3或者0,多的那个数加起来的那位,整除3的余数就是出现一次的元素。由于数组中的元素都在 int(即32位整数)范围内,因此可以依次计算答案的每一个二进制位是1还是0 。具体地,考虑答案的第i个二进制位( i0 开始编号),它可能为1 或 0。对于数组中出现三次的元素,每一个元素都出现了3次,对应着第i个二进制位的 3个0 或3 个1 ,无论是哪一种情况,它们的和都是3的倍数(即和为3或0 )。因此:

答案的第 个二进制位就是数组中所有元素的第i个二进制位之和除以3的余数。

这样一来,对于数组中的每一个元素 ,我们使用位运算 得到 的第 个二进制位,并将它们相加再对 取余,得到的结果一定为 或 ,即为答案的第 个二进制位。

细节

需要注意的是,如果使用的语言对「有符号整数类型」和「无符号整数类型」没有区分,那么可能会得到错误的答案。这是因为「有符号整数类型」(即 类型)的第31个二进制位(即最高位)是补码意义下的符号位,对应着 符号位,而「无符号整数类型」由于没有符号,第31个二进制位对应着2^{31} 。因此在某些语言(例如python )中需要对最高位进行特殊判断。

python实现代码

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            total = sum((num>>i) &1 for num in nums)  # 右移的元素与1与,得到最末尾元素是0/1
            if total % 3:
                if i == 31:
                    ans -= (1<<i)  # 31位置为1,表明是符号位
                else:
                    ans |= (1<<i)  # 或等表明获得该位置的值
        return ans

c++实现代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(int i=0; i<32; i++)
        {
            int total = 0;
            for(int num: nums)
            {
                total += ((num >> i) & 1);
            }

            if(total % 3)
            {
                ans |= (1<<i);
            }
        }
        return ans;
    }
};
171. 2的幂

给你一个整数 n,请你判断该整数是否是 2 的幂次方。如果是,返回 true ;否则,返回 false

如果存在一个整数 x 使得n == 2^x ,则认为 n 是 2 的幂次方。

示例 :

输入:n = 1
输出:true
解释:20 = 1
输入:n = 16
输出:true
解释:24 = 16
输入:n = 3
输出:false
输入:n = 4
输出:true
输入:n = 5
输出:false

解题思路

方法1:使用while循环一直除以2,看能不能结果为是否为0(1排外)

方法2:一个数n是2的幂,当且仅当n是正整数,并且n的二进制表示中仅包含1个1

使用位运算,自身与真身-1后进行与运算。如果是2的幂的话,则表明二进制位有值的是1,减1之后的二进制位最低位的1变成0,其后跟的0变成1,再与本身进行与,则将最低位的1消掉;n&(n-1),判断最终的结构是否为0

除了1之外,其它2的幂指数的二进制表示就只有1个1。幂指数不可能为负

如果n是正整数并且n&(n-1)==0 ,那么n就是2的幂。

另外考虑如果n是正整数并且n&(-n)==n, 那么n也是2的幂

python实现

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n == 1:
            return True

        return n > 0 and (n & (n-1)) == 0  # 幂指数不可能为负

c++实现

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n==1)
        {
            return true;
        }
        return n > 0 && (n& (n-1)) == 0;
    }
};
66.子集

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 :

输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
输入:nums = [0]
输出:[[],[0]]

解题思路:

观察结果可以看到,列表中肯定有一个空子集,其它的都是罗列出来的元素,从0个,1个,一直到最终整个列表。可以通过递归的方法获得结果。

python实现

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        if nums is None or len(nums) < 1:
            return [[]]
        length = len(nums)

        res = []
        def helper(i, tmp):
            res.append(tmp)
            for j in range(i, length):  # 循环结束时候就是回溯开始之时
                helper(j+1, tmp+[nums[j]])
        helper(0, [])
        return res

c++实现

class Solution {
public:
    vector<int> t;
    vector<vector<int>> ans;

    void dfs(int cur, vector<int>& nums) {
        if (cur == nums.size()) {
            ans.push_back(t);
            return;
        }
        // 考虑选择当前位置
        t.push_back(nums[cur]);
        dfs(cur + 1, nums);
        t.pop_back();
        // 考虑不选择当前位置
        dfs(cur + 1, nums);
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(0, nums);
        return ans;
    }
};
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2022-03-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 AI科技时讯 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 位运算
  • 知识点介绍
    • 1.原码、反码和补码
      • 2.按位非操作~
        • 3.按位与操作&
          • 4.按位或操作|
            • 5.按位异或操作^
              • 6.按位左移操作<<
                • 7.按位右移操作>>
                • 学习视频
                • 例题
                  • 114. 只出现一次的数字
                    • 181.只出现一次的数字III
                      • 115. 只出现一次的数字II
                        • 171. 2的幂
                          • 66.子集
                          领券
                          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档