位运算

•【3】位运算：与（&）、或（|）、非（~）、 异或（^）、左移、右移 •【1】数的进制：二进制、八进制、十六进制和十进制及其转换 格雷码

有符号数处理 (signed number representations)

二进制

0:0
1:1
10:2
11:3
...

为了表达方便，补齐到 8 位

二进制

00000000:0
00000001:1
00000010:2
00000011:3
00000100:4
00000101:5
...
11111111:255

原码 (sign-and-magnitude)
存-x，最高位是1，其他位是x的表示法

反码（ones' complement）
存-x，x的表示法取反
反码存在-0的问题

补码（two's complement）
存负数用补码

移码（offset binary)
用不到，用全0表示最小的二进制数，全1表示最大的二进制数

二进制

00000000:0
00000001:1
00000010:2
00000011:3
00000100:4
00000101:5
01111111:127
10000000:-128
10000001:-127
...
11111110:-2
11111111:-1

如果 x 是正数，那么 -x 的补码是
x的二进制取反加一

00000011: 3
取反
11111100:-4
加一
11111101:-3

补码的好处：计算加减法不需要考虑正负数

原码和反码只有理论意义

按位取反 （bitwise NOT, complement）

0 变成 1
1 变成 0

NOT 0111 (十进制 7)
= 1000 (十进制 8)

NOT 10101011 (十进制 171)
= 01010100 (十进制 84)

按位取反与在 C++ 和 Python 中的符号是~

按位与 （bitwise AND）

同时是1，结果是1
否则是0

    0101 (decimal 5)
AND 0011 (decimal 3)
  = 0001 (decimal 1)

按位与在 C++ 和 Python 中的符号是&
注意区分 按位与 和 逻辑与

按位或 （bitwise OR）

同时是0，结果是0
否则是1

   0101 (decimal 5)
OR 0011 (decimal 3)
 = 0111 (decimal 7)

按位或在 C++ 和 Python 中的符号是|
注意区分 按位或 和 逻辑或

按位异或 （bitwise XOR)

相同为0，不同为1
二进制不进位加法

    0101 (decimal 5)
XOR 0011 (decimal 3)
  = 0110 (decimal 6)

异或在 C++ 和 Python 中的符号是^，这个符号不表示乘方

异或 和 加法很类似，有结合律，交换律
异或的逆运算也是异或，如果 (a^b)==c 那 么a==(c^b) 并且 b==(c^a)
一个数字异或自己一定为0 (x^x)==0

左移

左移x位 相当于 乘以2的x次方
当然移动后可能超过int（或long long）的范围

左移，在最右边补0

左移位数不能超过类型本身的位数

int x = 1;
cout << (x << 32) << endl;

这是未定义行为，这样无法得到想要的结果

右移

右移x位 相当于 除以2的x次方，向下取整（一般的除法是向零取整）

右移，在最左边补符号位（负数补1，非负数补0），无符号类型补0

右移位数不能超过类型本身的位数

int x = 1;
cout << (x >> 32) << endl;

这是未定义行为，这样无法得到想要的结果

#include <bits/stdc++.h>
using namespace std;
int main()
{
    cout << (1 << 32) << endl;
    cout << (1 >> 32) << endl;
    int x = 1;
    cout << (x << 32) << endl;
    cout << (x >> 32) << endl;
    return 0;
}

在我的计算机上，前两个输出0，后两个输出1

内置函数

__builtin_popcount
__builtin_clz
__builtin_ctz

取反!

非0变成0，0变成1
!0结果是1
!1结果是0
!2结果是0
!!2结果是1

一般不区分 1 和 true
一般不区分 0 和 false

逻辑与 && and

如果其两个变量的真值都为真，其结果为真，否则其结果为假。

逻辑或 || or

如果其两个变量中有一个真值为真，其结果为真，两个变量同时为假，其结果为假。

二进制

整数部分，把十进制转成二进制一直分解至商数为0。读余数从下读到上，即是二进制的整数部分数字。
比如 十进制23 是 二进制10111

