位运算 - Hao's Blog

位操作是程序设计中对位模式按位或二进制数的一元和二元操作。

位运算操作符

基本的位操作符有与、或、异或、取反、左移、右移这 6 种，它们的运算规则如下所示：

符号	描述	运算规则
&	与	两个位都为 1 时，结果才为 1
\|	或	两个位都为 0 时，结果才为 0
~	取反	0 变 1，1 变 0
^	异或	两个位相同为 0，相异为 1
«	左移	各二进位全部左移若干位，高位丢弃，低位补 0

|右移 | 各二进位全部右移若干位，对无符号数，高位补 0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补 0（逻辑右移）

常用位操作小技巧

取一个整数的最后一位

给定一个整数 a, a & 1的值就是 a 的最后一位

取一个数的第 i 位

给定一个整数 a, a & (1 << i)的值就是 a 的第 i 位

异或操作性质

交换律 a^b=b^a
结合律 a^b^c=a^(b^c)
对于任何数 a，都有a^a=0，a^0=a
自反性 a^b^b = a^0 = a

利用位运算解八皇后问题

八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的 n 皇后摆放问题：这时棋盘的大小变为 n×n，而皇后个数也变成 n。

算法思路

通过 dfs 一行一行的进行搜索，在经过的每个格子上判断该格子是否能够放置皇后，利用 bitmask 储存棋盘状态信息。

代码及注释：

 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
34
35
36
37
38


#include <iostream>
#include <vector>

using namespace std;

int n = 8; //皇后数量
int count = 0; //计数器
int vertical = 0; //竖线
int left_s = 0; //左斜线
int right_s = 0; // 右斜线

void dfs(int r) { // 按行进行 dfs

    for (int c = 0; c < n; c++) { //每一行的每一列判断状态是否合法
        int j = r + c; //右斜线序号
        int k = n - 1 + c - r; //左斜线序号
        if ((((vertical >> c) | (right_s >> j) | (left_s >> k)) & 1) != 0) continue; // 如果该位置不合法 continue
        if (r == n-1) { //如果导到了最后一行，说明找到了解
            count++;
        }
        else {//标记该位置，进入下一行
            vertical ^= (1 << c);
            right_s ^= (1 << j);
            left_s ^= (1 << k);
            dfs(r+1);
            //回溯
            vertical ^= (1 << c);
            right_s ^= (1 << j);
            left_s ^= (1 << k);
        }
    }
}

int main() {
    dfs(0);
    cout << count << endl;
    return 0;
}

Contents