Problem：面试题 05.08. 绘制直线
基本思路
我们发现这道题仅仅只是求某一行的像素点，其它行的像素点都为 。故我们可以把问题「求屏幕像素」转化成子问题「求行像素」，最终在将行像素数组复制到屏幕像素数组中，这样我们便暂时不用考虑处理行数组中像素的索引到屏幕数组索引中的映射，这样问题就稍微简单一些。
对于求行像素的问题分析如下：
- 对于行像素数组 ，需要初始化 个 int 变量的空间来存储像素值。
- 接下来，我们要找 中第一个 出现的偏移置：；以及最后一个 出现的偏移置：。
- 当 时：可知 ，不需要操作。
- 当 时： 的高 位必定为 ，利用 即可得到待定的 二进制码。
- 当 时：，此时将上一次待定的 放入之前的 （因为之前待定的 后面的低位不会发生变化），并设置待定的 为 。
- 当 时：上一次待定 的低 位应当置 ，利用掩码运算 即可完成操作。
最后，将行像素数组复制到屏幕数组中的 的位置上。
当然，我们可以在上述代码的基础上利用行偏移直接映射行到屏幕，省去 数组的空间。
注意点
在 Java 语言中，int 类型的左移位数 时，JVM 会将 对 取模，以确保左移的位数在 x在 [ 之间。因此，代码
1 << 32 - x1 % 32
应当写成
1 << 31 - x1 % 32 << 1
代码
子问题「只考虑行」
Java
class Solution { public int[] drawLine(int length, int w, int x1, int x2, int y) { int[] row = new int[w / 32]; int offset = x1 / 32; int bits = (1 << 31 - x1 % 32 << 1) - 1; while (offset < x2 / 32) { row[offset++] = bits; bits = 0xffffffff; } row[offset] = bits & (0xffffffff << 31 - x2 % 32); int[] ans = new int[length]; System.arraycopy(row, 0, ans, y * row.length, row.length); return ans; } }
直接将行映射到屏幕
Java
class Solution { public int[] drawLine(int length, int w, int x1, int x2, int y) { int[] ans = new int[length]; int rowOffset = w / 32 * y, offset = x1 / 32; int bits = (1 << 31 - x1 % 32 << 1) - 1; while (offset < x2 / 32) { ans[rowOffset + offset] = bits; offset++; bits = 0xffffffff; } ans[rowOffset + offset] = bits & (0xffffffff << 31 - x2 % 32); return ans; } }
复杂度分析
- 时间复杂度：，不考虑分配数组时需要的时间，最多需要 次位运算的操作。
- 空间复杂度：，不考虑结果数组只需要常数空间。
位运算的奇技赢巧
- 判断奇偶：
- 奇：
(x & 1) == 1(x & 1) != 0 - 偶：
(x & 1) == 0(x & 1) != 1
- 乘（或除）以 2 的幂次：
x >> nx / 2^nx << nx * 2^n
- 去除最后一位 1：
x & (x - 1)
- 得到最后一位 1：
x & -x
- 判断 2 的幂次：
x & (x - 1) == 0
- 交换两个数：
a ^= b; b ^= a; a ^= b;
- 交换符号：
~x + 1-x
- 取绝对值：
(x ^ x >> size(x) - 1) - (x >> size(x) - 1)x < 0 ? -x : x
- 构造 n 个 1：
(1 << n) - 1
- 将最左边的 n 位清零：
x & (~0 << n)
- 获取 x 的第 n 位值（0 或 1）：
(x >> n) & 1
- 获取 x 的第 n 位的幂值：
x & (1 << n)
- 仅将第 n 位置为 1：
x | (1 << n)
- 仅将第 n 位置为 0：
x & (~(1 << n))
- 将 x 最高位至第 n 位（含）清零：
x & ((1 << n) - 1)
- 将第 n 位至第 0 位（含）清零：
x & (~((1 << (n + 1)) - 1))
- 取反第 n 位：
x ^ (1 << n)
- 异或满足交换律、结合律：
a ^ b ^ a = b ^ (a ^ a) = b ^ 0 = b