23 / 2 = 11 余 1
11 / 2 = 5 余 1
5 / 2 = 2 余 1
2 / 2 = 1 余 0
1 / 2 = 0 余 1

从下往上读是 10111

按位取反 ~ compl

按位取反是一元运算符，对一个二进制数的每一位执行逻辑反操作。使数字1成为0，0成为1。
在计算机中，比如 int 类型，一共有 32 位，前面的位需要补 0
比如 255 的二进制是

 255 = 00000000 00000000 00000000 11111111
~255 = 11111111 11111111 11111111 00000000 = 4294967040 = -256

补码

补码是一种用二进制表示有符号数的方法，也是一种将数字的正负号变号的方式，常在计算机科学中使用。
正数和0的补码就是该数字本身。负数的补码则是将其对应正数按位取反再加1。
补码系统的最大优点是可以在加法或减法处理中，不需因为数字的正负而使用不同的计算方式。

按位与& bitand

按位与是双目运算符。
其功能是参与运算的两数各对应的二进位相与。
只有对应的两个二进位都为1时，结果位才为1。

3 0011
5 0101
&
1 0001

按位或| bitor

按位或是双目运算符。
其功能是参与运算的两数各对应的二进位相或。
只要对应的二个二进位有一个为1时，结果位就为1。

3 0011
5 0101
|
7 0111

异或^ xor

异或是双目运算符。
其功能是参与运算的两数各对应的二进位做不进位加法。
也可以理解为相同为0，不同为1。

3 0011
5 0101
^
6 0110

左移 <<

二进制向左移动，注意对于 int 类型一共有 32 位，移出界的会消失，右侧补 0

255 << 2 = 255 * 4 = 1020

左移 x 位相当于 乘以 2 的 x 次方

右移 >>

二进制向右移动，注意对于 int 类型一共有 32 位，移出界的会消失，左侧补符号位

1023 >> 2 = 255
-1 >> 1 = -1

右移 x 位相当于 除以 2 的 x 次方 下取整
注意区分下取整和向零取整

8位

11111100 -4
11111101 -3
11111110 -2
11111111 -1
00000000 0
00000001 1
00000010 2
00000011 3

11111111 255

00000001

257

-x = (~ x) + 1
-~x = x + 1
~-x = x - 1

x & (~x + 1)

x=
110100
~x
001011
~x + 1
001100


least significant bit
lowbit(i) 

i的最大的2的次幂的约数，i转二进制，最低哪一位是1

lowbit(i) = (i & -i)
(i - lowbit(i)) == (i & (i-1))
lowbit(12) = 4
lowbit(13) = 1

i -= i & -i 等价于 i &= i - 1

(-i) == ((~i)+1)
(~i) == ((-i)-1)
(-~i) == i + 1
-~-~-~i = i + 3
(~-i) == i - 1
~-~-~-i = i - 3

补码存负数
00000011   3
00000010   2
00000001   1
00000000   0
11111111  -1
11111110  -2

lowbit(i) = i的约数中，最大的2的次幂
i写成二进制，最低是1的一位

lowbit(12) = 4
 1 1 0 0
   ^
 8 4 2 1

lowbit(17) = 1
 1 0 0 0 1
16 8 4 2 1
         ^

__builtin_popcount 1的个数
__builtin_parity 1的个数的奇偶性
__builtin_clz count leading zero 前导0的个数
__builtin_ctz count trailing zero 后缀0的个数




4
00000000 00000000 00000000 00000100
__builtin_clz(4) = 29
31 - __builtin_clz(4) = 2
31 - __builtin_clz(7) = 2

m的第i位

if (m >> i & 1)
{

}

一元位运算有多少种操作符？

一元：操作数只有一个数字，比如取反，取非，负号，正号
4种
一元位运算输入有0和1两种可能，输出有0和1两种可能，所以是4种

  1. 输入0输出0 输入1输出0 直接输出0 AND 0
  2. 输入0输出0 输入1输出1 直接输出x本身 AND 1, OR 0, XOR 0
  3. 输入0输出1 输入1输出0 直接输出!x XOR 1
  4. 输入0输出1 输入1输出1 直接输出1 OR 1

