二进制与位运算

二进制与位运算

二进制和位运算是计算机科学和编程中非常重要的概念，广泛应用于底层编程、硬件控制、数据加密、图像处理等领域。理解二进制与位运算是掌握计算机系统内部工作原理的基础。

二进制基础

二进制是计算机使用的基础数字系统，它只使用两种数字：0 和 1。每一位数字称为“二进制位”或者“bit”。在二进制中，每一位的值是由其位置决定的。常见的二进制位数包括：

1位：0 或 1。
8位（字节）：一个字节（Byte），表示范围为 0 到 255。
32位、64位：用于表示更大的整数。

四位二进制数

//无符号
int min == 0;
int max == 15;

0000 → 0
0001 → 1
0010 → 2
0011 → 3
0100 → 4
0101 → 5
0110 → 6
0111 → 7
1000 → 8
1001 → 9
1010 → 10
1011 → 11
1100 → 12
1101 → 13
1110 → 14
1111 → 15

//有符号
int min == -8;
int max == 7;

0000 → 0
0001 → 1
0010 → 2
0011 → 3
0100 → 4
0101 → 5
0110 → 6
0111 → 7
//正数 -> 取反加一 -> 负数 -> 取反加一 ->正数
1000 → -8
//最小的负数不支持这个操作
1001 → -7
1010 → -6
1011 → -5
1100 → -4
1101 → -3
1110 → -2
1111 → -1

N位二进制数

//无符号表示的范围
0 ~ (2^N - 1)

//有符号表示的范围
-2^(N-1) ~ 2^(N-1) - 1

// 有符号 int 的范围：
int s_int_min = -2147483648;  // -2^31
int s_int_max = 2147483647;   // 2^31 - 1

// 有符号 long long 的范围：
long long s_long_long_min = -9223372036854775808;  // -2^63
long long s_long_long_max = 9223372036854775807;   // 2^63 - 1

位运算基础

位运算（Bitwise operations）是对整数在 二进制位（bit）上的操作。在计算机中，数据是以二进制的形式存储的，位运算直接对这些二进制数据进行操作，效率非常高。位运算的常见操作包括 与、或、异或、取反、左移、右移等

#include <bits/stdc++.h>
using namespace std;

int main() {
	int a = 5;  // 二进制表示： 0101
	int b = 3;  // 二进制表示： 0011
	
	// 与运算（AND）
	int and_result = a & b;
	cout << "a & b = " << and_result << " \t(二进制：" << bitset<8>(and_result) << ")" << endl;
	
	// 或运算（OR）
	int or_result = a | b;
	cout << "a | b = " << or_result << " \t(二进制：" << bitset<8>(or_result) << ")" << endl;
	
	// 异或运算（XOR）
	int xor_result = a ^ b;
	cout << "a ^ b = " << xor_result << " \t(二进制：" << bitset<8>(xor_result) << ")" << endl;
	
	// 取反运算（NOT）
	int not_result = ~a;
	cout << "~a = " << not_result << " \t(二进制：" << bitset<8>(not_result) << ")" << endl;
	
	// 左移运算
	int left_shift = a << 1;  // 将a的二进制数左移1位
	cout << "a << 1 = " << left_shift << " \t(二进制：" << bitset<8>(left_shift) << ")" << endl;
	
	// 右移运算
	int right_shift = a >> 1;  // 将a的二进制数右移1位
	cout << "a >> 1 = " << right_shift << " \t(二进制：" << bitset<8>(right_shift) << ")" << endl;
	
	return 0;
}

//非负数 << 1, 等同于乘以2
//非负数 << 2, 等同于乘以4
//非负数 << 3, 等同于乘以8
//非负数 << i, 等同于乘以2 ^ i
//...
//非负数 >> 1, 等同于除以2
//非负数 >> 2, 等同于除以4
//非负数 >> 3, 等同于除以8
//非负数 >> i, 等同于除以2 ^ i
//...
//只有非负数符合这个特征，负数不能用

二进制打印函数

void printIntBinary(int num)
{
	for (int i = 31; i >= 0; i--) {
		// 检查第 i 位是否为 1
		cout << ((num & (1 << i)) ? "1" : "0");
	}
	cout << endl; 
}

void printLongLongBinary(long long num)
{
    for (int i = 63; i >= 0; i--) {  
        // 使用1LL表示long long常量
        cout << ((num & (1LL << i)) ? "1" : "0");  
    }
    cout << endl;  
}

y总的位运算小技巧

n的二进制表示中第k位

int n = 15;

k = 3 2 1 0
n = 1 1 1 1 

n >> k & 1

1的个数

#include <iostream>
using namespace std;

int lowbit(int x)
{
    return x & -x;
}

int main()
{
    int t;
    cin >> t;
    while (t--) {
        int x;
        cin >> x;
        int ans = 0;
        while (x > 0) {
            x -= lowbit(x);
            ans++;
        }
        cout << ans << " ";
    }

    return 0;
}

异或运算的性质

//(1) 异或运算是无进位相加
//(2) 异或运算满足交换律和结合律
//(3) 0 ^ n = n, n ^ n = 0
//(4) 整体异或和如果为x, 整体中某部分异或和如果为y, 那么剩下部分的异或和为x ^ y

交换两个数

void solve()
{
	int a, b;
	cin >> a >> b;
	//不妨我们设a = A, b = B;
	a = a ^ b;  //a = A ^ B;
	b = a ^ b;  //b = (A ^ B) ^ B = A ^ (B ^ B) = A;
	a = a ^ b;  //a = (A ^ B) ^ A = B ^ (A ^ A) = B;
	cout << "a = " << a << endl;
	cout << "b = " << b << endl;
	//用这种方法交换两个位置的数一定要保证不在同一位置
 }

