0x01 位运算

0x01 位运算"0x01位运算"定义是度量信息的单位,包含$0$和$1$两个汇总状态,这种操作的速度很快!!!首先来定义一下算术位运算与:$and,\&$或:$or,|$非:$not,~$异或:$xor,ˆ$($ˆ$这个符号通常不实用)移位运算左移$$11=

大家好,欢迎来到IT知识分享网。0x01

0x01 位运算

定义

bit是度量信息的单位,包含\(0\)\(1\)两个汇总状态,这种操作的速度很快!!!
首先来定义一下算术位运算

与:\(and,\&\)
或:\(or,|\)
非:\(not,~\)
异或:\(xor,ˆ\)
(\(ˆ\)这个符号通常不实用)

移位运算

左移

\[1<<n = 2^n\,\,\,n<<1=2n \]

右移

算数右移

\[n>>1 = \left \lfloor \frac{n}{2.0} \right \rfloor \]

逻辑右移

略(基本上不会用到)

\(aˆb^{\,\,CH0101}\)

\[求a的b次方对p取模的值,其中1\leq a,b,p \leq10^9 \]

标准算法(跟位运算无关)

#include <iostream>
using namespace std;
int main()
{
	int a, b, p;
	cin >> a >> b >> p;
	unsigned long long ans = 1;
	for (int i = 0; i < b; i++)
	{
		ans *= a;
		ans %= p;
	}
	cout << ans << endl;
	return 0;
}

如果去评测:恭喜你

TLE

因为大数据肯定超时。
于是就需要快速幂!

long long power(int a,int b,int p){
	int ans = 1%p;
	for(;b;b>>=1)
	//for(;b;b/2.0)
	{
		if(b&1)ans = (long long)ans*a%p;
		a=(long long)a*a%p;
	}
	return ans;
}

问题又来了,如果遇到这道题

\(64\text{位整数乘法}^{CH0102}\)

\[求a的b次方对p取模的值,其中1\leq a,b,p \leq10^{20} \]

那就不香了,连\(long\,\,long\)都存不下了,那就尴尬了。

方法一

类似于快速幂,把\(b\)用二进制表示,得到结果。

\[b = c_{k-1}\cdot 2^{n-1} + c_{k-2}\cdot 2^{n-2} + \cdots + c_{0}\cdot 2^{0} \]

\[\text{于是}a\cdot b = c_{k-1}\cdot 2^{n-1} \cdot a + c_{k-1}\cdot 2^{n-1} \cdot a + \cdots +c_{0}\cdot 2^{0} \cdot a \]

\[\because a\cdot 2^i = (a\cdot 2^{i-1})\cdot 2 \text{在运算时每一项都不会超过}2 \cdot 10^{18} \]

\[\therefore \text{这种方法很香啊,而且时间复杂度是} O(log_2 b)!!! \]

#define ll long long 
ll mul(ll a, ll b, ll c){
    long long ans = 0;
    for(; b; b >>= 1){
        if (b & 1) ans = (ans + a) % p;
        a = a * 2 % p;
    }
    return ans;
}

方法二

利用$ a\cdot b,,mod,,p =,,a,,*,,b ,,-,,\lfloor \frac{a\cdot b}{p} \rfloor \cdot p$ 这个公式。
首先, \(a , b \le p\) 时,这个可以直接完成运算,英文我们不需要其他的精度位,而如果数据很大,只需要考虑比较低位的数据,那就很香了。

#define ll long long
ll mul(ll a, ll b, ll c){
    a %= p, b %= p;
    ll c = (long double) a * b / p;
    ll ans = a * b - c * p
    if (ans < 0) ans += p;
    else if (ans >= p) ans -= p;
    return ans;
}

今天就先到这里了,二进制状态压缩请看这里

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/31972.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信