二元位运算有多少种操作符？

二元：操作数只有一个数字，比如加减乘除模 与 或 异或
16种
二元位运算输入(x,y)有(0,0) (0,1) (1,0) (1,1) 4种可能，输出有0和1两种可能，所以是16种
每个运算用4位数表示，
第一个数字表示输入(0,0)的输出
第二个数字表示输入(0,1)的输出
第三个数字表示输入(1,0)的输出
第四个数字表示输入(1,1)的输出
0000 直接输出0
0001 与 AND
0011 直接输出x
0101 直接输出y
0110 异或 XOR
0111 或 OR
1000 或非 NOR
1001 同或 XOR
1010 直接输出!y
1100 直接输出!x
1110 与非 NAND
1111 直接输出1

题目列表

P4310 绝世好题

spoj MAXXOR - Find the max XOR value

https://www.luogu.com.cn/problem/SP25844
(1 << (32 - __builtin_clz(L ^ R))) - 1

CF484A Bits

ans = l
把ans的最后一个0改成1 如果<=r继续改

ans |= ans + 1

x & (x - 1)
把最后一个1改成0
x | (x + 1)
把最后一个0改成1

(x&y) + (x|y) > max(x, y) * 2

每一位有4种情况

  1. 初始0最终是0，初始1最终是0
  2. 初始0最终是0，初始1最终是1
  3. 初始0最终是1，初始1最终是0
  4. 初始0最终是1，初始1最终是1

P1100 高低位交换

https://www.luogu.com.cn/problem/P1100

题目描述

给出一个小于2322^{32}的正整数。这个数可以用一个3232位的二进制数表示（不足3232位用00补足）。我们称这个二进制数的前1616位为“高位”，后1616位为“低位”。将它的高低位交换，我们可以得到一个新的数。试问这个新的数是多少（用十进制表示）。

例如，数13145201314520用二进制表示为000000000001010000001110110110000000 0000 0001 0100 0000 1110 1101 1000（添加了1111个前导00补足为3232位），其中前1616位为高位，即00000000000101000000 0000 0001 0100；后1616位为低位，即00001110110110000000 1110 1101 1000。将它的高低位进行交换，我们得到了一个新的二进制数000011101101100000000000000101000000 1110 1101 1000 0000 0000 0001 0100。它即是十进制的249036820249036820。

输入格式

一个小于2322^{32}的正整数

输出格式

将新的数输出

样例 #1

样例输入 #1
1314520
样例输出 #1
249036820

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
long long x;
int main() {
	cin >> x;
	cout << ((x >> 16) + ((x & 65535) << 16)) << endl;
	return 0;
}

题解

P2114 [NOI2014] 起床困难综合症

https://www.luogu.com.cn/problem/P2114

题目描述

2121 世纪，许多人得了一种奇怪的病：起床困难综合症，其临床表现为：起床难，起床后精神不佳。作为一名青春阳光好少年，atm 一直坚持与起床困难综合症作斗争。通过研究相关文献，他找到了该病的发病原因：在深邃的太平洋海底中，出现了一条名为 drd 的巨龙，它掌握着睡眠之精髓，能随意延长大家的睡眠时间。正是由于 drd 的活动，起床困难综合症愈演愈烈，以惊人的速度在世界上传播。为了彻底消灭这种病，atm 决定前往海底，消灭这条恶龙。历经千辛万苦，atm 终于来到了 drd 所在的地方，准备与其展开艰苦卓绝的战斗。drd 有着十分特殊的技能，他的防御战线能够使用一定的运算来改变他受到的伤害。具体说来，drd 的防御战线由 nn 扇防御门组成。每扇防御门包括一个运算 opop 和一个参数 tt，其中运算一定是 OR,XOR,AND\text{OR},\text{XOR},\text{AND} 中的一种，参数则一定为非负整数。如果还未通过防御门时攻击力为 xx，则其通过这扇防御门后攻击力将变为 xopt。最终 drd 受到的伤害为对方初始攻击力 xx 依次经过所有 nn 扇防御门后转变得到的攻击力。