比较两个数

//保证n是0或1
//这个函数可以时0变1，1变0
int filp(int n)
{
	return n ^ 1;
}

//这个函数可以返回符号位
//1为负数
//0为非负数
int sign(int n)
{
	return (n >> 31) & 1;
}

void solve()
{
	int a, b;
	cin >> a >> b;
	int c = a - b;
	cout << "c = " << c << endl;
	int returnA = filp(sign(c));
	int returnB = sign(c);
	cout << "returnA = " << returnA << endl;
	cout << "returnB = " << returnB << endl;
	int ans = a * returnA + b * returnB;
	cout <<  "max = " << ans << endl;
}

找到缺失的数

void solve()
{

	//0 - n中缺了一个数
	//找到缺的那个数是什么
	int n;
	cin >> n;
	vector<int> arr(n);
	int sum1 = 0;
	int sum2 = n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		sum1 ^= arr[i];
		sum2 ^= i;
	}
	int ans = sum1 ^ sum2;
	cout << ans << endl;	
}

找到出现了奇数次的数

void solve()
{
	//数组中有一个数出现的次数为奇数，其他所有的数都出现了偶数次
	//请找出那个出现了奇数次的那个数
	int n;
	cin >> n;
	vector<int> arr(n);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		ans ^= arr[i];
	}
	cout << ans << endl;
}

找到两个出现的奇数次的数

void solve()
{
	//数组中只有两种数出现了奇数次，其他数都出现了偶数次
	//请求出这两个出现了奇数次的数
	int n;
	cin >> n;
	int eor1 = 0;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		eor1 ^= arr[i];
	}
	//eor1的结果就是a ^ b
	//提取出eor1二进制中最右侧的1
	int rightOne = eor1 & (-eor1);
	int eor2 = 0;
	for (int i = 0; i < n; i++) {
		//如果数组中的数最右侧的1在相同位置
		//那么就开始求eor2的异或和
		//我们不妨设a在该位置为1，b在该位置为0
		//那么所有最右侧的数为1的数就包括一堆出现了偶数次的数的数和一个1
		//所以eor2 = a;
		//那么eor1 ^ eor2 = b;
		//同理如果a在该位置为0，b在该位置为1也成立
		if ((arr[i] & rightOne) == rightOne) {
			eor2 ^= arr[i];
		}
	}
	cout << (eor1 ^ eor2) << " " << eor2 << endl;
}

找到唯一小于m的数

void solve()
{
	//数组中只有一种数出现的次数少于m次，其他的数都出现了m次
	//请找出是哪个数出现的次数少于了m次
	int n, m;
	cin >> n >> m;
	vector<int> arr(n);
	vector<int> cnt(32);
	//cnt[0]：0位上有多少1
	//cnt[1]：1位上有多少1
	//cnt[2]：2位上有多少1
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		for (int j = 0; j < 32; j++) {
			cnt[j] += (arr[i] >> j) & 1;
		}
	}
	int ans = 0;
	for (int i = 0; i < 32; i++) {
		//其他数都出现的m次
		//实际上就是就是这些数对应位置上的1也出现的m次
		//所以这些位置上的数就可以被m整除
		//但是如果加进来一个出现次数小于m的数
		//那有些位上的数就不能被m整除
		//而这些位就是这个数的1所在位置
		//通过|的操作，实际上是把对应位置的1加进ans里
		if (cnt[i] % m != 0) {
			ans |= (1 << i); 
		}
	}
	cout << ans << endl;
}

位运算的骚操作

判读一个数是不是2的幂

bool check(int n)
{
	if (n > 0 && n == (n & -n)) {
		return true;
	}
	return false;
}

void solve()
{
	int n;
	cin >> n;
	if (check(n)) {
		cout << n << "是2的幂" << endl;
	} else {
		cout << n << "不是2的幂" << endl;
	}
}

判断一个数是不是3的幂

ool check(int n)
{
	//1162261467是int范围内最大的3的幂，它是3 ^ 19
	if (n > 0 && 1162261467 % n == 0) {
		return true;
	}
	return false;
}

void solve()
{
	int n;
	cin >> n;
	if (check(n)) {
		cout << n << "是3的幂" << endl;
	} else {
		cout << n << "不是3的幂" << endl;
	}
}

经典题目

Bits

https://codeforces.com/contest/484/problem/A

#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve()
{
	int l, r;
	cin >> l >> r;
	// 找到 1 最多的一个数
	for (int i = 1; ; i *= 2) {
		// 每次都尝试把 l 的最低位设置为 1
		// 从而使 l 尽可能大，并且使 1 的数量尽可能多
		if ((l | i) <= r) {
			l |= i;
		} else {
			break;
		}
	}
	cout << l << endl;
	
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
} 

最大的位或

https://acm.hdu.edu.cn/showproblem.php?pid=5969

#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve()
{
	int l, r;
	int ans = 0;
	cin >> l >> r;
	// ans = 高位相同的部分 + 后面一部分全部取值为1
	int x = r;
	int d = -1;
	while (x) {
		d++;
		x >>= 1;
	}
	int i;
	for (i = d; i >= 0; i--) {
		// 获取第 i 位
		int t1 = (l >> i) & 1;
		int t2 = (r >> i) & 1;
		if (t1 == t2) {
			ans += t1 * (1LL << i);
		} else {
			break;
		}
 	}
	if (i >= 0) ans += (1LL << (i + 1)) - 1; 
	cout << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}