文章目录
- 算法技巧——位运算
-
- 一、基础知识
- 二、位运算
-
- 1、按位非
- 2、按位与
- 3、按位或
- 4、按位异或
- 5、 **异或操作的性质**：
- 6、左移(<<)
- 7、右移(>>)
- 三、巧妙使用位运算解决算法题
-
- 1、只出现一次的数字
算法技巧——位运算 一、基础知识 二进制三种不同表现形式。
原码：最高位符号位，正数为0，负数为1。
反码：正数等于原码；负数，原码除了符号位，其他位取反。
补码：计算机内部使用补码表示。反码+1。
二、位运算 位运算中符号位也进行运算。
1、按位非
~1=0
~0=1
例：
1011-> -3
~(按位非)0100(补码) -> 0100(原码)->40100->4
~1011(补码)->1101(原码)-> -5
2、按位与
1 & 0 =0只有都是1最终才为1
0 & 0 =0
1 & 1 =1
0100(4) & 1101(-3) = 0100 (4)
3、按位或
1 | 0 =1只有都是0最终才为0
0 | 0= 0
1 | 1 =1
0100(4) | 1101(-3) =1101 (-3)
4、按位异或
1 ^ 0 =1当两数不同时为1
0 ^ 0 =0
1 ^ 1 = 0
0100(4) ^ 1101(-3) =1001 (-7)
5、 异或操作的性质：
满足交换律和结合律
例：A=0110 B=1011性质：
A^ B ^ A=1101 ^ 0110 =1011
A^ A ^ B = 0000 ^ 1011 =1011
A ^ A = 06、左移(<<)
0 ^ A = A
低位补0
00001110(14)左移一位相当于*2
00001110 << 3 = 01110000 (112)
14*2*2*2=112
7、右移(>>)
高位补0
01110000(112)右移一位相等于/2
01110000 >> 3 = 00001110(14)
112/2/2/2=14
三、巧妙使用位运算解决算法题 1、只出现一次的数字
https://leetcode-cn.com/problems/single-number/
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。使用 性质 异或满足结合律和交换律
例：[1,2,3,1,3] -> 2
【每日一道算法题|算法技巧——位运算】0 ^ 1 ^ 2 ^ 3 ^ 1 ^ 3 = 0 ^ 1 ^ 1 ^ 3 ^ 3 ^ 2 = 2
class Solution {
public:
int singleNumber(vector& nums) {
if(nums.empty()) return 0;
int result = 0;
for(int i=0;
i 推荐阅读
- 每日一道算法题|Leetcode 213.打家劫舍 II &剑指Offer II 090. 环形房屋偷盗
- Algorithm|ZOJ--003Crashing Balloon
- Algorithm|ZOJ练习--001A + B Problem
- Algorithm|ZOJ练习--002Fire Net
- MATLAB神经网络|SOM网络算法分析与应用（适合入门、快速上手）
- 算法|高性能计算专家Jack Dongarra获2021年图灵奖
- 数据结构|《数据结构》十道链表经典面试题多种方法深度解析
- 和事故斗智斗勇的这些天|关于 error: invalid types ‘int[int]‘ for array subscript 的解决
- Linux|Linux命令pwd的自我实现