由于 atm 水平有限，他的初始攻击力只能为 00 到 mm 之间的一个整数（即他的初始攻击力只能在 0,1,…,m0,1,\ldots,m 中任选，但在通过防御门之后的攻击力不受 mm 的限制）。为了节省体力，他希望通过选择合适的初始攻击力使得他的攻击能让 drd 受到最大的伤害，请你帮他计算一下，他的一次攻击最多能使 drd 受到多少伤害。

输入格式

输入文件的第 11 行包含 22 个整数，依次为 n,mn, m，表示 drd 有 nn 扇防御门，atm 的初始攻击力为 00 到 mm 之间的整数。

接下来 nn 行，依次表示每一扇防御门。每行包括一个字符串 opop 和一个非负整数 tt，两者由一个空格隔开，且 opop 在前，tt 在后，opop 表示该防御门所对应的操作，tt 表示对应的参数。

输出格式

输出一行一个整数，表示 atm 的一次攻击最多使 drd 受到多少伤害。

样例 #1

样例输入 #1
3 10
AND 5
OR 6
XOR 7
样例输出 #1
1

提示

【样例说明】

atm 可以选择的初始攻击力为 0,1,…,100,1,\ldots ,10。

假设初始攻击力为 44，最终攻击力经过了如下计算

4 AND 5=44 \text{ AND } 5 = 4

4 OR 6=64 \text{ OR } 6 = 6

6 XOR 7=16 \text{ XOR } 7 = 1

类似的，我们可以计算出初始攻击力为 1,3,5,7,91,3,5,7,9 时最终攻击力为 00，初始攻击力为 0,2,4,6,8,100,2,4,6,8,10 时最终攻击力为 11，因此atm的一次攻击最多使drd受到的伤害值为 11。

【数据规模与约定】

参考代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int f0 = 0, f1 = -1;
	int n, m, x, z = 0;
	char s[4];
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		scanf("%s%d", s, &x);
		if (*s == 'A')
		{
			f0 &= x;
			f1 &= x;
		}
		else if (*s == 'O')
		{
			f0 |= x;
			f1 |= x;
		}
		else
		{
			f0 ^= x;
			f1 ^= x;
		}
	}
	for (int i = 30; i >= 0; i--)
	{
		if (f0 >> i & 1)
		{
			z += 1 << i;
		}
		else if (f1 >> i & 1 && m >> i)
		{
			m -= 1 << i;
			z += 1 << i;
		}
	}
	printf("%d\n", z);
	return 0;
}

题解

P4144 大河的序列

https://www.luogu.com.cn/problem/P4144

题目背景

“唯有龙虎相伴 最是脉脉深情”

题目来源：KingSann

题目描述

大河有一些袜子，但经常十分散乱的堆放着。

有一天龙儿忍不住了，于是将袜子放到了一个序列上（称作袜子序列）。

每个袜子都有一个dirtydirty值，定义袜子序列的dirtydirty值为 max⁡((dirtyl bitand dirtyl+1 bitand ⋯ bitand dirtyr)+(dirtyl bitor dirtyl+1 bitor ⋯ bitor dirtyr))\max \left( (dirty_{l} \ bitand \ dirty_{l+1} \ bitand \ \cdots \ bitand \ dirty_{r}) + (dirty_{l} \ bitor \ dirty_{l+1} \ bitor \ \cdots \ bitor \ dirty_{r}) \right) ，其中 dirtyidirty_{i} 表示 第 ii 只袜子 的 dirtydirty 值，bitandbitand表示按位与（C++中是&），bitorbitor表示按位或（C++中是|）。

简而言之，就是找一段连续子序列，使得所有数字的按位与加上按位或最大。

如果这个袜子序列的dirtydirty值达到了某个阈值，那么龙儿会讨厌大河的。

