位运算与二进制表示集合

位运算

运算符

运算	运算符	数学符号表示	解释
与	`&`	&、\(and\)	只有两个对应位都为 \(1\) 时才为 \(1\)
或	\(\|\)	\(\|\)、\(or\)	只要两个对应位有一个 \(1\) 时就为 \(1\)
异或	`^`	\(\oplus\)、\(xor\)	只有两个对应位不同时才为 \(1\)
取反	`~`	无	二进制位均全部取反（\(0\) 变为 \(1\)，\(1\) 变为 \(0\)）
左移	`<<`	无	`num << i` 表示将 \(num\) 的二进制位向左移动 \(i\) 位所得的值
带符号右移	`>>`	无	正数右移后，高位补 \(0\)，负数右移后，高位补 \(1\)
无符号右移（\(java\)等部分语言）	`>>>`	无	无论正负，高位均补 \(0\)

原码、反码、补码

最高位是符号位，以下以 \(8\) 位的二进制举例

编码方式	解释	举例
原码	原码就是符号位加上真值的绝对值，即用第一位表示符号，其余位表示值	\(+1_{原}=(0000\ 0001)_{原}\)，\(-1_{原}=(1000\ 0001)_{原}\)
反码	正数的反码是其本身。负数的反码是在其原码的基础上，符号位不变，其余各个位取反.	\(+1_{反}=(0000\ 0001)_{原}=(0000\ 0001)_{反}\)，\(-1_{反}=(1000\ 0001)_{原}=(1111\ 1110)_{反}\)
补码	正数的补码就是其本身。负数的补码是在其原码的基础上，符号位不变，其余各位取反，最后+1。（即在反码的基础上+1）	\(+1_{补}=(0000\ 0001)_{原}=(0000\ 0001)_{反}=(0000\ 0001)_{补}\)，\(-1_{补}=(1000\ 0001)_{原}=(1111\ 1110)_{反}=(1111\ 1111)_{补}\)

计算机采用补码的编码方式

应用

一个数乘除 \(2\) 的非负整数次幂

计算 \(n\times 2^m\)：n << m

计算 \(n\div 2^m\)：n >> m

操作一个数的二进制位

操作	实现	举例
获取 \(a\) 的二进制倒数 \(b\) 位（编号从 \(0\) 开始）	`a >> b & 1`	`4 >> 2 & 1` 等于 `1`
将 \(a\) 的二进制倒数 \(b\) 位设置为 \(0\)	`a & ~(1 << b)`	`5 & ~(1 << 2)`等于`1`
将 \(a\) 的二进制倒数 \(b\) 位设置为 \(1\)	\(a \| (1 << b)\)	\(1 \| (1 << 2)\) 等于`5`
将 \(a\) 的二进制倒数 \(b\) 位取反	`a ^ (1 << b)`	`1 ^ (1 << 2)`等于`5`
获取 \(a\) 的二进制最后一个 \(1\) 的值	`a & -a`（或`a & (~a + 1)`）	`6 & -6`等于`2`
获取 \(a\) 的二进制位最后一个 \(1\) 设置为 \(0\) 的值	`a & (a - 1)`	`6 & (6 - 1)`等于`4`

一些自带的二进制方法

大多通过二分查找的方式实现

	C++（头文件`stdlib.h`中）	Java（均可通过使用`Long`类代替`Integer`类）
十进制转换其他进制（\(2\sim36\) 范围内）	`itoa(数字, char[] ans, 进制)`,`ltoa(数字, char[] ans, 进制)`同时返回值均为`char[]`类型的答案	`Integer.toString(数字, 进制)`
任意进制转换十进制（\(2\sim36\) 范围内）	`strtol(原进制字符数组, 接受剩余非法字符, 进制)`返回十进制数，`strtol`返回`long`类型，`strtoll`返回`long long`类型，`strtoul`返回`unsigned long`类型。还有`double`等类型函数	`Integer.parseInt(字符串String, 进制)`
二进制中 \(1\) 的个数	`int __builtin_popcount(unsigned int x)`及`int __builtin_popcountll(unsigned long long x)`等等	`Integer.bitCount(数字)`
二进制末尾连续 \(0\) 的个数	`int __builtin_ctz(unsigned int x)`，`long`等其他类型同上，当 \(x\) 等于 \(0\) 时，行为未定义	`Integer.numberOfTrailingZeros(数字)`，当 \(x\) 等于 \(0\) 时，返回 \(32\)
二进制前导零的个数（可用来求最高位的 \(1\) 的位置）	`int __builtin_clz(unsigned int x)`，`long`等其他类型同上，当 \(x\) 等于 \(0\) 时，行为未定义	`Integer.numberOfLeadingZeros(数字)`，当 \(x\) 等于 \(0\) 时，返回 \(32\)
获取符号	暂未了解	`Integer.signum(数字)`。当数字大于 \(0\) 时返回 \(1\)。当数字等于 \(0\) 时返回 \(0\)。当数字小于 \(0\) 时返回 \(-1\)。
获取二进制最后一个 \(1\) 的值	暂未了解	`Integer.lowestOneBit(数字)`通过 `x & -x` 实现
获取二进制第一个 \(1\) 的值（也就是小于等于该数的最大的 \(2\) 的幂的值）	暂未了解	`Integer.highestOneBit(数字)`通过调用 `numberOfLeadingZeros(数字)` 实现
二进制循环左移（低位缺少的位通过高位消去的位补充）	暂未了解	`Integer.rotateLeft(数字, 移动位数)`
二进制循环右移（高位缺少的位通过低位消去的位补充）	暂未了解	`Integer.rotateRight(数字, 移动位数)`
二进制按位反转	暂未了解	`Integer.reverse(数字)`返回二进制按位反转后的十进制值

