$$一.二进制的基本概念$$

1.原码、反码、补码

(1).原码:一个数的二进制原码就是该数怎么样用2^n表示，并且第一位表示符号,0为正，1为负。

如:八位字机器下[+127]原 = 0111 1111，[-64]原 = 1011 1111

(2).反码:正数的反码就是其原码;负数的反码是在其原码的基础上符号位不变，其余取反

如:八位字机器下[+127]反 = 0111 1111, [-64]反 = 1100 0000

(3).补码:正数的补码仍为其原码;负数的反码是在其反码的基础上+1

如:八位字机器下[+127]补 = 0111 1111，[-64]补 = 1100 0001

总之：正数的原码、反码、补码都一样，负数的反码是原码基础上符号位不变，其余取反，负数的补码是在反码上+1

$$二.各种类型大小以及常用二进制操作$$

1. 每一个类型的大小，上下界

//测试代码
#include <iostream>
#include <climits>
using namespace std;
int main(){
    int  n_int = INT_MAX;
    short n_short = SHRT_MAX;
    long n_long = LONG_MAX;
    long long n_llong = LLONG_MAX;
    // 类型长度
    cout << " sizeof operator yields size of type or of variable. " << endl;
    cout << " int is " << sizeof(int) << " bytes. " << endl;
    cout << " short is " << sizeof n_short << " bytes." << endl;
    cout << " long is " << sizeof n_long << " bytes." << endl;
    cout << " n_llong is " << sizeof n_llong << " bytes." << endl;
    cout << endl;
    // 类型最大值
    cout << "Maximum values: " << endl;
    cout << "int Maximum values: " << n_int << endl;
    cout << "short Maximum values: " << n_short << endl;
    cout << "long Maximum values: " << n_long << endl;
    cout << "long long Maximum values: " << n_llong << endl;
    cout << endl;
    // 最小值
    cout << "Minimum values: " << endl;
    cout << "int Minimum values: " << INT_MIN << endl;
    cout << "short Minimum values: " << SHRT_MIN << endl;
    cout << "long Minimum values: " << LONG_MIN << endl;
    cout << "long long Minimum values: " << LLONG_MIN << endl;

    cout << endl;cin.get();cin.get();
    return 0;
}

输出
 sizeof operator yields size of type or of variable. 
 int is 4 bytes. 
 short is 2 bytes.
 long is 8 bytes.
 n_llong is 8 bytes.

Maximum values: 
int Maximum values: 2147483647
short Maximum values: 32767
long Maximum values: 9223372036854775807
long long Maximum values: 9223372036854775807

Minimum values: 
int Minimum values: -2147483648
short Minimum values: -32768
long Minimum values: -9223372036854775808
long long Minimum values: -9223372036854775808

注：转自此

2.常用二进制运算

• &:同为真才为真,即 同 1 得 1
• |:有一个为真就为真,即 有 1 为 1
• ~:代表取反, 即 1 变 0， 0 变 1
• ^:两个不同时才为1, 即 相同个数的 1 和 0 结果为 1

二进制有个很特殊的特点: 二进制下不进位, 即对某一位进行二进制运算，对其他位置无影响,例题

3. 常用运算:

(n >> k) & 1;      // 取出 n 在二进制下第 k 位
n & ((1 << k) -1); // 取出 n 在二进制下第 0 ~ k - 1 位 
n ^ (1 << k);      // 将 n 在二进制下第 k 位取反
n | (1 << k);      // 将 n 在二进制下第 k 位赋值 1
n & (~(1 << k));   // 将 n 在二进制下第 k 位赋值 0
// 常用于状态压缩

$$三.快速幂_{_{二进制的运用}}$$

对于任意 $a^b$ ,其中 $b = {(2^0) + 2^1 + 2^2 + 2^3 +…+ 2^k}$, 因此可以将 b 减小,转换成底数增大;

即当 b & 1 == 0 (b 为偶数)： ${a ^ b}$ = ${a ^ 2 { ^ { ^ {log_2^b}} } }$

否则: ${a ^ b}$ = ${a * a { ^ {b - 1}} }$

例题：快速幂

#include <iostream>

using namespace std;

typedef long long ll;

ll a, b, p;

ll mi(ll a, ll b, ll p){
    ll res = 1;

    while(b){
        if( b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res % p;
}

int main(){
    cin>> a >> b >> p;

    cout << mi(a, b, p) <<endl;
    return 0;
}