C22.【C++ Cont】位运算总结(1)(例题五种解法!含汇编解法)
目录
1.撰写缘由
之前零零散散写过用位运算解题的文章,但没有系统总结过,本文的主要目标为总结相关算法
2.知识回顾
位运算符
<< //左移操作符
>> //右移操作符
& //按位与操作符
| //按位或操作符
^ //按位异或操作符
~ //按位取反操作
提醒:位运算操作符只适用于整数(含char类型)
左移和右移的特点
对于正整数和无符号整数数而言,左移一位相当于乘以2,右移一位相当于除以2
Dev C++采用算术右移
3.位运算的应用
1.判断奇偶性
事实:所有偶数的二进制表示中最低位一定是0(无论正负),由此可以推出:所有奇数的二进制表示中最低位一定是1(无论正负)
例如:
2:0000 0010 1:0000 0001
4:0000 0100 3:0000 0011
6:0000 0110 5:0000 0101
.......
因此判断为奇数还是偶数只需要判断最低位即可
AND运算的真值表:
| AND | 0 | 1 |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
则(x & 1) == 1, ,说明x是奇数;(x & 1) == 0, 说明x是偶数.(非最低位都变成0,最终的结果只和最低位有关)
判断奇偶性的本质为获取二进制数的第0位(最低位)
2.保留二进制位中的指定位
如8位的x,想保留x的第0,2,和4位(最低位为第0位),则让8位的m的指定位(第0,2,和4位)为1,即m==0001 0101b,使x&m,结果即为所求,结果其他位为0
3.获取二进制的指定位
如8位的x,想获取x的第4位,则先让x>>4,再对其&1(借鉴判断奇偶性)即可
结论:想获取x的第i位,结果为(x>>i) & 1
注:获取二进制的指定位要和保留二进制位(保留指定位,其余位置为0)中的指定位要区分开
4.按位或在某些情况下等价于加法运算
条件:没有相同位置的两个1时(即不产生进位),按位或运算的结果与加法运算的结果相同
*例题
颠倒给定的 32 位无符号整数的二进制位。
提示：
- 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
- 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数
-3，输出表示有符号整数-1073741825。示例 1：
输入：n = 00000010100101000001111010011100 输出：964176192 (00111001011110000010100101000000) 解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596， 因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。示例 2：
输入：n = 11111111111111111111111111111101 输出：3221225471 (10111111111111111111111111111111) 解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293， 因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。提示：
- 输入是一个长度为
32的二进制字符串进阶: 如果多次调用这个函数，你将如何优化你的算法？
解题限制:只能使用位运算解决
分析
方法1&方法2:获取n的每一个二进制位,之后依次乘以权重存到局部变量num中
方法3:当成字符串处理,之后调用reverse函数和bitset
代码
方法1
class Solution {
public:
uint32_t reverseBits(uint32_t n)
{
uint32_t num=0;
for (int i=0;i<32;i++)
{
num+=((n>>i)&1)*pow(2,31-i);
}
return num;
}
};提交结果
方法2
从方法1而来,pow(2,31-i)可以理解为多次左移位
class Solution {
public:
uint32_t reverseBits(uint32_t n)
{
uint32_t num=0;
for (int i=0;i<32;i++)
{
num+=((n>>i)&1)<<(31-i);
}
return num;
}
};提交结果
方法3
class Solution {
public:
uint32_t reverseBits(uint32_t n)
{
int bits = 0;
string s;
while (n / 2)
{
s = (char)(n % 2+'0') + s;
n /= 2;
bits++;
}
s = (char)(n % 2 + '0') + s;
bits++;
while (bits < 32)
{
s = "0" + s;
bits++;
}
reverse(s.begin(), s.end());
return (uint32_t)stol(s,NULL,2);
}
};
注意:不能写return (uint32_t)stoi(s,NULL,2); uint32_t范围与int范围不重合!!!,导致转换时超出范围的错误
提交结果
方法4:在方法2上稍加修改
class Solution {
public:
uint32_t reverseBits(uint32_t n)
{
uint32_t num=0;
for (int i=0;i<32;i++)
{
num|=((n>>i)&1)<<(31-i);
}
return num;
}
};
for循环体只需要一行就能解决问题
提交结果
方法5:shr+adc指令
由于LeetCode平台不支持嵌入汇编指令,因此在VS2022上测试
#include <iostream>
using namespace std;
uint32_t reverseBits(uint32_t n)
{
_asm
{
push eax
push ecx
push edx
xor edx, edx
mov eax, n
mov ecx, 32
_reverse:
shr eax, 1
adc edx, edx
dec ecx
jg _reverse
mov n, edx
}
return n;
}
int main()
{
cout << reverseBits(43261596);
return 0;
}注意:起到关键作用的是adc指令!(shl将左移丢弃的位存放在CF中,adc利用了CF位,adc num1,num2 : num1=num2+num1+CF)
测试结果
原文地址：https://blog.csdn.net/2401_85828611/article/details/145263345
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！