Bit Manipulation

STL, bit, leetcode

二进制计算基本概念

操作符 功能 解释
~ 位求反 将操作数的每一个二进制位取反
<< 左移 将左操作数的各个位向左移动右操作数位
>> 右移 将左操作数的各个位向右移动右操作数位
& 位或 两个操作数均为1结果为1，否则为0
^ 位异或 对于每个位，两个操作数对应的位只有一个为1，则结果该位为1，否则为0
¦ 位或 对于每个位，两个操作数至少一个为1，则结果该位为1，否则为0

注

强烈建议用unsigned整型操作数。
<<和>>的右操作数必须不是负数，并且必须严格小于左操作数位数的值，否则操作结果未定义。这两个操作都是用0补充空位，并丢弃移出去的位。

一个手动计算的示例

手动二进制计算示例
二进制乘法：

1
2
3
4
5
0011 * 0101
= 0011 * 1 * 2^0 + 0011 * 0 * 2^1 + 0011 * 1 * 2^2 + 0011 * 0 * 2^3
= 0011 + 0011 << 2
= 0011 + 1100
= 1111

其中第三列的可以用一些技巧计算：

  1. 0110 + 0110等价于0110 * 2，也等价于把0110左移一位。
  2. 因为0100等价于4，也就是222^2。凡是乘以2n2^n的操作都可以通过左移n位来计算。所以将0011左移2位得到1100。
  3. 每一位和自己的取非值进行XOR操作都是1。所以a^(~a)的结果永远是一列1。
  4. 一个像x&(~0<<n)的操作会将x最右边的n位清0。通过进行~0<<n操作，我们得到一个1右面跟着n个0。再与x进行AND操作，会将x的最右n位清0。注意~0和1可不一样哦。~0是11111111,1是00000001。
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <bitset>
using namespace std;
int main()
{
	// 12 is 1100
	std::cout << std::bitset<sizeof(unsigned int)*8>(12 & (~0 << 2)) << std::endl;	// 00000000000000000000000000001100
	std::cout << std::bitset<sizeof(unsigned int)*8>(12 & (1 << 2)) << std::endl;	// 00000000000000000000000000000100
	std::cout << std::bitset<sizeof(unsigned int)*8>(1 << 2) << std::endl;	// 00000000000000000000000000000100
	std::cout << std::bitset<sizeof(unsigned int)*8>(~0 << 2) << std::endl;	// 11111111111111111111111111111100
	system("Pause");
}

位操作相关的运算符优先级

Precedence Operator Description Associativity
3 ~ Bitwise NOT Right-to-left
7 << >> Bitwise left shift and right shift Left-to-right
10 & Bitwise AND Left-to-right
11 ^ Bitwise XOR(exclusive or) Left-to-right
12 ¦ Bitwise OR(inclusive or) Left-to-right
15 <<= >>= Assignment by bitwise left shift and right shift Right-to-left
15 &= ^= ¦= Assignment by bitwise AND, XOR, and OR Right-to-left

常见计算技巧

常见二进制计算技巧

常见二进制操作

Get Bit(得到某一位的Bit值)

方法是把1左移i位，得到一个类似00010000的值。再与num进行一个AND操作，就可以把第i位之外的值都清0。最后，把得到的值与0进行比较，如果结果不是0，那么第i位一定是1，否则一定是0。

1
2
3
4
bool get_bit(int num, int i)
{
	return ((num & (1 << i)) != 0);
}

Set Bit(设置某一位的Bit值为1)

方法是把1左移i位，得到一个类似00010000的值。再与num进行一个OR操作，只有第i位的值会被影响。

1
2
3
4
int set_bit(int num, int i)
{
	return num | (1 << i);
}

Clear Bit(清零某位的Bit值)

方法差不多是SetBit的反转。首先得到一个类似00010000的值，然后取反得到11101111。然后与num进行AND操作。这样可以让某位变成0，同时保持其他位不受影响。

1
2
3
4
5
int clear_bit(int num, int i)
{
	int mask = ~(1 << i);
	return num & mask;
}

如果想把包含i在内一直到到最左边的所有位都清零。

1
2
3
4
5
int clear_i_to_leftmost_bit(int num, int i)
{
	int mask = (1 << i) - 1;
	return num & mask;
}

如果想把最右边到包含i在内的所有位都清零。

1
2
3
4
5
int clear_rightmost_to_i_bit(int num, int i)
{
	int mask = ~((1 << (i + 1)) - 1);
	return num & mask;
}

Update Bit(设置某位的Bit值)

方法差不多是把SetBit和ClearBit组合起来。首先，通过用一个长得像11101111的遮罩把num第i位的值清0。然后把想设置的值v左移i位，这样会得到一个除了第i位是v，其他位都是0的数。然后让这两个数进行OR操作，第i位就会变成v的值。

1
2
3
4
5
int update_bit(int num, int i, int v)
{
	int mask = ~(1<< i);
	return (num & mask) | (v << i);
}

STL中的bitset类型

需要包含头文件：

1
2
#include <bitset>
using std::bitset;

bitset对象的定义和初始化

bitset类型对象的区别仅在其长度而不在其类型。在定义bitset时，要明确bitset含有多少位，须在尖括号里给出它的长度值：

