10 条题解
-
7
整活归整活,符合题意的代码还是要写的。
我们都知道
^
运算符是 不进位的加法 ,那么对于加法来说只需要 想个办法模拟进位 即可。对于两个二进制数
1010
和1100
来说,他们的相加即为0001 0110
。都知道
&
运算是全1
为真,那么对于二进制数来说,两个1
不就是进位吗?所以对于第四位上的进位,就可以视为
(1010&1100)<<1
。加法解决了,减法其实就是加上一个数的相反数,计算机里使用的是 补码 ,负数表示为其绝对值 取反再加一 ,如
-1
即为(~1)+1
,恰好可以使用加法解决。乘法本质上是一个数自己加自己数次,使用循环搞定。
……
草,好像不能用
i++
那回头来看二进制乘法
1010 * 1001 -------- 1010 0000 0000 1010 -------- 1011010
发现什么了?
由于二进制只有
1
和0
所以a*b
其实相当于把a
分别左移上b
中每个一所在的位数,最后相加。那你用过快速幂没有?
怎么判断一个二进制数每位有没有一,只需要想个办法把每位的一扔到最后一位(可以通过右移实现),然后再与一即可。
加法的代码:
ll add(ll a,ll b){ return b==0?a:add(a^b,(a&b)<<1); }
减法:
ll reduce(ll a,ll b){ return add(a,add(~b,1)); }
乘法:
ll times(ll a,ll b){ ll re=0; bool A=a<0,B=b<0; a=abs(a),b=abs(b); while(b){ if(b&1) re=add(re,a); a<<=1,b>>=1; } return A^B?add(~re,1):re; }
全代码:
#include<cstdio> #include<cmath> using namespace std; #define ll long long ll add(ll a,ll b){ return b==0?a:add(a^b,(a&b)<<1); } ll reduce(ll a,ll b){ return add(a,add(~b,1)); } ll times(ll a,ll b){ ll re=0; bool A=a<0,B=b<0; a=abs(a),b=abs(b); while(b){ if(b&1) re=add(re,a); a<<=1,b>>=1; } return A^B?add(~re,1):re; } ll a,b; int main() { scanf("%lld%lld",&a,&b); printf("%lld %lld %lld",add(a,b),reduce(a,b),times(a,b)); return 0; }
该用位运算还是要用的。
此处参拜白咕咕神教教主
信息
- ID
- 246
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- (无)
- 递交数
- 252
- 已通过
- 58
- 上传者