banner
NEWS LETTER

位运算 | OI笔记

Scroll down

计算机数据存储方式

例:当(int)x = 10
注:int类型整数共计有32位,不足的位数在前面补0

原码

对于一个
表示原本的二进制数:x = 000…1010

反码

将二进制数的每一位进行取反运算:x = 111…0101

补码

对于x,除符号位不变之外进行~x + 1的操作:x = 111…0110

shudecunchu


进制转换

  • 10进制转2进制: 短除法,逆序取余

  • 2进制转10进制: 乘权求和

  • 二进制转八进制: 取二进制的三位

  • 八进制转二进制

同理,二进制与十六进制之间的转换也可以类比以上的方法,每四位转换为一个十六进制

一张模板走天下

注:在此62进制的数中
0 ~ 9 表示 0 ~ 9
A ~ Z 表示 11 ~ 35
a ~ z 表示 36 ~ 61
另外,此模板使用了高精度,可以适用于所有情况

此题可以简化为两个目标:

  • $a$ 进制转十进制(秦九韶迭代)
  • 十进制转 $b$ 进制

图解:

transform

位运算

按位与 &

0 & 0 = 0, 1 & 0 = 0, 1 & 1 = 1

与运算的应用:

  • 取出某一数的后某位

  • 判断一个整数的奇偶性

x & 1 = 0 偶数, x & 1 = 1 奇数

  • 返回n的最后一位1以及之后的0: lowbit(n)

lowbit 实现方式:

1
2
3
4
int lowbit(int x)
{
return x & -x;
}

按位或 |

0 | 0 = 0, 1 | 0 = 1, 1 | 1 = 1

按位异或 ^

0 ^ 0 = 0, 1 ^ 0 = 1, 1 ^ 1 = 0

值得注意的是,按位异或满足交换律和结合律,因此:

洛谷1496-找筷子

一个非常巧妙的解法

1
2
3
4
5
6
7
8
9
10
int n;
cin >> n;
int ans = 0;
for (int i = 0; i < n; i ++)
{
int tmp;
cin >> tmp;
ans = ans ^ tmp;
}
cout << ans << endl;

取反 ~

返回n的第k位数字: n >> k + 1

位运算内建函数

1
int __builtin_ffs(int x);

返回 $x$ 的二进制末尾最后一个 $1$ 的位置,位置的编号从 $1$ 开始(最低位编号为 $1$ )。当 $x$ 为 $0$ 时返回 $0$

1
int __builtin_clz(unsigned int x);

返回 $x$ 的二进制的前导 $0$ 的个数。当 $x$ 为 $0$ 时,结果未定义 ($ub$)。

1
int __builtin_ctz(unsigned int x);

返回 $x$ 的二进制末尾连续 $0$ 的个数。当 $x$ 为 $0$ 时,结果未定义 ($ub$)。

1
int __builtin_clrsb(int x);

当 $x$ 的符号位为 $0$ 时返回 $x$ 的二进制的前导 $0$ 的个数减一,否则返回 $x$ 的二进制的前导 $1$ 的个数减一。

1
int __builtin_popcount(unsigned int x);

返回 $x$ 的二进制中 $1$ 的个数。

Other Articles
cover
双指针算法 | OI笔记
  • 22/10/04
  • 17:16
  • 信息竞赛
cover
前缀和 | OI笔记
  • 22/09/30
  • 11:31
  • 信息竞赛
Please enter keywords to search