1
bitset<32> bitvec;	// 32 bits, all zero

给出的长度值必须是常量表达式。必须定义为整型字面值常量或是已用常量值初始化的整型的const对象。
初始化bitset对象的方法

代码 说明
bitset<n> b; b有n位，每位都为0
bitset<n> b(u); b是unsigned long型u的一个副本
bitset<n> b(s); b是string对象s中含有的位串的副本
bitset<n> b(s, pos, n); b是s中从位置pos开始的n个位的副本

用unsigned值初始化bitset对象

十六进制值0xffff表示为二进制位就是十六个1和十六个0(每个0xf可表示为1111)。

1
2
3
4
5
6
// bitvec1 is smaller than the initializer
bitset<16> bitvec1(0xffff);		// bits 0...15 are set to 1
// bitvec2 same size as initializer
bitset<32> bitvec2(0xffff);		// bits 0...15 are set to 1; 16...31 are 0
// on a 32-bit machine, bits 0 to 31 initialized from 0xffff
bitset<128> bitvec3(0xffff);	// bits 32 through 127 initialized to 0

用string对象初始化bitset对象

从string对象读入位集的顺序是从右向左。即string对象最右边字符（下标最大的那个字符）用来初始化bitset对象的低阶位（即下标为0的位）。

1
2
3
4
5
string strval("1100");
bitset<32> bitvec4(strval);	// 1100
string str("1111111000000011001101")
bitset<32> bitvec5(str, 5, 4);	// 4 bits starting at str[5], 1100
bitset<32> bitvec6(str, str.size() - 4);	// use last 4 characters, 1101

bitset对象上的操作

bitset操作

代码 说明
b.any() b中是否存在置为1的二进制位？
b.none() b中不存在置为1的二进制位吗？
b.count() b中置为1的二进制位的个数，返回值类型是size_t
b.size() b中二进制位的个数，返回值类型是size_t
b[pos] 访问b中在pos处的二进制位
b.test(pos) b中在pos处的二进制位是否是1？
b.set() 把b中所有二进制位都置为1
b.set(pos) 把b中在pos处的二进制位置为1
b.reset() 把b中所有二进制位都置为0
b.reset(pos) 把b中在pos处的二进制置为0
b.flip() 把b中所有二进制位逐位取反
b.flip(pos) 把b中在pos处的二进制位取反
b.to_ulong() 用b中同样的二进制位返回一个unsigned long值
os << b 把b中的位集输出到os流

测试整个bitset对象

1
2
3
4
5
bitset<32> bitvec;	// 32 bits, all zero
bool is_set = bitvec.any();	// false, all bits are zero
bool is_not_set = bitvec.none();	// true, all bits are zero
size_t bits_set = bitvec.count();	// returns number of bits that are on
size_t sz = bitvec.size();	// return 32

访问bitset对象中的位

1
2
3
4
5
6
7
8
9
// assign 1 to even numbered bits
for (int index = 0; index != 32; index += 2)
	bitvec[index] = 1;
// equivalent loop using set operation
for (int index = 0; index != 32; index += 2)
	bitvec.set(index);
// test if a bit is 1
if (bitvec.test(i)) {}
if (bitvec[i]) {}

对整个bitset对象进行设置

1
2
3
4
5
bitvec.reset();	// set all the bits to 0
bitvec.set();	// set all the bits to 1
bitvec.flip(0);	// reverse value of first bit
bitvec[0].flip();	// also reverse the first bit
bitvec.flip();	// reverses value of all bits

获取bitset对象的值

仅当bitset类型的长度小于或等于unsigned long的长度时，才可以使用to_ulong操作：

1
usigned long ulong = bitvec3.to_ulong();

输出二进制数

1
bitset<32> bitvec2(0xffff);	// bits 0...15 are set to 1; 16...31 are 0

输出结果为：00000000000000001111111111111111

使用位操作符

bitset类也支持内置的位操作符。

Using Bitsets as Sets of Flags

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bitset>
#include <iostream>
using namespace std;
int main()
{
	// enumeration type for the bits
	// - each bit represents a color
	enum Color {red, yellow, green, blue, white, black,
				numColors};
	// create bitset for all bits/colors
	bitset<numColors> usedColors;
	// set bits for two colors
	usedColors.set(red);
	usedColors.set(blue);
	// print some bitset data
	cout << "bitfield of used colors:	" << usedColors << endl;
	cout << "number   of used colors:	" << usedColors.count() << endl;
	cout << "bitfield of unused colors:	" << ~usedColors << endl;
	// if any color is used
	if (usedColors.any())
	{
		// loop over all colors
		for (int c = 0; c < numColors; ++c)
		{
			// if the actual color is used
			if (usedColors[(Color)c])
			{
				//...
			}
		}
	}
	system("Pause");
}

一些利用二进制思路解决的题目

[Brute Force] | Subsets
[Brute Force] | Subsets II
[Array] | Gray Code
[Array] | Single Number
[Array] | Single Number II
[Brute Force] | Power of Four

[1] C++ Primer 5th Edition
[2] Cracking the Code Inteview
[3] The C++ Standard Library 2nd Edition
[4] http://en.cppreference.com/w/cpp/language/operator_precedence
[5] leetcode