题解系列第三弹，这次来看一些位运算的例题。

利用位运算求唯一元素

题目一

题目：给出 n 个整数，已知仅有一个元素出现一次，其他元素均成对出现，请输出该“唯一元素”。

题解：第一次看到该问题的解法是在邓公的在线课堂上，利用异或运算满足交换律、结合律且同数异或得零的特性，直接将初始值设为零，做一趟线性扫描与每个元素做异或操作更新自身值最后即获得“唯一元素”的值，返回即可。这是我目前在笔试中遇到的唯一与位运算相关的试题。附 LeetCode 题目链接[1]。

题目二

题目：给出 n 个整数，已知仅有一个元素出现一次，其他元素均出现 m 次，请输出该“唯一元素”。

题解：仅从异或的角度思考此类问题的解法容易让人掉入思维陷阱，对于此类问题的一般形式，我们实际上可以通过遍历给定数组记录各比特位 1 出现的次数，最后将结果初始化为 0，根据比特位计数结果把出现次数不是 m 的整数倍的比特位全置 1 即可。通过位运算执行该过程仅是做了高效实现，并非改变了算法理论复杂度。建议将“计数”原理和位运算技巧(技巧1: m 次出现等同于 0 次出现，仅需 cell(log_2(m)) * sizeof(integer) 比特即可完成计数，节省空间。技巧2: 整数加法可以手动通过位运算模拟，以二进制表示为前提，XOR 即为求得各位加和值，AND 即求各位进位值，+1 即遇一置零，直到找到首个零置一并停止，其实就是通过代码复现芯片底层通过门电路完成运算的逻辑) 分开来看，易于消化理解，“题目一”中可以通过单个计数变量一趟扫描完成，但只是该类问题的简化实例。如 m=3 时，可通过下面这种“奇技淫巧”完成计算任务，但本质还是通过位运算实现高效“计数”。参考 LeetCode 原题[2]。

int singleNumber(vector<int>& nums) {
    int bits01 = 0, bits10 = 0;
    for (auto num:nums) {
        // only when high bit is 0 and self is 0, take 1
        // 1 meet 1 would lead to 0
        bits01 = (bits01^num)&(~bits10);
        // only when meet 1 that made low bit turned 0
        // low bit would provide all 1 to it when high is 1
        bits10 = (bits10^num)&(~bits01);
    }
    return bits01;
}

题目三

题目：给出 n 个整数，已知有两个元素仅出现一次，其他元素均成对出现，请输出两个“特殊元素”。

题解：解题关键在于找出两个元素的差异并利用该差异获取二者的具体值。首先参考“题目一”的操作如法炮制获得两元素的异或值，然后找出该值首个值为1的比特位(异或运算零零得零，一一得零，零一得一，一零得一，直观看就是 XOR 结果为0表示比特位对应值相同，结果为1表示比特位对应值不同，恰好帮助我们捕捉两数差异)，拿到该差异值后即可重新遍历数组，仅和该值 AND 结果不为零(即对应比特位为 1) 的数做异或操作，即求得两数中该位为1的那个数。继而再将该数异或两数的异或，即得到另一个数(是不是又很拗口 :)，这里求差异值也有个位运算的“奇技淫巧”-因为计算机上带符号整数表示能力有限，加负数其实是加了一个将对应绝对值相同的正数所有位置反再+1的“超过表示范围的正数”，两者相加发生一次上溢之后所有有效比特位都被置零，等同于与自身相反数相加得零，联系我们之前说过的+1是“遇一置零，直到找到首个零置一并停止”的备注，(某数 AND 自身的相反数)即可得到该数首个值非零(就是一）的比特，对 A XOR B 的值做该操作就找出了首个差异位。实际操作不理解的话，直接不断右移动直到找到1，再让初值为1的变量左移对应步数即可，反正是常数时间，不必要上各种“奇技淫巧”。对应代码如下，此处继续给出 LeetCode 原题链接[3]。且此处声明，本人在笔试中只遇到过“题目一”。

vector<int> singleNumber(vector<int>& nums) {
    // need the guarantee that 
    int a_xor_b = 0;
    for (auto num:nums) {
        a_xor_b ^= num;
    }

    int a_first_unique_one = (a_xor_b) & (-a_xor_b);
    int a = 0;
    for (auto num:nums) {
        if (num&a_first_unique_one)
            a ^= num;
    }
    vector<int> res{a, a^a_xor_b};
    return res;
}

利用位运算加速 N 皇后求解

题目：国际象棋中的皇后，可以攻击同一行/列/对角线上的所有对手，给出棋盘大小 N，求所有可能的 N 个皇后不能互相攻击的放置数或放置方式。

题解：实际就是做深度优先搜索(DFS)，维护每列/主对角线/辅对角线的状态(“已占据”/”仍可用”)从第一行起根据状态变量判定每一列是否可用，若可用，则做放置，通过递归调用进入下一列的处理，调用返回后清空上一个位置的放置操作并尝试后续位置。只在最后一行判定并报告成功放置，更新计数变量或记录新的可行放置。该问题搜索空间极大，可通过位运算做算法的高效实现，具体策略为 1) 通过比特记录各列/主对角线/辅对角线是否已被占用 2) 初始仅记录与第一行相关的 N 条主对角线和辅对角线状态，在第一行处理完成后因所有涉及第一行的对角线状态均无需再维护，分别对二者做左移/右移操作，这样所有时刻需要维护的状态变量均是 N 位，节约空间方便对齐。N <= 32 时对应代码如下(两年多以前的老代码，参考了 该博客[4])，若 N > 32，需使用 std::bitset bits 等工具辅助处理，但考虑搜索空间，N 过大时实际无法在合理时间内获得所需结果，一般题目测例 N 均在 16 以内 :) LeetCode 原题1[5], LeetCode 原题2[6]。