大河当然不希望这样了，于是她想知道这个袜子序列的dirtydirty值是多少。

输入格式

第一行三个整数 n,b,pn,b,p ，分别表示数列长度和输出相关的东西

第二行有 nn 个整数，表示这个数列的初始数值

输出格式

设答案为 xx ，你需要输出 (x+233)b  mod  p(x+233)^{b} \,\, \text{mod} \,\,p

样例 #1

样例输入 #1
10 1 10000000
7 9 9 4 0 0 8 8 4 7
样例输出 #1
251

提示

1≤n,p≤1051 \le n, p \le 10^{5}

0≤b,ditryi≤1070 \le b, ditry_{i} \le 10^{7}

对于测试点 11 和测试点 22 的数据，保证 1≤n≤1001 \le n \le 100

参考代码

题解

P1461 [USACO2.1]海明码 Hamming Codes

https://www.luogu.com.cn/problem/P1461

题目描述

给出 n,b,dn,b,d，要求找出 nn 个由 0,10,1 组成的编码，每个编码有 bb 位），使得两两编码之间至少有 dd 个单位的 “Hamming距离”。“

Hamming距离”是指对于两个编码，他们二进制表示法中的不同二进制位的数目。看下面的两个编码 0x554 和 0x234（十六进制数）

0x554 = 0101 0101 0100
0x234 = 0010 0011 0100
不同位    xxx  xx

因为有五个位不同，所以“Hamming距离”是 55。

输入格式

一行，包括 n,b,dn,b,d。

输出格式

nn 个编码（用十进制表示），要排序，十个一行。
如果有多解，你的程序要输出这样的解：假如把它化为 2b2^b 进制数，它的值要最小。

样例 #1

样例输入 #1
16 7 3
样例输出 #1
0 7 25 30 42 45 51 52 75 76
82 85 97 102 120 127

提示

【数据范围】
对于 100%100\% 的数据，1≤n≤641\le n \le 64，1≤b≤81\le b \le 8，1≤d≤71\le d \le 7。

请解释：“必须与其他所有的数相比，Hamming 距离都符合要求，这个数才正确”

答：如样例输出，0,70,7，0,250,25，比较都符合海明码，同样 7,257,25，7,307,30，比较也符合要求，以此类推。题中至少有 dd 个单位，意思就是大于等于 dd 个单位的都可以。

USACO 2.1

翻译来自NOCOW

参考代码

题解

P6599 「EZEC-2」异或

https://www.luogu.com.cn/problem/P6599

题目描述

有 TT 组询问，每次给定两个正整数 n,ln,l，

你需要构造一个长度为 ll 的正整数序列 aa（编号从 11 至 ll），

且满足 ∀i∈[1,l]\forall i\in[1,l]，都有 ai∈[1,n]a_i\in[1,n]。

求：

∑i=1l∑j=1i−1ai⊕aj\sum_{i=1}^l\sum_{j=1}^{i-1}a_i\oplus a_j

的最大值。

为了避免答案过大，对于每组询问，只需要输出这个最大值对 109+710^9+7 取模的结果。

输入格式

第一行一个整数 TT，表示数据组数。

接下来第 22 行到第 T+1T+1 行，每行两个整数 n,ln,l ，分别代表 aia_i 的最大取值与 aa 的长度。

输出格式

共 TT 行，每行一个整数，对应每组询问的答案对 109+710^9+7 取模的结果。

样例 #1

样例输入 #1
1
2 3
样例输出 #1
6

样例 #2

样例输入 #2
2
114 514
1919 180
样例输出 #2
8388223
16580700

提示

【样例解释 #1】
当 n=2,l=3n=2,l=3，aa 取 {1,2,1}\{1,2,1\} 的任一排列时可以得到最大值，为 (1⊕2)+(1⊕1)+(2⊕1)=6(1\oplus2)+(1\oplus1)+(2\oplus1)=6，易证明此时原式有最大值。

【数据规模与约定】

