9 条题解

  • 6
    @ 2022-10-3 9:03:00

    整活归整活,符合题意的代码还是要写的。

    我们都知道 ^ 运算符是 不进位的加法 ,那么对于加法来说只需要 想个办法模拟进位 即可。

    对于两个二进制数 10101100 来说,他们的相加即为0001 0110

    都知道 & 运算是全 1 为真,那么对于二进制数来说,两个 1 不就是进位吗?

    所以对于第四位上的进位,就可以视为 (1010&1100)<<1

    加法解决了,减法其实就是加上一个数的相反数,计算机里使用的是 补码 ,负数表示为其绝对值 取反再加一 ,如 -1 即为 (~1)+1 ,恰好可以使用加法解决。

    乘法本质上是一个数自己加自己数次,使用循环搞定。

    ……

    草,好像不能用 i++

    那回头来看二进制乘法

    1010
    *   1001
    --------
        1010
       0000
      0000
     1010
    --------
     1011010
    

    发现什么了?

    由于二进制只有 10 所以 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
    标签
    (无)
    递交数
    209
    已通过
    45
    上传者