class Solution {
public:
    int N;
    int mask;
    string *row;
    vector<int> *placement;
    vector<vector<string>> res;

    void put(int row_id, int col_status, int floating_ld, int floating_ad) {
        if (col_status == mask) {
            vector<string> new_board;
            for (int i = 0; i < N; i++) {
                (*row)[(*placement)[i]] = 'Q';
                new_board.push_back(*row);
                (*row)[(*placement)[i]] = '.';
            }
            res.push_back(new_board);
        } else {
            int available = mask &(~(col_status | floating_ld | floating_ad));
            while (available) {
                int position = available & (~available + 1); // 单取置位 bit
                int bit_pos = -1, tmp = position;
                while (tmp != 0) {
                    bit_pos++;
                    tmp >>= 1;
                }
                (*placement)[row_id] = bit_pos;
                available -= position; // 又被 occupy 一个
                put(row_id+1, col_status | position, (floating_ld | position) << 1, (floating_ad | position) >> 1);// 其实 + 也可以，但 | 更快
                (*placement)[row_id] = -1;
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        N = n;
        mask = (1 << n) - 1;
        row = new string(n, '.');
        placement = new vector<int>(n, -1);
        put(0, 0, 0, 0);

        delete row;
        delete placement;
        return res;
    }
};

秘籍

继续推荐邓公的数据结构与算法 MOOC 大讲堂👍 数据结构(上)[7], 数据结构(下)[8], THUOJ[9], DSA.WORKSPACE[10]，十二道编程题做了不吃亏，做了不上当(不能用 STL， 各种结构全要手动实现 :)。

外加 DPV算法书[11] 及对应教学视频[12]。

后续题解会陆续推送，欢迎关注及订阅 :)

References

[1] Single Number: https://leetcode.com/problems/single-number/

[2] Single Number-II: https://leetcode.com/problems/single-number-ii/

[3] Single Number-III: https://leetcode.com/problems/single-number-iii/

[4] 该博客: https://blog.csdn.net/hacker00011000/article/details/51582300

[5] 需要输出棋盘状态: https://leetcode.com/problems/n-queens/

[6] 直接计数，上一题答案删删改改即可: https://leetcode.com/problems/n-queens-ii/

[7] 数据结构(上): https://next.xuetangx.com/course/THU08091000384

[8] 数据结构(下): https://next.xuetangx.com/course/THU08091002048

[9] THUOJ: https://dsa.cs.tsinghua.edu.cn/oj/

[10] DSA.WORKSPACE: https://github.com/pmixer/dsa.workspace

[11] Dasgupta S, Papadimitriou C H, Vazirani U V. Algorithms[M]. New York: McGraw-Hill Higher Education, 2008.: http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf

[12] Gatech CS6515 Course: https://classroom.udacity.com/courses/ud401