例题

231. 2 的幂 - 力扣

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        return (n & (n - 1)) == 0; 
    }
}

342. 4的幂 - 力扣

class Solution {
    public boolean isPowerOfFour(int n) {
        if (n <= 0) return false;
        if ((n & (n - 1)) != 0) return false;
        return (0b10101010101010101010101010101010 & n) == 0;
    }
}

461. 汉明距离 - 力扣

class Solution {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}

剑指 Offer 15. 二进制中1的个数 - 力扣

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        return Integer.bitCount(n);
    }
}

190. 颠倒二进制位 - 力扣

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        // 或者直接调用
        //return Integer.reverse(n);
        int ans = 0;
        for (int i = 0; i < 16; ++i) {
            ans |= (n >> i & 1) << (31 - i);
            ans |= (n >> (31 - i) & 1) << i;
        }
        return ans;
    }
}

405. 数字转换为十六进制数 - 力扣

每四位二进制数对应一位十六进制数

class Solution {
    char[] ch = "0123456789abcdef".toCharArray();
    final int mask = 0b1111;
    public String toHex(int num) {
        if (num == 0) return "0";
        StringBuilder ans = new StringBuilder();
        while (num != 0) {
            ans.append(ch[num & mask]);
            num >>>= 4; // 注意要无符号右移
        }
        return ans.reverse().toString();
    }
}

477. 汉明距离总和 - 力扣

数列横着看和竖着看是两种方式，有时另一种会十分简便

class Solution {
    public int totalHammingDistance(int[] nums) {
        int n = nums.length, ans = 0;
        for (int i = 0; i < 32; ++i) {
            int sum = 0;
            // 计算第i位1的个数
            for (int v : nums) {
                sum += v >> i & 1;
            }
            ans += sum * (n - sum);
        }
        return ans;
    }
}

693. 交替位二进制数 - 力扣

class Solution {
    public boolean hasAlternatingBits(int n) {
        n ^= n >> 1;
        return n != 0 && (n & (n + 1)) == 0;
    }
}

401. 二进制手表 - 力扣

class Solution {
    // 预处理小时位和分钟位的二进制1的个数
    static LinkedList<String>[] hours = new LinkedList[4];
    static LinkedList<String>[] minutes = new LinkedList[9];
    static {
        for (int i = 0; i < 4; ++i) hours[i] = new LinkedList<String>();
        for (int i = 0; i < 9; ++i) minutes[i] = new LinkedList<String>();
        for (int i = 0; i < 12; ++i) {
            hours[Integer.bitCount(i)].add(Integer.toString(i));
        }
        for (int i = 0; i < 10; ++i) {
            minutes[Integer.bitCount(i)].add(":0" + i);
        }
        for (int i = 10; i < 60; ++i) {
            minutes[Integer.bitCount(i)].add(":" + i);
        }
    }
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> ans = new LinkedList<String>();
        if (turnedOn >= 9) return ans;
        // 枚举小时位灯的个数
        for (int i = Math.min(3, turnedOn); i >= 0; --i) {
            for (String hour : hours[i]) {
                for (String minute : minutes[turnedOn - i]) {
                    ans.add(hour + minute);
                }
            }
        }
        return ans;
    }
}

二进制表示集合

集合操作

操作	集合表示	位运算符
交集	\(a\cap b\)	`a & b`
并集	\(a\cup b\)	\(a \| b\)
补集	\(\bar{a}\)	`~a`（全集为二进制位均为 \(1\)）
差集	\(a\setminus b\)	`a & (~b)`
对称差	\(a\bigtriangleup b\)	`a ^ b`

遍历子集

若遍历的是二进制表示除前导 \(0\) 外均为 \(1\) 的集合（如 111111），则可以通过下述方式遍历

