算法笔记-位运算

Algorithm › bitmap

Overall

位运算， 无非： 与， 或， 非， 左移， 右移， 异或。

目前接触到位运算的思路主要两种：

  • 利用异或，找出重复元素：
    • leetcode 136. 只出现一次的数字
  • 利用 左移+与或， 达到用 bit 形成 bool数组， 也即 Redis中的bitmap的形式：
    • leetcode 面试题 01.01 判断无重复字符的字符串
  • 信息论 （略）：
    • 老鼠试毒

关于异或， 其记忆的点为： 异或结果与顺序无关。

关于 左移+与或 这种类型， 只需记忆 bitmap即可， 当一个问题， 需要使用 数组记录一 二元变量的值时， 可以考虑使用 bitmap 替代 Bool[]。

而bitmap的使用关键， 即是理解， 要 update bitmap中的一位， 则需 将 bitmap 与一 tempBit 进行 或 运算。 读， 则进行 与 运算。 其中 tempBit是一个只包含一个 ‘1’ 的二进制数字。 1 所在的 索引， 即要 读/写 的 bitmap中的对应位索引。

同时， 字符转数字， 则可通过ASC码实现。 一个字符， 直接进行 左移/右移， 输出的就是数字。 如果需要标的， 则可通过 ”字符-a“ 实现锚定。

Sample Question

leetcode 136

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
"""
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

输入一组数字， 每个元素都重复一次， 只有 一个元素是单独出现的， 没有重复， 找出这个单独的元素

使用异或：
异或的特点： 相同为0， 不同为1， “并且异或的顺序不影响结果” 即 A ^ B ^ A ^ B ^ C = A ^ A ^ B ^ B ^ C..
"""
def fun(nums):
    to_return = 0 # 之所以初始化为0， 因为 如果 0 与 01010110 异或的话， 原值不变, e.g. 0 ^ 34 = 34
    for i in range(len(nums)):
        to_return = to_return ^ nums[i]
    return to_return

leetcode 面试题01.01

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * 无重复字符的字符串
 *
 * 利用bit运算解决 --> 即， 利用 Redis中的bitmap的思路， 形成一个二进制数， 而这个二进制数即相当于一个bool数组。
 * 为什么是bool数组？ 因为 每一位上不是0就是1
 *
 * 那么接下来， 即如何实现的问题：
 *
 * 1. 将字符转换为数字 --> ASC码。
 * 2. 如何将 转换后的数字， 映射到 二进制数字中的一位？ 即， 转换后的数字相当于一个索引， 如何利用这个索引， 读/写 二进制中的某一位？
 *    即， 如何将 1001 改为 1000？ 同时， 如何读取到 1001中的 第2 位是0还是1？
 *    -->
 *    通过 与， 或运算。 与即是 读， 或等 便是 写。
 *    以 1001 为例， 要判断 1001 的低处第2位是不是1， 则可用 0010 跟 1001 做 and， 则结果为 1 则代表 第二位为1， 反之为0.
 *    那么， 要将 1001 的低处低2位改为1， 则， 使 1001 |= 0010 即可。 因为 0|0 为0， 0|1 为1， 用0做或， 不会改变原值. 而1 或 任何数
 *    均为1， 所以能达到更改某一个位的值的作用。
 *
 * 3. 至此， 仅剩最后一个步骤， 即如何将字符转换为一个二进制数？
 * --> 左移 + ASC码。
 *     3.1 首先， 要的到 1000， 则只需 将 0001， 也即1， 左移3 位即可。
 *     3.2 每个字符， 与 ‘a’ 相减， 则能得到一个唯一数 x， 也即， 1 左移 x位， 就能得到该字符对应的唯一 二进制数。
 *
 * 4. 最后， 针对此题的context， 字符的数量， 也即字符的种类， 最多有128个， 也即需要 128 位 这么长的二进制数， 也即， 两个 long型变量。
 */
public class UniqueLCCI {
    public static void main(String[] args) {
        //System.out.println(checkUnique("123"));
        char c = 'c';
        System.out.println(c<<0);
    }

    public static boolean checkUnique(String target){

        // high 64 bits and low 64bits
        long high = 0;
        long low = 0;

        for (Character c : target.toCharArray()){
            // check use high bits or low bits
            if (c >= 64){
                long toBit = 1l << (c-64);
                if ((high & toBit) != 0){
                    return false;
                }
                // if not return, then update high bits to record a character
                high |= toBit;
            }
            else{
                long toBit = 1l << c;

                if ((low & toBit) != 0){
                    return false;
                }

                low |= toBit;
            }

        }
        return true;
    }
}