0x3F

0x3F3F3F3F在算法中是很有用的数值,他是满足以下两个条件的最大值

  1. 整数的两倍不超过0x7FFFFFFF,即int能表示的最大的整数。
  2. 整数的每8位(每个字节)都是相同的。

程序中经常使用memset(a, val, sizeof(a))**初始化int数组,该语句把数值a(0x00~0xFF)填充到a的每个字节**上。

然而,1个int占用4个字,所以memset只能赋值出“每8位相同”的int。


综上所述,0x7F7F7F7F是能用memset初始化出的最大的int。不过,为了避免加法算法上溢繁琐的判断,经常使用**memset(a, 0x3f, sizeof(a))**给数组初始化。

移位运算

在二进制表示下把数字同时向左移动,低位用0填充高位越界后舍弃

1 << n = 2n

n << 1 = 2 * n

算术右移

在二进制表示下把数字同时向右移动,高位以符号位填充低位越界后丢弃

n >> 1 = [n / 2.0]

算术右移等于除以2向下取整

值得注意,在C++中,除法默认向0取整

二进制状态压缩

二进制状态压缩是指:利用一个m位的二进制表示长度为m的布尔数组。

通过位运算访问布尔数组中对应下标的元素。

操作 运算
取出n在二进制表示下的第k位 (n >> k) & 1
取出n在二进制表示下的第0~k-1位(后k位) n & ((1 << k) - 1)
把整数n在二进制表示下的第k位取反 n xor (1 << k)
把整数n在二进制表示下的第k位赋值1 n | (1 << k)
把整数n在二进制表示下的第k位赋值0 n & (~(1 << k))

成对变换

通过计算可以发现,对于非负整数n:

  • 当n为偶数时(最低位为0),n xor 1 = n + 1
  • 当n为奇数时(最低位为1),n xor 1 = n - 1

这一性质常用于图论邻接表存储一对无向边(双向边)。

这两条边一般存储在n和n+1位置(n为偶数)。

lowbit运算

lowbit(n)运算定义为求非负整数n在二进制表示下“最低位的1及其后面所有的0”构成的数值。

如:n = 10 = (1010)2,则lowbit(n) = (10)2 = 2。


证明过程:

设n > 0,n的第k位是1,第0~k - 1位都是0。

为了实现lowbit运算,先把n取反,此时第k位是0,其余位是1。

再令n = n + 1,由于进位,第k位是1,其余位为0。

进行完上述取反加一操作后,n的第k+1到最高位恰好与原来相反。lowbit(n) = n & (~n + 1)。

在补码表示下:n = - 1 - n,因此:lowbit(n) = n & (n + 1) = n & (-n)