int n = 1;
int S = (1 << n) - 1;
for (int i = 1; i <= S; ++i) {
    for (int j = 0; j < n; ++j) {//遍历二进制每一位
        if ((i >> j & 1) == 1) {//判断第j位是否存在
            // do something;
        }
    }
}

但如果要屏蔽某一位置的遍历（如111110011），若仍选择通过上述方式遍历，就需要一些判断，更推荐如下做法（逆序遍历）

/*
// 这种写法不会遍历空集
int n = 1;
int S = (1 << n) - 1;
for (int i = S; i != 0; i = (i - 1) & S) {
    for (int j = 0; j < n; ++j) { // 遍历二进制每一位
        if ((i >> j & 1) == 1) { // 判断第j位是否存在
            //do something;
        }
    }
}
*/
int n = 1;
int S = (1 << n) - 1;
int i = S;
do {
    for (int j = 0; j < n; ++j) { // 遍历二进制每一位
        if ((i >> j & 1) == 1) { // 判断第j位是否存在
            //do something;
        }
    }
    i = (i - 1) & S;
} while (i != S);

原理：

减 \(1\) 是为了遍历所有比 \(S\) 小的数，减 \(1\) 的实质就是去掉二进制数的最后一个 \(1\)，并在其后面的位上补上 \(1\)，如\((10100)_2-1=(10011)_2\)
& 操作是让原来 \(S\) 二进制上是 \(0\) 的位均保持 \(0\)
当 \(i\) 变为空集 \(0\) 时，继续减一会变成 \(-1\)，而 \(-1=(111\cdots111)_2\)，他与 \(S\) 做 & 运算就会重新变为 \(S\)，此时循环终止

例题

784. 字母大小写全排列 - 力扣

class Solution {
    public List<String> letterCasePermutation(String s) {
        int len = s.length();
        char[] t = s.toCharArray();
        List<String> ans = new LinkedList<>();
        ans.add(s);
        int S = 0;
        for (int i = 0; i < len; ++i) {
            if (Character.isDigit(t[i])) continue;
            S |= 1 << i;
        }
        for (int i = S; i != 0; i = (i - 1) & S) {
            t = s.toCharArray();
            for (int j = 0; j < len; ++j) {
                if ((i >> j & 1) == 1) t[j] ^= 32; // 英文字母异或32代表大小写转换
            }
            ans.add(new String(t));
        }
        return ans;
    }
}

78. 子集 - 力扣

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int len = nums.length;
        List<List<Integer>> ans = new ArrayList<>(1 << len);
        for (int i = 0, S = 1 << len; i < S; ++i) {
            List<Integer> t = new LinkedList<>();
            for (int j = 0; j < len; ++j) {
                if ((i >> j & 1) == 1) {
                    t.add(nums[j]);
                }
            }
            ans.add(t);
        }
        return ans;
    }
}

90. 子集 II - 力扣

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        List<List<Integer>> ans = new ArrayList<>(1 << len);
        for (int i = 0, S = 1 << len; i < S; ++i) {
            List<Integer> t = new LinkedList<>();
            boolean mark = true;
            for (int j = 0; j < len; ++j) {
                if ((i >> j & 1) == 1) {
                    if (j > 0 && nums[j] == nums[j - 1] && (i >> (j - 1) & 1) == 0) {
                        mark = false;
                        break;
                    }
                    t.add(nums[j]);
                }
            }
            if (mark) ans.add(t);
        }
        return ans;
    }
}

1178. 猜字谜 - 力扣

class Solution {
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (String s : words) {
            // 二进制映射
            int mask = 0;
            for (int i = 0; i < s.length(); ++i) {
                mask |= 1 << (s.charAt(i) - 'a');
            }
            // 题目保证puzzle字符串长度为7
            // 只加入个数小于等于7的减少空间消耗
            if (Integer.bitCount(mask) <= 7) {
                map.put(mask, map.getOrDefault(mask, 0) + 1);
            }
        }
        List<Integer> ans = new ArrayList<>(puzzles.length);
        for (String s : puzzles) {
            // 二进制映射
            int mask = 0;
            // 跳过首字母，之后处理集合的时候单独加上，保证首字母存在
            for (int i = 1; i < s.length(); ++i) {
                mask |= 1 << (s.charAt(i) - 'a');
            }
            int cnt = 0;
            int begin = s.charAt(0) - 'a';
            for (int i = mask; i != 0; i = (i - 1) & mask) {
                // 保证首字母存在
                cnt += map.getOrDefault(i | (1 << begin), 0);
            }
            // 处理空集（只有首字母的情况）
            cnt += map.getOrDefault(1 << begin, 0);
            ans.add(cnt);
        }
        return ans;
    }
}