测试点编号 T≤T\le n≤n\le l≤l\le
1∼51\sim5 11 1010 55
66 5×1055\times 10^5 101210^{12} 22
77 5×1055\times 10^5 101210^{12} 33
8∼108\sim10 5×1055\times 10^5 101210^{12} 10510^5

对于 100%100\% 的数据，满足 1≤T≤5×1051\le T\le 5\times10^5，1≤n≤10121\le n\le 10^{12}，2≤l≤1052\le l \le 10^5。

【提示】

  1. 「⊕\oplus」是按位异或符号。如果您不知道什么是按位异或，可以参考这里。
  2. 取模是一种运算，aa 对 bb 取模代表将 aa 赋值为 aa 除以 bb 所得到的余数。
    在 C++ / Python 中的取模符号为 %，在 Pascal 中的取模符号为 mod。
  3. ∑\sum 是求和符号。如果您不知道什么是 ∑\sum 符号，可以参考这里。
  4. 请注意数据的读入输出对程序效率造成的影响。

参考代码

题解

CF784E Twisted Circuit

https://codeforces.com/problemset/problem/784/E
https://www.luogu.com.cn/problem/CF784E

参考代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << ((a^d|b&c)^(a^b)&(c|d)) << endl;
	return 0;
}

题解

CF1220D Alex and Julian

https://codeforces.com/problemset/problem/1220/D
https://www.luogu.com.cn/problem/CF1220D

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, z;
int c[64];
long long a[200020];
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		c[__builtin_ctzll(a[i])]++;
	}
	for (int i = 0; i < 64; i++)
	{
		if (c[z] < c[i])
		{
			z = i;
		}
	}
	cout << n - c[z] << endl;
	for (int i = 0; i < n; i++)
	{
		if (__builtin_ctzll(a[i]) != z)
		{
			cout << a[i] << ' ';
		}
	}
	cout << endl;
	return 0;
}

题解

abc261_e Many Operations

https://atcoder.jp/contests/abc261/tasks/abc261_e
输入n个操作，有 与 或 异或
初始是X=C
执行操作1，输出X
（不重置X为C）
执行操作1和操作2输出X
执行操作1和操作2和操作3输出X
……
执行操作1操作2……操作n输出X

参考代码

题解

假设操作数只有0和1
对于每个前缀，只有4种情况
0变0 1变0 变0
0变0 1变1 不变
0变1 1变0 变1
0变1 1变1 0和1交换

与1 或0 异或0 等价于不变
与0 等价于设成0
或1 等价于设成1
异或1 等价于0和1互换

先与0 再异或1 等价于 等价于设成1

对于前i个操作，一定等价于四种之一

abc238_d AND and SUM

https://atcoder.jp/contests/abc238/tasks/abc238_d
输入非负整数a和s，问是否存(x,y)使得(x&y)==a且(x+y)==s
&是按位与

参考代码

题解

  1. 位运算
    1. 有符号数处理 (signed number representations)
    2. 按位取反 （bitwise NOT, complement）
    3. 按位与 （bitwise AND）
    4. 按位或 （bitwise OR）
    5. 按位异或 （bitwise XOR)
    6. 左移
    7. 右移
    8. 内置函数
    9. 取反!
    10. 逻辑与 && and
    11. 逻辑或 || or
    12. 二进制
    13. 按位取反 ~ compl
    14. 补码
    15. 按位与& bitand
    16. 按位或| bitor
    17. 异或^ xor
    18. 左移 <<
    19. 右移 >>
    20. 一元位运算有多少种操作符？
    21. 二元位运算有多少种操作符？
  2. 题目列表
    1. P4310 绝世好题
    2. spoj MAXXOR - Find the max XOR value
    3. CF484A Bits
    4. P1100 高低位交换
    5. P2114 [NOI2014] 起床困难综合症
    6. P4144 大河的序列
    7. P1461 [USACO2.1]海明码 Hamming Codes
    8. P6599 「EZEC-2」异或
    9. CF784E Twisted Circuit
    10. CF1220D Alex and Julian
    11. abc261_e Many Operations
    12. abc238_d AND and SUM
≡